Collision Resistance and the Birthday Bound

A 256-bit hash returns a value that no adversary can invert by brute force, and yet a 256-bit hash gives only about 128 bits of collision resistance. Both statements are true, and the gap between them is the single most misunderstood fact about digest sizing. It is not an implementation weakness or a margin that careful engineering can recover. It is a consequence of how collisions are found, and it applies identically to a perfect hash function and to a broken one.

Three properties that are not interchangeable

Collision resistance asks that nobody can find two distinct messages with the same digest. Preimage resistance asks that nobody can, given a digest, find any message that produces it. Second-preimage resistance asks that nobody can, given a specific message, find a different message with the same digest. The middle and last look similar and behave very differently.

Preimage resistance holds at 2^n for a digest of n bits, because a generic search evaluates the function on candidates until one matches, and each evaluation succeeds with probability 2^-n. Second-preimage resistance also sits near 2^n for short messages, but degrades as messages grow, because the search can exploit the internal structure of the target, as the Kelsey-Schneier attack on long messages shows.

Collision resistance cannot exceed 2^(n/2), whatever the function is, because the attacker generates messages rather than guessing preimages. Sample q distinct inputs, keep their digests, and look for a repeat. Each pair collides with probability 2^-n, and there are about q^2/2 pairs, so the expected number of collisions is q^2 / 2^(n+1). Setting that to 1 gives q ≈ 2^(n/2). No structure is assumed and no weakness is exploited; this is the birthday bound, and it is a bound on the property, not on any particular algorithm.

The asymmetry is worth stating plainly: a 256-bit digest offers 256-bit preimage resistance and 128-bit collision resistance. A protocol that needs 128-bit security throughout can use SHA-256 for both purposes, but a protocol that needs 256-bit collision resistance needs a 512-bit digest. NIST’s guidance on digest sizing takes exactly this position, tying the minimum digest length for collision resistance to twice the target security strength.

What the arithmetic actually says

The approximation q ≈ 2^(n/2) is the point at which the collision probability reaches roughly one half, not the point at which collisions become possible. Collisions become likely far earlier in relative terms: at q = 2^(n/4) the expected number of collisions is 2^(-n/2 - 1), negligible, and the curve is steep between those scales.

import math

def samples_for_collision_probability(bits: int, p: float) -> float:
    """Number of draws from a 2**bits space to reach collision probability p."""
    space = 2 ** bits
    # exact form: q ~ sqrt(2 * space * ln(1 / (1 - p)))
    return math.sqrt(2 * space * math.log(1 / (1 - p)))

for bits in (128, 160, 256, 512):
    print(bits, f"{samples_for_collision_probability(bits, 0.5):.3e}")

The output is not a measurement of any hash; it is the generic bound evaluated, and it scales as sqrt(space). Doubling the digest width multiplies the collision cost by about 2.83, not by 2, since the exponent doubles and the square root halves it.

The same counting argument explains why truncation is a deliberate security decision rather than a formatting convenience. Taking the low 128 bits of a 256-bit digest gives 64-bit collision resistance, which is within reach of a determined attacker and well below any modern requirement. HMAC-SHA-256 truncated to 128 bits appears in protocols, and there it is chosen because the MAC security target is 128 bits for forgery, not because truncation is free.

Collisions between chosen prefixes

Ordinary collision resistance lets the attacker pick both messages, but only after the fact: they generate garbage until two pieces of garbage collide. Many real attacks need more. A chosen-prefix collision fixes two meaningful prefixes first, then appends computed suffixes so the two full messages collide. That is the shape of an attack on a certificate authority, where both messages must be valid certificate requests with attacker-chosen identities.

Chosen-prefix collision resistance is strictly stronger and substantially more expensive to achieve than plain collision resistance, so the birthday bound alone understates the requirement. The practical difference between MD5 and SHA-1 in the 2000s was largely about which of these two notions fell first: MD5 fell to ordinary collisions in 2004, and chosen-prefix collisions against it followed quickly, which is what made the rogue-certificate demonstrations possible. SHA-1 held ordinary collisions until 2017 and chosen-prefix collisions somewhat longer. The progression is covered in the SHA-1 collision work.

Where the generic bound does not hold

The birthday bound is a floor on attack cost only when the attacker has nothing but the digest. Three situations move the floor.

Structured inputs let the attacker skip work. If a protocol hashes messages whose first 64 bytes are constant, the attacker cannot vary them, and if the messages have a constrained format the effective input space shrinks. This does not break the bound so much as reduce the number of available candidates, and it is why protocols that hash attacker-influenced data with heavy structure need care about the size of the free portion.

Iterated constructions let one collision buy many. As Joux showed, a single compression-function collision in a Merkle-Damgård hash can be spliced, so k collisions produce 2^k colliding messages at k times the cost of one. The birthday bound describes the cost of the first collision and says nothing about how many messages come with it.

Memory, not time, is often the binding constraint. Storing 2^(n/2) digests is infeasible for any realistic n, which is why the naive table-based attack is not the one that matters. Pollard’s rho method and the parallel collision search of van Oorschot and Wiener find collisions in the same asymptotic time with negligible storage, by walking a deterministic function on the digest space and detecting cycles. Parallel versions scale almost linearly with the number of processors, because each walker can start from a distinct point and only the distinguished points need to be shared. The upshot for sizing is that the birthday bound is achievable in practice at whatever width the attacker can afford, so the margin has to come from the digest width rather than from the assumption that a huge table is required.

Quantum search changes both exponents, and the change is not uniform. Grover’s algorithm gives a quadratic speedup for unstructured search, so preimage resistance of an n-bit digest drops from 2^n to about 2^(n/2). Collision search gains a smaller factor: the best known generic quantum collision algorithms run in about 2^(n/3), so a 256-bit digest retains roughly 85 bits of collision resistance against a quantum adversary rather than 128. Digest sizes chosen for a post-quantum world are sized against the weaker of these figures, and the memory requirements of the quantum collision algorithms matter as much as the gate counts.

Choosing a width

The practical rule is that the digest width should be at least twice the security level the surrounding protocol claims, and the protocol’s own claims should be checked before the hash is blamed for them. A signature scheme built on a 256-bit hash cannot claim 256-bit collision resistance no matter how strong the signature arithmetic is, because the hash is the weak link and its bound is 128 bits.

Two digests with the same width are not interchangeable. SHA-256 and SHA3-256 both return 256 bits and both sit at the birthday bound, but they differ in preimage behaviour under long messages, in length-extension exposure, and in how much of their security depends on the compression function’s structure rather than on the iteration rule. Those differences are the subject of the rest of the cluster: the iteration rule for the SHA-2 family, and the sponge for SHA-3.