5 ms·
What really worries me about de-duping is what if it fucks up your files. What if one file just happens to have the same hash as another completely different fi
by hristov 15y ago
What really worries me about de-duping is what if it fucks up your files. What if one file just happens to have the same hash as another completely different file uploaded by a different person? Then all of a sudden, this really important contract that you think you have stored online and in the dropbox folders of your four different computers gets automatically deleted and replaced with a completely different file everywhere. And if you have set up automatic backups like a good boy, it may even be automatically replaced in all your backups before you figure out the problem.
I know you will say that the hashes are long enough so this should not happen until dropbox has trillions of files, etc. But those calculations are all based on assumption of random data in the files. We all know that various computer files may have structured and patterned data. It is possible for the data in certain types of files to be structured in such a way as to produce a much narrower range of possible hashes than generally assumed.
And with 25 million users and hundreds of millions of files, God knows what may happen.
- thurn 15y agoAs long as they're using a reasonable hash, that probably won't be much of a concern any time soon. To give some context, a 256 bit key space is about enough to uniquely identify every atom in the known universe.
- hristov 15y agoThat is an impressive fact, but not really relevant IMO. There are many more possible files than particles in the universe. A hash does not uniquely identify a file from all other possible files. This follows from the definition of a hash function.
- Dylan16807 15y agoIt's not going to happen unless an attack is discovered on the hash algorithm, and even they they'll need to know the hash of your file. And it's still not going to replace the version you have on your computer; only fresh downloads from dropbox will be wrong.
- dedward 15y agoMore likely, and worrying, is that it could happen by accident. Hashing is not the same as compression - we should all know that by now. Pigeonhole principle and all that. In a 256 bit hash, there are 2^256 possible hash values. There are far more than 2^256 possible values that can be hashed. Therefore, hash collisions are inevitable. There is no way to take a hash and expand it back to a unique original value, or it would be a compression algorithm, not a hash.
- Dylan16807 15y agoI don't buy that argument. We have about 2^70 bytes in the entire world. To collide accidentally you're going to need to approach 2^128 items in dropbox. That's not 'inevitable'.
- hristov 15y agoHow did you do that math? To get a hash collision you only need two files and some bad luck.
- william42 15y agoThe probability of a hash collision between n files if there are N possible hashes, assuming that each hash is equally likely, is roughly 1-e^(-n^2/(2N))[1]. Let's suppose that there are roughly a trillion, that is, 2^20, files; this is way more than the actual number of files, by the way. And let's suppose that we have a 256-bit hash such that every 256-bit string is equally likely(a reasonable assumption as long as the hash hasn't been defeated)--the number of possible hashes is 2^256. So the chance of a collision is roughly 1-e^(-2^80/(2^257)); since the number inside the exponential is so small, we can approximate it as 2^-177, or less than 10^-53. That number is so small that it's more likely your office will get hit by multiple independent meteors. [1]This formula is taken from http://en.wikipedia.org/wiki/Birthday_paradox http://en.wikipedia.org/wiki/Birthday_paradox
- 15y ago