Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

It'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.


More 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.


I 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'.


+1

Also, keep in mind anything that could conceivably be called a "file" is fundamentally an arrangement of atoms in a measurable state which can be resolved into an ordered sequence bits. Whether that's a capacitor holding or not holding a charge, of a bit of spinning iron oxide with a measurable magnetic orientation - any actual "bit" is made up of many atoms, and any ordered collection of bits requires many more atoms to hold them in their ordered arrangement (and many more atoms to provide the capability of reading this bits).

A terabyte is 2^40 or ~10^12 bits. A hard drive weighs, what, a few hundred grams? Guessing an average molecular weight of ~50, that represents something like 10^24 atoms - suggesting a "bit density" of around 10^12 atoms are required to store each bit.

Even if you turned every single atom in the universe into hard drives to store your files, and stored every possible arrangement of bits you had space for in all that storage, your chances of a 256 bit hash collision is still way smaller than your chance of winning the lottery.

Big numbers are often confusing. 2^256 is a very bit number. Although abstract mathematics makes if easy to say "yeah, but 2^512 is bigger", it's only bigger in an abstract sense, and not useable in any arguement along the lines of "well, if I had 2^512 physical objects"...


How did you do that math? To get a hash collision you only need two files and some bad luck.


The 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


Again all of this assumes unifrom distribution. The files used in dropbox are not guaranteed to be random or uniformly distributed. As I already said in my initial comment, various different files types have internal structures which may (again if you are unlucky) result in multiple different files of those types tending to have similar hashes.


One of the goals of a good hash is a uniform distribution. The source files don't have to be random at all. I wouldn't put any money on the odds of by accident hitting a systematic flaw that security researchers haven't yet found in analyzing the hash.

That said, I think it will be possible to deliberately create a collision in SHA256 at some point in the future.


That's true, but what sort of level of "luck" are we talking about?

Flipping a coin "head or tails" odds?

Buying a winning lottery ticket odds?

Or winning the lottery without buying a ticket and having the atoms forming the winning ticket spontaneously appear in your pocket odds?

Yeah it's _possible_, but 1:2^256 odds are not really something you need to worry about...




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: