4 ms·

> [...] the implication is that a uniquely identifiable thing can be derived from any given piece of data. This returns some burden to Mega—rather than throw up

by daeken 14y ago

> [...] the implication is that a uniquely identifiable thing can be derived from any given piece of data. This returns some burden to Mega—rather than throw up its hands and say that it has no idea what Mega users Alice or Bob have in their Mega accounts, there apparently is a way of telling whether or not Bob and Alice have the same file or files. If the MPAA gets wind that Bob is hosting a copy of The Hobbit: An Unexpectedly Long Movie in his Mega folder, and Alice also happens to have the same file in her Mega folder, it's trivial to prove that Alice has the same file—in fact, the nature of deduplication means there's some record of every deduplicated block, and therefore every other infringing user. This actually doesn't follow at all. What files a given user has in their account doesn't have to be known to the server, though it's generally not difficult to correlate gets/puts/deletes to accounts. If the hierarchy is handled on the client side and encrypted like everything else, then all the server knows is: we store blobs identified by keys, and when those keys are overlapping, we don't need to store a second copy. This does make keeping track of storage usage impossible.

roc 14y ago
It sounds to me like Mega is just using block-level hardware de-duplication and they're making sure it's clearly spelled out in the Terms. After all, if each file is being encrypted with different keys, then Alice and Bob's encrypted copies of THE HOBBIT wouldn't match at all. So much as removing the file from Mega's servers and re-uploading it would seemingly change the key and thus the encrypted data entirely, right? And when encrypted blocks do happen to match, there'd be absolutely no way of knowing whether they represent the same block of the same source file. In fact, one could be reasonably confident that a block overlap was purely incidental, given the random unique keys. (barring completely broken key generation)
- daeken 14y ago
  > After all, if each file is being encrypted with different keys, then Alice and Bob's encrypted copies of THE HOBBIT wouldn't match at all. So much as removing the file from Mega's servers and re-uploading it would seemingly change the key and thus the encrypted data entirely, right? As far as I can tell, they're generating the keys for the files from a hash of the file, meaning the keys are not random and unique (for the files -- user keys are different). I described rough steps for secure dedupe in another comment below.
  - roc 14y ago
    Then the encryption isn't worth the processing time. And as a 'legal shield' it seems like it will not only be utterly ineffective in court, but it's going to be cited as proof of Mega's ability to know what people are hosting, due their generation of a file fingerprint as a matter of course. They're going to wind up having to maintain a hash blacklist which is going to be just annoying enough that people aren't going to bother. It's a shame mega isn't just running an encrypted block-level store. They should have shipped client binaries that handle the encryption and key generation and simply exchanged blocks with Mega servers.
- jerf 14y ago
  No, it's the other way around; a block overlap is effectively a guarantee it's the same file with the same key. Suppose they are using 1MB chunks. The keys are 16 bytes. The 1MB chunk may be 2 ^ (8 millionish) different things, the keys only 2^128 different things. Thus, two different 1MB chunks, to be the same file with different keys, must have two of their possible 2^128[1] encryptions overlap out of the possibility space of 2^(8 millionish); that any two different chunks would even have such an overlap available is exceedingly, exceedingly improbable, let alone that the two users would end up with the exact correct keys to have actually manifested the overlap. There are only two plausible theories when an overlap occurs: 1. It is the same file with the same key or 2. Someone's worked out how to artificially create a collision. And those two are hardly equal in probability either.... [1]: Yeah, that's a simplification since there aren't actually 2^128 valid keys. Roll with it. Actually I've taken a number of small liberties for simplicity; none of them matter.
  - roc 14y ago
    Why would you choose so large a block size for de-duplication? Your disk space savings decrease as block size increases. Choosing a more effective block size will increase the chance of collisions. And collisions are rather the desired goal of de-duplication.
    - jerf 14y ago
      And all of your other costs associated with the block go up. While I do not work on the backup product my company produces, I've used it as a service. They've told me 1MB is pretty much too small nowadays, though it made sense when they started. People have this weird fetish around deduplication, but it isn't magic. It makes it so the tenth copy of storing a backup of Windows XP doesn't hardly cost you any space. This is where the astonishing compression claims come from. It does not magically compress much of anything else, though. The claims are true, but not generally applicable. In practice, the middle bits of otherwise unrelated files don't get de-duped, excepting a couple of obvious and rare cases like 'a megabyte of zero padding in the middle of a file' which hardly amount to anything. Your World of Warcraft texture file is simply not going to overlap with your eBook copy of 50 Shades of Grey, and in general, two things sampled even from a 2^(524,288) possibility space, which corresponds to an absurdly small 64KB block size, are very unlikely to collide. Block size has very little effect on collisions; what collides are identical files, or files that are nearly identical because they are versions of the same thing (and block size tends to matter surprisingly little there for various reasons), and what doesn't collide is everything else.

