5

I mean "normal" collisions not based on any attack.

How do i calculate it?

2
  • Can you be a little more specific?
    – user11869
    May 6, 2013 at 0:57
  • Let say a = md5(sha256(someval)) b = md5(sha256(otherval)) What are the chances that a == b? why?
    – kR105
    May 6, 2013 at 2:09

1 Answer 1

10

The relevant principle here is the birthday attack. It roughly states that for a 2n algorithm, your probably of a random collision is between any two items is 50% once you generate 2(n/2) outputs.

When looking at a hashing algorithm, the naive consideration of the algorithm is that the odds are bassed only on the last iteration. In this way, a 128 bit algorithm doesn't care if you feed it 1 bit or a million bits: your odds of collision should be the same for a given number of unique inputs (as you can obviously only input 2 different one-bit values).

Thus, the answer for a 128 bit algorithm is that it has a 50% chance of a collision occurring between any two values after 264 outputs have been created.

3
  • 5
    It is also worth noting that 2^64 is a teeny tiny fraction of the 2^128 hash space.
    – lynks
    May 6, 2013 at 7:48
  • 1
    2^64 is eighteen quintillion. So probably not getting a collision any time soon.
    – swdev
    Jun 19, 2019 at 2:38
  • 2^64 is a high number but it's also for 50% collision probability. In practice, you'll probably want to ensure that the collision probability is lower than your total number of items. ie: you want collisions to be 1 in <however many objects you project on having>. So if you're expecting 100 billion items you ideally want your probability of collisions to be lower than 10^-11 (very far from 50%). In that case, a 128 bit hash like md5 will give you these odds for anything below roughly 2.6×10^13 items (26 trillion). Since 100 billion is below 26 trillion you're good to go. But getting close.
    – D.Mill
    Mar 27 at 23:13

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.