Collision Resistance

A hash function `H` maps arbitrary-length inputs to fixed-length `n`-bit outputs. Collision resistance demands that it be computationally infeasible to find a collision: a pair of distinct inputs `x ≠ x'` such that `H(x) = H(x')`. Note the existential phrasing — collisions always exist by the pigeonhole principle, since the input space is larger than the output space. Collision resistance is not about non-existence; it is about unfindability by any efficient algorithm. Formally, collision resistance is defined relative to a family of keyed hash functions `{H_s}` indexed by a public key or seed `s`, not a single fixed function. This is a subtle but essential point: for any single fixed function `H`, there trivially exists an algorithm that outputs a hard-coded collision (some fixed pair `x, x'`) — that algorithm is not efficient to construct, but as an algorithm it runs in constant time and always succeeds. Since we quantify over all efficient adversaries, a fixed function can never be proven collision resistant in the asymptotic sense. Using a keyed family sidesteps this: the adversary must succeed for a randomly chosen key it does not get to hard-code against in advance. In practice, deployed hash functions like SHA-256 are unkeyed, and we treat them as a fixed representative instance drawn from this idealized family, with collision resistance understood as a computational conjecture rather than a proven theorem. Collision resistance sits at the top of a hierarchy of hash security properties. Preimage resistance says that given `y = H(x)`, it is hard to find any `x'` with `H(x') = y`. Second-preimage resistance says that given a specific `x`, it is hard to find a different `x' ≠ x` with `H(x') = H(x)`. Collision resistance is strictly stronger: it lets the adversary choose both inputs, giving it far more freedom. A standard reduction shows collision resistance implies second-preimage resistance (contrapositive: any second-preimage finder yields a collision finder by fixing `x` and calling it). The converse fails in general — a function can resist second-preimage attacks against an honestly chosen `x` while still admitting collisions between two adversarially chosen inputs.

There is no "algorithm" that achieves collision resistance the way there is an algorithm for sorting — collision resistance is a security property that a hash construction either has or lacks, verified by trying to break it. What we can specify precisely are (1) the security game that defines the property, and (2) the best generic attack strategy any adversary can mount against any hash function, which sets the baseline every real construction must meet or exceed.

The collision-resistance game, played between a challenger and an adversary `A`: ``` Game Collision-Resistance(H, A, n): // H is a hash function family with n-bit output, A is a PPT algorithm s <- sample a key/seed for H // challenger picks the instance (x, x') <- A(s) // adversary outputs a candidate pair if x != x' and H_s(x) = H_s(x'): return WIN // adversary found a genuine collision else: return LOSE H is collision resistant if, for every probabilistic polynomial-time adversary A, Pr[ A wins Collision-Resistance(H, A, n) ] is negligible in n. ``` An adversary that has no strategy better than guessing is bounded by the generic birthday attack, which treats `H` as a random function (a black box, ignoring any internal structure): ``` Algorithm GenericBirthdayCollisionFinder(H, n): // H: n-bit hash function treated as a random oracle table <- empty hash map from digest -> input loop: x <- sample a fresh random input y <- H(x) if y is a key in table and table[y] != x: return (table[y], x) // FOUND a collision else: table[y] <- x // remember this input for future comparison ``` This is the algorithmic core previewed in The Birthday Attack: because each new sample is compared against all previous samples (via the table), the number of pairs being implicitly checked grows quadratically with the number of samples, not linearly. That quadratic growth is what makes `2^(n/2)` — not `2^n` — the right threshold, and it is the single most important quantitative fact in this article.

Generic attack cost. Model `H` as a random function mapping into a set of size `N = 2^n`. By the birthday-paradox argument, if we draw `k` independent samples uniformly from a set of size `N`, the expected number of pairs among them is `C(k,2) ≈ k²/2`. Each pair collides with probability `1/N`. So the expected number of colliding pairs is approximately ``` E[collisions] ≈ (k² / 2) · (1 / N) ``` Setting this to `1` (the threshold where a collision is expected) gives ``` k ≈ sqrt(2N) = sqrt(2) · 2^(n/2) ``` So roughly `2^(n/2)` hash evaluations suffice to find a collision with good probability, against any hash function that behaves like a random function — this is the birthday bound. For SHA-256 (`n = 256`), that is about `2^128` operations: astronomically infeasible with current or foreseeable computing. For MD5 (`n = 128` nominal, but structurally far weaker than the generic bound), dedicated cryptanalysis finds collisions in seconds on a laptop, meaning MD5's actual security is nowhere near its `2^64` generic bound.

Time and space of the generic algorithm. The naive `GenericBirthdayCollisionFinder` above stores every sample in a hash table for `O(1)` expected lookup, so it runs in expected time `O(2^(n/2))` and — critically — space `O(2^(n/2))` as well, since it must remember every digest seen. This space cost is often the real bottleneck. A well-known refinement, Floyd's cycle-detection (used in Pollard's rho-style collision search), finds a collision in the same `O(2^(n/2))` expected time but only `O(1)` space, by iterating a pseudo-random function and detecting a cycle with a tortoise-and-hare pointer scheme rather than storing history. This is why collision-resistance claims are always stated with time as the binding constraint — attackers with enough storage were never the real barrier, and modern rho-style methods remove even that requirement.

