The Birthday Attack

Suppose you host a party and wonder how many guests you need before two share a birthday. Most people guess hundreds. The true answer is astonishingly small — just 23 people give better than even odds. This counterintuitive fact is not a party trick. It is a precise mathematical bound with devastating consequences for Cryptographic Hash Functions. Any hash function producing an $n$ -bit digest can be forced into a collision using roughly $2^{n/2}$ evaluations. This is far fewer than the $2^n$ one might naively expect. The birthday attack matters because it sets the real security level of every hash function deployed in practice. Designers cannot simply pick a digest length that resists brute-force preimage search. They must double it to resist collision search. This single insight explains why MD5's 128-bit output was declared broken long before any structural flaw was found. It also explains why SHA-1's 160 bits proved insufficient. And it explains why SHA-256 and SHA-3 target 256-bit or larger outputs. They do so specifically to keep collision search near $2^{128}$ operations. The big picture is a clean piece of probabilistic reasoning. When sampling uniformly from a large set, a repeat tends to appear quickly. The expected number of draws before a repeat scales as the square root of the set size. It does not scale as the set size itself. This "square-root law" recurs throughout cryptography and computer science. It appears in collision-finding in hash tables. It also appears in the analysis of hash-based signatures and meet-in-the-middle attacks. This article derives the birthday bound rigorously. It walks through the generic collision-search algorithm step by step. It quantifies the memory-time tradeoffs of real implementations. It also draws out the exact design rule — double the output length. Every modern hash function follows this rule. The article closes by connecting collision resistance to Message Authentication Codes. There, similar birthday-style reasoning bounds how much data a MAC key can safely protect.

Key takeaways

