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.

Improve this question
2
  • 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, 2015 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, 2015 at 1:30

2 Answers 2

Reset to default
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.

Improve this answer
7
  • 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, 2015 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, 2015 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, 2015 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, 2015 at 0:06
  • 1
    2^80 is about one month for the bitcoin mining network.
    – CodesInChaos
    Oct 26, 2015 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.

Improve this answer
5
  • 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, 2015 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, 2015 at 20:47
  • Not if you're calculating the Meaning of Life, The Universe and Everything
    – CodyBugstein
    Oct 25, 2015 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, 2015 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, 2015 at 7:49

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .