# How much work is required to find multiple collisions for a hash function?

Assume an ideal hash function of output size n bits, finding one collision requires approximately 2^(n/2) evaluations of the hash function using a birthday attack.

However, how many evaluations are required to produce two or more collisions?

Note I am talking about distinct collisions i.e. $H(A)=H(B)$, $H(C)=H(D)$, etc.

## 1 Answer

The expected effort to find $k$ distinct collisions on an ideal hash function of output size $n$ is about $\sqrt{2k} \cdot 2^{n/2} = \sqrt{k2^{n+1}}$ (for $k << 2^{n/2}$).

One way to see this is to look at the probability of the outputs of two distinct inputs colliding, which is $2^{-n}$; if we generate outputs for $\sqrt{2k} \cdot 2^{n/2}$ distinct inputs, there are $(\sqrt{2k} \cdot 2^{n/2} \cdot (\sqrt{2k} \cdot 2^{n/2}-1))/2 \approx 2^nk$ pairs of outputs; if the collision probabilities are independent (which they approximately are if we stay $k << 2^{n/2}$), then the expected number of collisions we get in the set of outputs is $2^{-n} \cdot 2^nk = k$

Note that for $k=1$, we get about $\sqrt{2}\cdot 2^{n/2}$ expected outputs for a single collision. That's not a contradiction to the $2^{n/2}$ rule of thumb; $\sqrt{2}\cdot 2^{n/2}$ is a slightly more precise value.

• Thanks a lot. Even though I am not very good at maths, your solution makes sense to me. – Chaitanya Gupta Jan 23 '15 at 19:43
• I believe you are incorrect in stating the probabilities are independent. (Yet for calculating expectation that isn't required ) – Meir Maor Sep 14 '17 at 3:36