Birthday Attack

Let’ assume we have a hash function with an output space of \(2^b\). Then, the number of hash computations required to find a collision with probability 0.5 is roughly \(2^{b/2}\).

Proof: From a past post we know that the probability of a hash collision when computing the hash value for \(n\) different inputs is roughly

\[p \approx 1-e^{\frac{-n(n-1)}{2m}}\]

with \(m=2^b\).

For large \(n\) we can simplify this to

\[p \approx 1-e^{\frac{-n^2}{2m}}\]

Now, we can solve this equation for n:

\[e^{\frac{-n^2}{2m}} \approx 1-p\] \[\frac{-n^2}{2m} \approx \ln (1-p)\] \[\frac{n^2}{2m} \approx -\ln (1-p) = \ln\left(\frac{1}{1-p}\right)\] \[n \approx \sqrt{2m\ln\left(\frac{1}{1-p}\right)}\]

For \(p=0.5\) we finally get \(n \approx 1.177\sqrt{m} \approx \sqrt{m} = \sqrt{2^b} = 2^{b/2}\).