Correctness of the birthday-bound reasoning. The argument only shows that a collision becomes likely; it does not construct a specific collision certificate independent of running the search. The reduction, however, is airtight: if `H` truly behaves as an idealized random function, no algorithm — generic or not — can do fundamentally better than this pair-counting argument, because the adversary's only leverage against a black-box random function is querying it and comparing outputs, and every query only ever creates new pairs at the same quadratic rate. This gives a matching lower bound for black-box (oracle) hash functions: `Ω(2^(n/2))` queries are also necessary in the random-oracle model, so `Θ(2^(n/2))` is tight for generic attacks.

Where the guarantee can fail. Real hash functions are not literal random functions; they are concrete algorithms (Merkle–Damgård constructions, sponge constructions) built from compression functions. If that internal structure has exploitable algebraic weaknesses — as with MD5's differential paths or SHA-1's near-collision chains — an attacker can beat the `2^(n/2)` generic bound by a wide margin using structural cryptanalysis, not brute force. Collision resistance is therefore always a conjecture backed by cryptanalytic effort, not a theorem; confidence grows only from years of public scrutiny finding no shortcut.

Let's trace both the abstract birthday-bound calculation and a stripped-down concrete simulation over a tiny toy hash, to make the mechanics unmistakable.

Part 1 — scaling the birthday bound across real digest sizes.

The SHA-1 row is the pedagogically important one: the generic bound said `2^80`, but a real attack succeeded around `2^63.1` — about `2^17` (~130,000×) cheaper than genericity would predict, because differential cryptanalysis exploited SHA-1's internal round structure. This is the concrete difference between generic security and actual security.

Part 2 — a fully worked toy simulation with a 6-bit hash. Take a deliberately tiny toy: `H(x) = (x² + 5x + 3) mod 64`, mapping any integer input to a 6-bit output (`N = 64`). This is not cryptographically meaningful — it is small enough to search exhaustively so we can see the birthday bound land exactly where predicted. By the birthday formula, we expect a collision after about `sqrt(2 · 64) ≈ 11.3` samples. Let's sample `x = 0, 1, 2, …` in order and hash each:

At `x = 15`: `15² + 5·15 + 3 = 225 + 75 + 3 = 303`, and `303 mod 64 = 47`... let's recompute carefully to keep the arithmetic honest. `303 / 64 = 4` remainder `47`, so `H(15) = 47`, not `45` — recheck `x=13`: `169 + 65 + 3 = 237`, `237 mod 64 = 237 - 192 = 45`. So `H(13)=45`, and `H(15)=47` do not collide; continuing the search:

A genuine collision: `H(29) = H(30) = 29`, with `29 ≠ 30`. It took `31` samples (`x = 0..30`) rather than the predicted `~11`, which is expected — the birthday formula gives an expected order of magnitude, not a guaranteed exact count, and this particular quadratic hash is not perfectly uniform, so its actual collision rate deviates somewhat from the ideal random-function model. The qualitative lesson holds exactly as claimed: collisions in a `64`-slot space showed up after a few dozen trials, not after anywhere near `64` trials, precisely because comparisons scale quadratically in the number of samples.

The theoretical study of hash-function security properties, including the formal separation between preimage, second-preimage, and collision resistance, matured through the work of cryptographers formalizing provable security in the 1970s–1990s, alongside the practical construction efforts that produced MD4, MD5, SHA-1, and eventually the SHA-2/SHA-3 families under public NIST competitions.

Digital signature schemes — RSA-PSS, ECDSA, EdDSA — all sign a hash of the message rather than the message itself, an approach called hash-and-sign. This is precisely why Digital Signatures and their security proofs assume the underlying hash is collision resistant: without it, an attacker crafts two messages with identical hashes, gets the victim to sign the innocuous one, and then presents the malicious one bearing an equally "valid" signature. Certificate authorities in the TLS/HTTPS ecosystem, code-signing infrastructure, and PDF-signing standards have all had to migrate away from MD5 and SHA-1 for exactly this reason, following demonstrated collision attacks that let attackers forge look-alike certificates. Beyond signatures, collision resistance underpins content-addressed storage: Git identifies every commit and file blob by its SHA-1 (now transitioning to SHA-256) hash, and a collision would let an attacker silently substitute malicious file content for legitimate content sharing the same identifier. Blockchain systems chain blocks together via hash pointers, relying on collision resistance to make history immutable in practice. Message Authentication Codes use hash functions as building blocks (e.g., HMAC) and rely on related but distinct properties, illustrating that collision resistance, while central, is one member of a broader toolkit of hash-based guarantees rather than a universal cure-all.

Ask the tutor: How does the Merkle–Damgård proof actually reduce full-hash collision resistance to compression-function collision resistance, step by step?