The birthday attack on an N-bit hash

Question

A hash function outputs an N-bit digest, so there are d = 2^N equally likely outputs. You feed it random inputs and watch for two that collide. Roughly how many inputs before a collision is more likely than not? What does this say about the security of a 128-bit hash?

Accepted Answer

The birthday threshold for d equally likely values is n \approx \sqrt{2d\ln 2} \approx 1.18\sqrt{d}, derived exactly as in the calendar case: a collision becomes likely once the number of pairs \binom{n}{2} \approx \frac{n^2}{2} reaches about d. With d = 2^N, n \approx 1.18\sqrt{2^N} \approx 2^{N/2}. So you expect a collision after about 2^{N/2} random inputs, the square root of the output space, not the whole space. Consequence for a 128-bit hash. Collision resistance is only about 2^{64} work, not 2^{128}. That is why designers target twice the desired collision security: SHA-256 gives roug…

The birthday attack on an N-bit hash

Your answer

More Probability questions