The birthday attack and output length

Why finding any hash collision takes far fewer attempts than intuition suggests, and why that forces every cryptographic hash function to have an output of at least 160 bits.

State the birthday problem's result: 23 people are enough for a better-than-even chance of a shared birthday.
Generalise the birthday attack to n uniformly-distributed choices and state its threshold at root N attempts.
Apply the birthday attack to an n-bit hash output and derive the 2^(n/2) attempt count.
State the accepted minimum output length for a cryptographic hash function and the resulting work factor.

15 min read

Intuition

Collision resistance is the easiest of the three properties to attack, because the attacker does not need to match any specific input, any two colliding inputs will do. That extra freedom turns out to make collisions dramatically easier to find than intuition suggests, a phenomenon known as the birthday attack.

Mechanism

The birthday problem. If 365 days are possible birthdays and people are added to a room one at a time, only 23 people are needed before there is a better than 50% chance that two of them share a birthday. Most people guess a much larger number, because they are implicitly asking “does someone share my birthday?”, a single fixed target. The actual question is “does any pair in the room share a birthday?”, which has far more ways to succeed: with 23 people there are $\binom{23}{2} = 253$ distinct pairs to check, not 23 individual comparisons against one target.

A sketch of how the probability of no match falls as people are added: the first person cannot conflict with anyone (probability 1), the second has a $364/365$ chance of a new birthday, and so on, so the probability that all $k$ birthdays stay unique is the product $1 \cdot \frac{364}{365} \cdots \frac{365-k+1}{365}$ .

k	P(no match)
20	58.9%
22	52.4%
23	49.3%
25	43.1%

At $k = 23$ , P(no match) drops to 49.3%, meaning P(at least one match) has just crossed 50%.

Mechanism

Generalised birthday attack. If values are drawn uniformly at random from a range of $N$ possible values, the probability of hitting a repeated value exceeds 50% after roughly $\sqrt{N}$ draws, far fewer than $N$ itself. 50% is the standard benchmark in cryptanalysis: once an attacker has better-than-coin-flip odds, the scheme is treated as practically broken.

Formula

Birthday attack, general form

\text{after } \sqrt{N} \text{ choices, } P(\text{repeat}) > 0.5

$N$: the size of the uniform range the values are drawn from

Mechanism

Applied to hash functions. A hash function with an $n$ -bit output has $N = 2^n$ possible values. By the birthday bound, more than $\sqrt{2^n} = 2^{n/2}$ attempts give a better than 50% chance of finding some collision, not one matching any particular target. For a hash function with a 64-bit output, that is only $2^{32}$ attempts, small enough to be trivially achievable on modern hardware. This is exactly why hash output length is a hard security requirement rather than a tuning parameter: currently the accepted minimum output length for a cryptographic hash function is $n \geq 160$ bits, which pushes the birthday-attack cost up to $2^{80}$ attempts, considered computationally infeasible today.

Formula

Birthday attack on an n-bit hash

\sqrt{2^n} = 2^{n/2}

$n$: the hash function's output length, in bits
$2^n$: the total number of possible hash values
$2^{n/2}$: the number of attempts needed for a better-than-50% chance of finding some collision

For n = 160, the currently accepted minimum, this is 2^80 attempts.

Worked example

AnswerA 64-bit hash needs about 2^32 attempts for a likely collision; the accepted 160-bit minimum needs 2^80.

Take a hash function with output length $n = 64$ bits. Its output space has $N = 2^{64}$ possible values.
By the birthday bound, the number of attempts needed for a better-than-50% chance of a collision is $\sqrt{N} = \sqrt{2^{64}} = 2^{32}$ .
$2^{32}$ is about 4.3 billion, a search well within reach of ordinary modern hardware. A 64-bit hash is therefore not safe against collision-finding.
Now take the accepted minimum, $n = 160$ bits. The output space is $N = 2^{160}$ .
The birthday bound gives $\sqrt{2^{160}} = 2^{80}$ attempts, currently considered computationally infeasible, which is exactly why 160 bits is the floor rather than 64.

Pitfall

Do not treat the birthday bound $2^{n/2}$ as the cost of all attacks on an $n$ -bit hash. It is specifically the cost of finding any collision. Recovering a preimage for one fixed, given hash value is a different, harder problem: that search has no substitute target to settle for, so its cost stays at the full $2^n$ . An attacker choosing which attack to mount will always prefer the birthday attack when a collision, rather than a specific preimage, is enough for their purpose.

Exam detail

Keep the exact figures memorised: 23 people for the birthday problem’s classic 50% threshold, the general bound $2^{n/2}$ attempts for an $n$ -bit hash, the currently accepted minimum output length of $n \geq 160$ bits, and the resulting work factor of $2^{80}$ attempts. A 64-bit output, by contrast, only needs $2^{32}$ attempts, which is why it is not considered safe.

Recall

Why is 23 the answer to the birthday problem, rather than something closer to half of 365?

The question is not whether one specific birthday is matched, it is whether any two people out of the group match each other. With 23 people there are 253 distinct pairs being checked simultaneously, not 23 individual comparisons against a single fixed date. That many simultaneous chances to match pushes the 50% threshold far lower than intuition, built around matching one target, would predict.

Source

Week 6 Notes PDF