Birthday Attack — the square-root speedup that governs any collision search

Finding ANY collision in an n-bit function takes only ~2^(n/2) work, not 2^n — because among k random outputs the probability that two coincide crosses 50% near k ≈ 1.18 * 2^(n/2) (Wikipedia gives the sharper constant 1.1774). This is a distinct problem from preimage search (2^n work): you don't need a *specific* output, just *any two equal* outputs, and pairs grow quadratically with samples.

The signal that betrays it

- The challenge wants a collision, not a preimage — two different inputs with the same output, not "find x such that H(x) = target". - The digest/tag/nonce space is short: a 64-bit tag, a hash truncated to a handful of bytes, an 8-16 byte nonce/IV that's supposed to be random. - The challenge literally asks "how many messages/queries until two outputs match" — that phrasing is the birthday bound in disguise. - A custom or reduced primitive advertises an n-bit output but the REAL question is whether n is small enough that 2^(n/2) is a number you can actually spend (see feasibility check below).

How it's exploited

Feasibility check first — this is the single most useful triage step: compute 2^(n/2) for the actual output/tag width and see if it's a number a laptop or a rented GPU can reach. - 64-bit output → ~1.18·2^32 ≈ 5 billion candidate messages needed for a 50% collision chance (not the naive ~2^32 ≈ 4 billion — that undercounts by ~25-30%): doable in minutes to hours on commodity hardware. - 128-bit output → 2^64 is infeasible by brute collision search alone; you need extra structure (a differential path, a broken/truncated variant, a weak custom construction) — see Hash Collisions and Weak Preimages — truncated tags and broken functions that fall to brute force or known tooling.

Practical CTF form — dict-based collision search (simple, when you have memory to spare): ``python seen = {} while True: m = os.urandom(16) d = H(m) if d in seen: return seen[d], m # collision: (m_old, m_new) seen[d] = m `` This is the version to reach for first in a CTF: it's a few lines, and up to ~2^32-ish digests it just works on a normal machine.

Memory-light version — Floyd/Brent cycle detection (rho method), when storing every output would blow memory (e.g. very long search or you're pushed past 2^32-ish samples): treat H as a function iterated on itself (x_{i+1} = H(x_i)) and detect the cycle with tortoise-and-hare instead of a hash table of everything seen. This trades memory for a constant-factor slowdown, which matters once the dict itself becomes the bottleneck rather than the CPU work. Public sources tie this same rho idea to Pollard's rho for discrete logs — same cycle-detection trick, different problem.

Where the bound shows up beyond raw hash collisions

- Truncated MAC/hash tags: an n-bit tag makes blind forgery succeed with probability 2^-n per try, but if you're allowed *many* trials or you're hunting a collision between two tag values (not guessing one), it's the birthday bound — not the naive 2^-n — that governs cost. Feeds directly into MAC Forgery — the construction, not the primitive, decides the attack and HMAC Fundamentals — the nested MAC that tells you when to STOP trying length-extension reasoning about "is this tag length actually safe". - Random nonces/IVs: if a nonce is meant to be random and reused across enough messages, the birthday bound tells you when a repeat becomes likely — feeds Poly1305 Nonce Issues — nonce reuse turns a one-time MAC into a solvable polynomial (nonce reuse turns a one-time MAC into a solvable equation) and any "how many sessions until IV repeats" estimate. - Sponge constructions: security is set by the capacity c, not the full state width — if a custom sponge sets c small, collisions/preimages drop to ~2^(c/2), making a birthday attack feasible where you'd otherwise assume the full output width protects you. See Sponge Construction — why length-extension does NOT work on SHA-3/Keccak. - Multicollisions on cascaded/concatenated hashes: build a 2^(n/2)-way multicollision cheaply in one Merkle-Damgard hash (cost ~ (n/2)·2^(n/2) via chained single-block collisions), then birthday-search *inside that set* for a collision in a second hash — this is what actually breaks H1(m) || H2(m) concatenation schemes people assume are stronger than either hash alone. See Multicollision Attack — Joux's trick: 2^t colliding messages for the price of t single-block collisions. - Chosen-prefix collisions (MD5/SHA-1 rogue certs) use a birthday/near-collision phase to align two attacker-chosen prefixes' internal states before the differential blocks merge them — the birthday step is the alignment, not the final forgery. See Chosen-Prefix Collision — forcing two attacker-chosen, meaningfully different prefixes to hash equal.

What does NOT work

- Treating a collision search like a preimage search. If you compute "I need 2^n tries" for a collision target, you've mixed up the two problems — you need 2^(n/2), which can be the difference between infeasible and a coffee break. Always double check which one the challenge actually needs. - Assuming full output width = full security when a construction exposes only part of it. A sponge's capacity, a truncated tag, a hash-of-hash scheme — the *effective* n for the birthday bound is whatever the attacker-visible space actually is, not the nominal digest size. - Brute-force collision search past ~2^64ish without extra structure. At that scale storing/generating enough samples is impractical even with rho-style memory tricks; you need a real weakness in the primitive (differential path, reduced rounds, known collision tooling) rather than raw random search — that's the point where this page hands off to Hash Collisions and Weak Preimages — truncated tags and broken functions that fall to brute force or known tooling and Chosen-Prefix Collision — forcing two attacker-chosen, meaningfully different prefixes to hash equal. - Ignoring that pairs, not samples, drive the probability. The naive intuition ("half the space is ~50% likely to hit") is wrong by a large margin — it's the *quadratic* growth of possible pairs among k samples that gets you to 50% at ~1.18·2^(n/2), far earlier than 2^(n-1).

Related

Hash Collisions and Weak Preimages — truncated tags and broken functions that fall to brute force or known tooling Multicollision Attack — Joux's trick: 2^t colliding messages for the price of t single-block collisions Chosen-Prefix Collision — forcing two attacker-chosen, meaningfully different prefixes to hash equal MAC Forgery — the construction, not the primitive, decides the attack HMAC Fundamentals — the nested MAC that tells you when to STOP trying length-extension Poly1305 Nonce Issues — nonce reuse turns a one-time MAC into a solvable polynomial Sponge Construction — why length-extension does NOT work on SHA-3/Keccak