0
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

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

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.