by daeken 14y ago

roc 14y ago

It sounds to me like Mega is just using block-level hardware de-duplication and they're making sure it's clearly spelled out in the Terms. After all, if each file is being encrypted with different keys, then Alice and Bob's encrypted copies of THE HOBBIT wouldn't match at all. So much as removing the file from Mega's servers and re-uploading it would seemingly change the key and thus the encrypted data entirely, right? And when encrypted blocks do happen to match, there'd be absolutely no way of knowing whether they represent the same block of the same source file. In fact, one could be reasonably confident that a block overlap was purely incidental, given the random unique keys. (barring completely broken key generation)

daeken 14y ago
> After all, if each file is being encrypted with different keys, then Alice and Bob's encrypted copies of THE HOBBIT wouldn't match at all. So much as removing the file from Mega's servers and re-uploading it would seemingly change the key and thus the encrypted data entirely, right? As far as I can tell, they're generating the keys for the files from a hash of the file, meaning the keys are not random and unique (for the files -- user keys are different). I described rough steps for secure dedupe in another comment below.
- roc 14y ago
  Then the encryption isn't worth the processing time. And as a 'legal shield' it seems like it will not only be utterly ineffective in court, but it's going to be cited as proof of Mega's ability to know what people are hosting, due their generation of a file fingerprint as a matter of course. They're going to wind up having to maintain a hash blacklist which is going to be just annoying enough that people aren't going to bother. It's a shame mega isn't just running an encrypted block-level store. They should have shipped client binaries that handle the encryption and key generation and simply exchanged blocks with Mega servers.
jerf 14y ago
No, it's the other way around; a block overlap is effectively a guarantee it's the same file with the same key. Suppose they are using 1MB chunks. The keys are 16 bytes. The 1MB chunk may be 2 ^ (8 millionish) different things, the keys only 2^128 different things. Thus, two different 1MB chunks, to be the same file with different keys, must have two of their possible 2^128[1] encryptions overlap out of the possibility space of 2^(8 millionish); that any two different chunks would even have such an overlap available is exceedingly, exceedingly improbable, let alone that the two users would end up with the exact correct keys to have actually manifested the overlap. There are only two plausible theories when an overlap occurs: 1. It is the same file with the same key or 2. Someone's worked out how to artificially create a collision. And those two are hardly equal in probability either.... [1]: Yeah, that's a simplification since there aren't actually 2^128 valid keys. Roll with it. Actually I've taken a number of small liberties for simplicity; none of them matter.
- roc 14y ago
  Why would you choose so large a block size for de-duplication? Your disk space savings decrease as block size increases. Choosing a more effective block size will increase the chance of collisions. And collisions are rather the desired goal of de-duplication.
  - jerf 14y ago
    And all of your other costs associated with the block go up. While I do not work on the backup product my company produces, I've used it as a service. They've told me 1MB is pretty much too small nowadays, though it made sense when they started. People have this weird fetish around deduplication, but it isn't magic. It makes it so the tenth copy of storing a backup of Windows XP doesn't hardly cost you any space. This is where the astonishing compression claims come from. It does not magically compress much of anything else, though. The claims are true, but not generally applicable. In practice, the middle bits of otherwise unrelated files don't get de-duped, excepting a couple of obvious and rare cases like 'a megabyte of zero padding in the middle of a file' which hardly amount to anything. Your World of Warcraft texture file is simply not going to overlap with your eBook copy of 50 Shades of Grey, and in general, two things sampled even from a 2^(524,288) possibility space, which corresponds to an absurdly small 64KB block size, are very unlikely to collide. Block size has very little effect on collisions; what collides are identical files, or files that are nearly identical because they are versions of the same thing (and block size tends to matter surprisingly little there for various reasons), and what doesn't collide is everything else.