0

I'm wondering why it's so hard to find collisions for cryptographic hashes.

Take for example a hash function that outputs a 64 bit hash.

In order to find collisions, if you feed the function every single 65 bit string possible, aren't you guaranteed to find a collision? The hash function has to turn 65 bits into 64 bits so is has to find some collisions.

Can't a collision be found in a pretty straightforward way using this technique?

I understand computing all of them will take a lot of time but it seems pretty reasonable to do so and create a database index to store them in so hashes can be broken.

  • 4
    Have a look at how much 2^64 already is and take into consideration that common cryptgraphic hashes are >128 Bit. – John Oct 25 '15 at 15:11
  • Also note that as you start to get into the 256-bit range, the mere cost of running a counter from 0 to 2^256-1 in terms of minimum theoretical energy is on the order of a good chunk of the nuclear energy in the galaxy! – Cort Ammon Oct 26 '15 at 1:30
6

Yes, you are right. Although you would expect (statistically) to find a collision already after about 2^32 tries.

If you have a hash of 160 bit length you would have to try 2^80 combinations (on average) to find a collision. But still, with today computing power trying 2^80 combinations will take too long for you to become old enough to see the collision :-)

That's pretty much all about it. Making the bits so many that it just takes to long to try all necessary combinations out.

  • 1
    @RobW: If you only need a collision between any two inputs, then the birthday paradox applies, and you only need to try about sqrt(2*2^n) = 2^(n/2+1/2) inputs to find a collision for an n bit hash. – Ilmari Karonen Oct 25 '15 at 20:59
  • 2⁸⁰ may sound like a lot. But compare that to the number of hashes computed by Bitcoin. Bitcoin has computed approximately 2⁸³ hashes in 2015. – kasperd Oct 25 '15 at 21:23
  • @IlmariKaronen That ("any collision") is also a way to read the question. I was assuming that the OP wanted to construct a table and then look up a specific hash in that table, which would require trying half of the possibilities (2^63 for the example of the OP). – Rob W Oct 25 '15 at 21:28
  • @kasperd Didn't know that number. Although it makes clear why the trend goes to saying 2^80 is no longer enough. – fr00tyl00p Oct 26 '15 at 0:06
  • 1
    2^80 is about one month for the bitcoin mining network. – CodesInChaos Oct 26 '15 at 7:45
4

fr00tyl00p explained it pretty nicely, so I'll just dump some numbers to make clear how much data that would be.

Lets stay with your example (Every 65 bit value hashed to 64 bit). 65 bit can hold 2^65 different values = 36.893.488.147.419.103.232. So you'd need to save at least 2^65 * 64 bit. You may also need some sort of index but lets ignore that for now.

This would require about 256 pebibyte, or 262144 petabyte data. And this is for only 64 bit hashes and without any form of index.

  • wow that's an insane amount of memory. But probably in the not too distant future, it won't be as insane – CodyBugstein Oct 25 '15 at 19:44
  • 1
    Also: if you can try one combination per nanosecond, this will take 2^65/(1e9*86400*365) = 1170 years. Too long to wait for. – Guntram Blohm Oct 25 '15 at 20:47
  • Not if you're calculating the Meaning of Life, The Universe and Everything – CodyBugstein Oct 25 '15 at 22:18
  • 1PB is only 2⁵⁰ bytes. 2⁶⁰ bytes is 1EB. You don't actually need to store 2⁶⁴ hashes though. If you combine a birthday attack with rainbow tables, you only need to store 2¹⁶ hashes in order to produce a collision on a hash function with 64 bits of output. – kasperd Oct 25 '15 at 22:29
  • 1) You'll find a collision after around 2^32 computations (birthday problem), so even with your naive algorithm you'd only need a few GB. 2) If you use a proper algorithm (cycle finding, distinguished points etc.) for collision finding you barely need any storage at all. – CodesInChaos Oct 26 '15 at 7:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.