A birthday attack finds a hash collision in roughly $2^{n/2}$ trials for an $n$ -bit digest, not $2^n$ .
The bound comes from the classic birthday paradox: collisions in a random sample appear surprisingly fast.
Practical algorithms (like Floyd's cycle-finding) achieve this bound with negligible memory.
Because of this bound, secure hash functions need digests at least twice the desired security level in bits.
MD5 (128-bit) and SHA-1 (160-bit) are both broken in practice partly due to birthday-style collision search.
The same square-root scaling underlies attacks on MACs, nonces, and other uniformly-sampled cryptographic values.

The core insight

Collisions in a random $n$ -bit hash function appear after only about $2^{n/2}$ samples, so digest length must be doubled to achieve a target collision-resistance security level.

The idea

A hash function $H$ maps arbitrary-length inputs to fixed-length $n$ -bit digests. Collision resistance means it should be computationally infeasible to find distinct inputs $x \ne y$ with $H(x) = H(y)$ . The naive intuition — that finding a collision requires trying close to $2^n$ inputs — is wrong, and the reason is a purely combinatorial fact about random sampling known as the birthday paradox. Model each hash evaluation as drawing a uniformly random value from a set of $N = 2^n$ possible digests (the random oracle idealization). The question "how many draws until two draws collide" is exactly the birthday problem, historically posed as "how many people are needed before two share a birthday" with $N = 365$ . The surprising answer is that the number of draws needed scales as $\Theta(\sqrt{N})$ , not $\Theta(N)$ . Applied to hashing, this means an attacker needs only about $2^{n/2}$ hash evaluations — not $2^n$ — to find some pair of inputs that collide, with no target digest specified in advance. This is fundamentally different from a preimage attack, where the adversary is given a specific target digest $y$ and must find any $x$ with $H(x) = y$ ; that task genuinely requires about $2^n$ trials because the attacker is confined to hitting one fixed value. The birthday attack instead exploits the freedom to compare all pairs among a batch of random samples, and the number of pairs among $k$ samples grows quadratically as $\binom{k}{2}$ , which is what lets a linear-in- $\sqrt{N}$ sample size generate enough pairwise comparisons to expect a match.

How it works

Deriving the bound. Suppose we draw $k$ independent uniform samples from a set of size $N$ . Let $\bar{P}(k)$ be the probability that all $k$ samples are distinct (no collision). Using the exact formula:

\bar{P}(k) = \prod_{i=0}^{k-1}\left(1 - \frac{i}{N}\right)

Taking logarithms and using $\ln(1-x) \approx -x$ for small $x$ :

\ln \bar{P}(k) \approx -\sum_{i=0}^{k-1} \frac{i}{N} = -\frac{k(k-1)}{2N} \approx -\frac{k^2}{2N}

\bar{P}(k) \approx e^{-k^2/2N}

Setting the collision probability $1 - \bar{P}(k) = 1/2$ and solving:

e^{-k^2/2N} = \tfrac12 \quad\Longrightarrow\quad k^2 = 2N \ln 2 \quad\Longrightarrow\quad k \approx 1.1774\sqrt{N}

For $N = 365$ , this gives $k \approx 22.5$ , matching the well-known "23 people" result. For a hash function with $N = 2^n$ , this gives:

k \approx 1.1774 \cdot 2^{n/2}

which is the origin of the standard rule of thumb that roughly $2^{n/2}$ hash evaluations suffice to find a collision with even odds.

The generic algorithm. The simplest approach is to hash random inputs, store each digest in a table, and check for a repeat. ``` function NAIVE-BIRTHDAY-ATTACK(H, n):

# H: hash function producing n-bit digests table = empty hash map from digest -> input loop: x = random input d = H(x) if d is in table and table[d] != x: return (table[d], x) # collision found table[d] = x ``` Because the digest space has size $N = 2^n$ , the derivation above shows this loop terminates after an expected $\Theta(\sqrt{N}) = \Theta(2^{n/2})$ iterations. The catch is space: the table itself grows to size $\Theta(2^{n/2})$ , which for a 256-bit hash ( $2^{128}$ entries) is utterly infeasible to store.

Memory-free collision search. In practice, attackers use cycle-detection techniques that need only constant memory, exploiting the fact that iterating a hash function $x_{i+1} = H(x_i)$ over a finite domain must eventually enter a cycle (a "rho" shape: a tail leading into a loop). Floyd's cycle-finding algorithm (tortoise and hare) locates a collision in the sequence using two pointers moving at different speeds. ``` function FLOYD-COLLISION(H, x0):

# Finds i < j with H^i(x0) colliding into the cycle, using O(1) memory tortoise = H(x0) hare = H(H(x0)) while tortoise != hare: tortoise = H(tortoise) hare = H(H(hare))

# tortoise and hare are now in the cycle at the same point

# find the start of the cycle (the actual collision point) mu = 0 tortoise = x0 while tortoise != hare: tortoise = H(tortoise) hare = H(hare) mu = mu + 1 lambda = 1 hare = H(tortoise) while tortoise != hare: hare = H(hare) lambda = lambda + 1 return (mu, lambda) # mu = tail length, lambda = cycle length ``` This still requires $\Theta(2^{n/2})$ hash evaluations on expectation (by the same birthday-style analysis applied to the functional graph of $H$ ), but uses only $O(1)$ memory instead of $O(2^{n/2})$ storage — a crucial practical improvement, since memory access often dominates real-world cost more than raw computation.

Figure

The birthday collision search: a functional graph forming a "rho" shape, where iterating H eventually cycles

Complexity & correctness

Time complexity. The expected number of hash evaluations to find a collision is $\Theta(2^{n/2})$ . This follows directly from the derivation above: the collision probability transitions from near 0 to near 1 within a window of $\Theta(\sqrt{N})$ samples, and by a coupon-collector-style argument the expected number of draws until the first collision is exactly:

\mathbb{E}[k] = \sqrt{\frac{\pi N}{2}} + O(1) \approx 1.2533\sqrt{N}

a classical result obtainable by summing $\bar P(k)$ over all $k$ (since $\mathbb{E}[k] = \sum_{k\ge 0} \bar P(k)$ for a non-negative integer random variable).

Space complexity. The naive table-based algorithm requires $\Theta(2^{n/2})$ memory to store all seen digests for comparison. The Floyd/Brent cycle-detection variants reduce this to $O(1)$ auxiliary memory at the cost of a small constant-factor slowdown (roughly 2-3x more hash evaluations), because they must re-walk the sequence to locate the exact meeting point. This is the standard time-memory tradeoff: parallel variants (parallel collision search, van Oorschot–Wiener) distribute the $2^{n/2}$ work across many machines using distinguished points, achieving near-linear speedup with sublinear memory per machine.

Correctness argument. The core claim — that $\Theta(\sqrt N)$ samples suffice for a collision with constant probability — rests on two facts, both provable rigorously: 1. Union bound lower bound direction: for $k$ samples there are $\binom{k}{2} \approx k^2/2$ pairs, each colliding independently with probability $1/N$ (approximately, ignoring dependencies), so the expected number of colliding pairs is $\approx k^2/(2N)$ . Setting this to $\Theta(1)$ forces $k = \Theta(\sqrt N)$ , giving the heuristic scaling immediately. 2. Exact computation direction: the exact product formula $\bar P(k) = \prod_{i=0}^{k-1}(1 - i/N)$ is a straightforward application of the multiplication rule for conditional probabilities (the $i$ -th draw avoids all $i$ previous distinct values with probability $(N-i)/N$ ), and the Taylor approximation $\ln(1-x) \approx -x$ is valid whenever $i \ll N$ , which holds throughout the relevant range $k = O(\sqrt N)$ since then $i/N = O(1/\sqrt N) \to 0$ . Both directions agree at $k \approx \sqrt{N}$ , confirming the bound is tight, not just an upper or lower estimate.

Honest tradeoffs. The birthday bound is an attack on collision resistance specifically — it says nothing about preimage resistance, which genuinely costs $\Theta(2^n)$ even generically. A hash function can therefore be "birthday-bound broken" (collisions found faster than expected due to a structural weakness, as with MD5) while remaining preimage-resistant for practical purposes. Conversely, even an ideal, structurally perfect hash function is still only as collision-resistant as $2^{n/2}$ — this is an information-theoretic floor, not a design flaw, so no amount of clever construction can push collision resistance past $2^{n/2}$ for an $n$ -bit output.

Worked example

Take a toy hash function with only $n = 16$ bits of output, so $N = 2^{16} = 65{,}536$ possible digests. The birthday bound predicts a 50% chance of a collision after:

k \approx 1.1774 \sqrt{65{,}536} = 1.1774 \times 256 \approx 301 \text{ hash evaluations}

compare this to $2^{16} = 65{,}536$ , the number a naive preimage-style brute force would need — over 200 times more work.

Number of samples $k$	Formula estimate $1-\bar P(k)$	Interpretation
50	$1 - e^{-50^2/(2\cdot 65536)} \approx 1.9\%$	Very unlikely yet
150	$1 - e^{-150^2/(2\cdot 65536)} \approx 15.7\%$	Rising quickly
301	$1 - e^{-301^2/(2\cdot 65536)} \approx 50.4\%$	Predicted 50% threshold
500	$1 - e^{-500^2/(2\cdot 65536)} \approx 88.1\%$	Nearly certain
1000	$1 - e^{-1000^2/(2\cdot 65536)} \approx 99.98\%$	Essentially guaranteed

Tracing the memory-based algorithm concretely: imagine hashing random 64-bit nonces with this toy 16-bit hash. After roughly 300 insertions into the lookup table, the very next randomly drawn nonce has, on average, about a 300/65536 ≈ 0.46% chance of colliding with each existing entry — summed over 300 existing entries this single new draw already carries close to a 1.4% marginal collision chance, and by draw 301 cumulative collision probability crosses the 50% mark exactly as the formula predicts. Scaling this reasoning to a real 128-bit hash ( $N = 2^{128}$ ) shows why 128-bit digests are considered broken for collision resistance even though $2^{128}$ sounds astronomically large: the birthday bound puts the actual attack cost at only $2^{64}$ operations, a number large clusters of GPUs can approach within years, not eons. This is precisely why SHA-256 (giving $2^{128}$ collision resistance) and SHA-3-256 replaced MD5 and SHA-1 in security-critical applications.

Common pitfalls & traps

Pitfall	Why it's wrong
Confusing preimage resistance with collision resistance	Preimage attacks cost $\Theta(2^n)$ ; collision attacks cost only $\Theta(2^{n/2})$ — mixing these up leads to underestimating collision risk by a huge margin
Assuming you need $N$ samples for "guaranteed" collision by pigeonhole	True for a guaranteed collision ( $N+1$ samples), but attackers only need a 50% (or any constant) probability, which needs far fewer, $\Theta(\sqrt N)$ , samples
Ignoring memory cost in naive implementations	Storing $2^{n/2}$ digests for large $n$ (e.g., $2^{80}$ for a 160-bit hash) is physically infeasible; real attacks use cycle-detection or distinguished-point methods with sublinear memory
Treating the $1.1774$ or $\sqrt{\pi/2}$ constant as exact for small $N$	The Taylor approximation $\ln(1-x)\approx -x$ degrades when $i$ is not $\ll N$ ; for very small digest spaces exact computation is needed
Believing collision resistance alone guarantees MAC security	MACs rely on different assumptions (unforgeability under chosen-message attack); birthday-style repeat-nonce or repeat-block attacks affect them independently of hash collision resistance
Underestimating parallel/distributed collision search	The $2^{n/2}$ work parallelizes near-perfectly across machines, so "resistant to a single machine" badly understates real-world attacker capability

Pioneers & history

The birthday paradox itself predates cryptography by decades, emerging from classical probability theory, but its cryptographic weaponization is tied to the formal study of hash function security in the late 20th century.

Origins · 1 minWhitfield Diffie and how this was discovered

Whitfield Diffie

born 1944 · Co-inventor of public-key cryptography; his and Martin Hellman's foundational 1976 paper spurred formal analysis of cryptographic primitives, including hash function security requirements

History

1939

— the birthday paradox's mathematical form is popularized in probability courses, though its combinatorial roots go back further.

1979

— Yuval and later cryptanalysts formalize the birthday attack against digital signature hash functions, showing collision attacks undercut naive digest-length choices.

1990

— Ralph Merkle and Ivan Damgård independently publish the Merkle–Damgård construction, standardizing iterative hash design and making collision-resistance analysis central to hash function security.

2004–2005

— Xiaoyu Wang and collaborators demonstrate practical collision attacks on MD5 and SHA-1, exploiting structural weaknesses that push effective attack cost well below the generic birthday bound.

2017

— Google and CWI Amsterdam announce the "SHAttered" attack, producing a real SHA-1 collision, cementing the shift toward 256-bit-and-larger hash functions industry-wide.

Where this matters

Digest length choice driven by the birthday bound underlies essentially every deployed cryptographic hash function. TLS certificate signatures moved from SHA-1 to SHA-256 specifically because SHA-1's 160-bit output offers only about $2^{80}$ collision resistance, now considered within reach of well-funded adversaries. Git, which uses SHA-1 for object addressing, has begun migrating toward SHA-256 for the same reason, since a birthday-style collision could in principle let an attacker substitute a malicious file with the same hash as a legitimate one. Blockchain systems relying on hash-based proof-of-work and Merkle trees explicitly reason about birthday bounds when choosing digest sizes to prevent forged transaction histories. Digital signature schemes (RSA-PSS, ECDSA) that hash-then-sign inherit collision resistance requirements directly from this bound, since an attacker who finds two messages with the same hash can get one signed and present it as a valid signature for the other. The same square-root scaling reappears in the birthday bound for nonce collisions in block cipher modes and, as foreshadowed for Message Authentication Codes, in bounding how many messages a single MAC key can safely authenticate before repeat-input collisions threaten forgeability — a direct descendant of the reasoning developed here for Collision Resistance.

Ask the tutor: How does the birthday bound translate into concrete data limits for a MAC key in schemes like HMAC or GCM?

Why is it called the "birthday paradox" if it's not actually a logical paradox?

It's a "paradox" in the informal sense of being wildly counterintuitive, not a logical contradiction. Most people guess you need close to 183 people (half of 365) before two share a birthday, reasoning naively about "half the possibilities." The real answer, 23, feels impossibly small. The mismatch arises because people intuitively think about matching a specific target (which does need ~183 people for 50% odds), rather than any pair matching each other, where the number of comparisons grows quadratically with group size. This distinction — target-matching versus any-pair-matching — is exactly the difference between preimage and collision attacks in cryptography.

Does the birthday bound mean SHA-256 only offers 128 bits of security overall?

No — it means SHA-256 offers 128 bits of collision resistance specifically, while still offering close to the full 256 bits of preimage resistance. These are different security properties measured against different attack goals. For applications only needing preimage resistance (like password hashing verification against a fixed target), SHA-256 remains extremely strong. For applications needing collision resistance (like digital signatures over arbitrary messages), the effective security level to plan around is 128 bits, which is why 256-bit-or-larger outputs are the modern standard.

Can a hash function ever beat the birthday bound for collision resistance?

No, not against a generic attacker treating it as a random oracle. The $2^{n/2}$ bound is an information-theoretic consequence of the pigeonhole principle combined with probabilistic sampling, not a limitation of any specific construction. Any function mapping to an $n$ -bit space, however cleverly designed, is subject to this bound when analyzed generically. What can happen is a hash function performing worse than the bound due to structural flaws (as with MD5 and SHA-1), but never provably better in the generic collision-finding model.

How does the birthday attack apply to digital signatures specifically?

In hash-then-sign schemes, a signer hashes a message and signs the digest, rather than signing the whole message directly, for efficiency. If an attacker can find two messages $m_1$ (innocuous) and $m_2$ (malicious) with $H(m_1) = H(m_2)$ , they can get the signer to sign $m_1$ and then present that same signature as valid for $m_2$ , since the signature only certifies the shared digest. The birthday bound tells signers exactly how large a digest they need so this collision-finding attack remains computationally infeasible, typically at least 256 bits for long-term security.

What is the connection between the birthday attack and time-memory tradeoffs like van Oorschot–Wiener parallel collision search?

The basic birthday attack needs $\Theta(2^{n/2})$ time and, if done naively, $\Theta(2^{n/2})$ memory to store all seen digests. Real-world attackers use "distinguished points" — flagging hash outputs meeting a simple pattern (e.g., leading zero bits) — to detect collisions across parallel machines using only sublinear memory per machine, while total work across the cluster stays $\Theta(2^{n/2})$ . This technique, formalized by van Oorschot and Wiener, is what made practical large-scale collision searches (like the SHA-1 SHAttered attack) computationally realistic rather than merely theoretical.

Does increasing digest length always proportionally increase security?

Roughly, yes, but the relationship is exponential, not linear — every additional bit of digest length doubles both the preimage-resistance cost ( $2^n$ ) and the collision-resistance cost ( $2^{n/2}$ ). Going from 128 to 256 bits doesn't just double security; it takes collision resistance from $2^{64}$ (weak, breakable) to $2^{128}$ (currently considered infeasible). The key design rule is simply to pick $n$ large enough that $2^{n/2}$ exceeds any plausible attacker's computational budget for the required security lifetime of the data.

Is the birthday attack relevant outside of hash functions?

Yes — the same square-root scaling shows up anywhere values are sampled uniformly at random and collisions matter: block cipher nonce reuse in modes like CTR or GCM, random session ID collisions, nonce reuse in ECDSA, nonce collisions in AEAD constructions, and even discrete-log algorithms like Pollard's rho, which explicitly reuses birthday-style cycle detection to solve the discrete logarithm problem in $O(\sqrt{p})$ steps. It's a fundamental combinatorial phenomenon that recurs throughout cryptography, not a quirk specific to hashing.