The Birthday Paradox and Hash Collisions: Why SHA-256 Has Only 128-Bit Collision Resistance

This article has three layers:

1. The intuition: the birthday paradox and the three properties a hash function must have
2. Real-world use: blockchains, Git, certificates and the breaks of MD5 and SHA-1
3. The mathematics: deriving $\sqrt{N}$, memoryless Pollard-rho-style collision search and a real truncated-collision experiment

Layer 1: The Intuition

1.1 The birthday paradox

There are 365 days in a year. How many people must be in a room for the probability that "two share a birthday" to exceed 50%?

Intuition often answers 183 (half of 365). The correct answer is 23.

The key is that we aren't asking "does someone share a birthday with me", but "do any two people share one". 23 people form $\binom{23}{2} = 253$ pairs, each with a $1/365$ chance of matching, and across 253 pairs the odds become substantial.

1.2 What a hash function is

A hash function compresses data of any length into a fixed-length "fingerprint"; SHA-256, for example, outputs 256 bits. A good hash function must satisfy:

The third corresponds exactly to the birthday paradox: a collision attacker freely chooses both inputs, like finding "any two people" with the same birthday in a room, so only $\sqrt{2^n}$ tries are needed.

1.3 Why collisions are dangerous

If you can find two files A and B with the same hash: get someone to sign the harmless A (a signature really signs the hash), and that signature is equally valid for the harmful B.

Layer 2: Real-World Use

Hash functions are everywhere

• Blockchains: Bitcoin uses SHA-256 for proof of work and for linking blocks; an Ethereum address is the last 20 bytes of the Keccak-256 hash of a public key.
• Merkle trees: thousands of transactions are hashed into a single root, and $\log n$ hashes prove a given transaction is in a block.
• Git: every commit and file is named by a hash (historically SHA-1, now migrating to SHA-256).
• Digital signatures, certificates, password storage and file integrity checks.

A history of collision attacks

SHAttered took about $2^{63}$ SHA-1 computations, far fewer than the $2^{80}$ of a birthday attack. This shows it exploited structural weaknesses in SHA-1, not just the birthday paradox.

The design conclusion: for 128-bit security, collision-resistant uses need 256-bit output. This is why SHA-256 became the default choice.

Layer 3: The Mathematics

3.1 Deriving the birthday bound

Drawing $k$ values independently and uniformly from $N$ possibilities, the probability that all are different is

$$P_{\text{no collision}} = \prod_{i=0}^{k-1}\Big(1 - \frac{i}{N}\Big).$$

Using $1 - x \le e^{-x}$ (approximately equal for small $x$):

$$P_{\text{no collision}} \approx \exp\Big(-\sum_{i=0}^{k-1}\frac{i}{N}\Big) = \exp\Big(-\frac{k(k-1)}{2N}\Big) \approx e^{-k^2/(2N)}.$$

Setting the collision probability to $1/2$ and solving gives

$$k \approx \sqrt{2N \ln 2} \approx 1.18\sqrt{N}.$$

With $N = 365$, $k \approx 22.5$, which matches 23. With $N = 2^{256}$, $k \approx 2^{128}$.

3.2 A worked example: actually finding a collision

3.3 Collision search without much memory

The method above stores every hash seen, which is infeasible at the scale of $2^{64}$. Floyd's cycle detection solves this:

Treat the hash function $H$ as a map on a finite set, and starting from $x_0$ iterate $x_{i+1} = H(x_i)$. Because the set is finite, the sequence eventually enters a cycle, shaped like the Greek letter $\rho$. At the moment it enters the cycle, two different points map to the same point: a collision.

A "tortoise and hare" race (one moves one step at a time, the other two) finds it in $O(\sqrt{N})$ time and $O(1)$ memory. This is the same idea as Pollard rho for solving discrete logarithms. The parallel version by van Oorschot and Wiener lets thousands of machines search at once.

3.4 Why the birthday bound can't be "designed" away

The birthday attack is generic: it ignores the hash function's internal structure and works on any function with $n$-bit output. So the ceiling on collision resistance is always $n/2$ bits. Cryptographers can do only one thing about it: make the output longer.

Summary