I mean "normal" collisions not based on any attack.
How do i calculate it?
1 Answer
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.
answered May 6, 2013 at 1:31
-
5It is also worth noting that 2^64 is a teeny tiny fraction of the 2^128 hash space.– lynksMay 6, 2013 at 7:48
-
12^64 is eighteen quintillion. So probably not getting a collision any time soon.– swdevJun 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.MillMar 27 at 23:13
a = md5(sha256(someval)) b = md5(sha256(otherval))What are the chances that a == b? why?