6

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

How do i calculate it?

2
  • Can you be a little more specific?
    – user11869
    Commented 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
    Commented May 6, 2013 at 2:09

1 Answer 1

12

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
    Commented May 6, 2013 at 7:48
  • 1
    2^64 is eighteen quintillion. So probably not getting a collision any time soon.
    – swdev
    Commented 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
    Commented Mar 27, 2022 at 23:13

You must log in to answer this question.

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