The birthday paradox and collisions

How many tries does it take to find a collision on an n-bit digest? Intuition says 2^n. Intuition is wrong, and the gap changes the whole sizing of cryptography.

The birthday paradox

Ask the question: in a group of people, how many must be gathered to have more than a one-in-two chance that two of them share the same birthday?

There are 365 days. One might think about 183 people are needed. The real answer is 23. This is the birthday paradox: it is not paradoxical, just counter-intuitive.

The reason: we are not looking for a person born on a fixed day, we are looking for any pair that coincides. Now the number of pairs in a group of k people is k(k-1)/2, which grows like the square of k. With 23 people, that already makes 253 pairs.

Chercher une préimage      : "qui est né le 14 mars ?"   -> ~365 essais
Chercher une collision     : "deux personnes coïncident" -> ~23 essais
       (même écart entre 2^n et 2^(n/2) sur une empreinte)

Application to hashing

An n-bit digest has 2^n possible values. Let us transpose:

• Finding a preimage or a second preimage (fixed target) costs about 2^n tries.
• Finding a collision (any pair) only costs ~2^(n/2) tries, by the birthday paradox.

This is a major result: the collision resistance of a hash function is at most n/2 bits, regardless of its quality. This is not an implementation flaw, it is an unavoidable mathematical bound.

The sizing table

The security level against collisions is half the size of the digest:

Digest size	Preimage security	Collision security
128 bits (MD5)	2^128	2^64 (breakable)
160 bits (SHA-1)	2^160	2^80 (breakable)
256 bits (SHA-256)	2^256	2^128 (safe)
512 bits (SHA-512)	2^512	2^256 (safe)

The practical consequence

To aim for 128 bits of security against collisions — the current standard — you need a 256-bit digest. This is exactly why SHA-256 is the recommended minimum today: its 256 bits provide 128 bits of collision resistance.

Conversely, MD5's 64 bits of resistance are well within reach of a modern attacker: 2^64 operations are feasible.

In summary

The birthday paradox means that a collision on n bits only costs ~2^(n/2) tries, not 2^n. Collision resistance is therefore worth half the size of the digest. For 128 bits of security, you need a 256-bit digest: this is the reason SHA-256 exists.