Hacker News Reader

Comment by StavrosK | Hacker News Reader

That'll only take about 10^585 years, assuming you can do a billion hashes a second. Good luck!

Nobody said it would need to be quick.

I thought of using hashes too, but then I realized that after thousands of years, the program is only going to output a collision, and not the original data.

Checking the first and last few bits reduces the number of collisions, but there are still 2^unchecked_bits/2^160 cyphers which map to the same hash. You could store the number of collisions to skip along with the hash, but that number will be about (unchecked_bits - 161) bits long, so that won't work either.

Adding md5 (or whichever other hashing function), I have a feeling (but no direct proof of) it's not just equivalent to adding bits to the sha hash. Anyone with a better sense for hashing than me why my intuition is wrong?

Whether you have two 128-bit hashes or one 256-bit hash, you're still trying to fit 2^n pigeons into (2^128)*(2^128) = 2^256 pigeonholes.

Maybe your intuition is telling you that two hashes must be more secure because if one of the two hash functions turns out to be easy to break, then at least you will still be protected by the other?

No, what I was thinking was more like coverage. For any given hash, you do NOT have the same coverage for the other hash function. Let's make a bucket of all the originating bits of length n that will deliver a collision for one hash function. You are not guaranteed that the results of another hashing function has a uniform distribution. I still think I am wrong but you did not convince me.

Reply on news.ycombinator.com