Hash Collision Resistance (Birthday Bound)

This is the birthday relation solved for the one case everybody quotes: the number of messages at which a collision becomes as likely as not. Set $p = 1/2$ in $p \approx 1 - e^{-n^2/(2N)}$, take logs, and $n = \sqrt{2N\ln 2}$. With $N = 2^b$ that is $\sqrt{2\ln 2}\cdot 2^{b/2} = 1.1774 \cdot 2^{b/2}$. The constant is real but rarely quoted, because at these scales a factor of 1.18 is noise beside a factor of $2^{b/2}$; NIST SP 800-107 Rev. 1 simply states that a hash function with a $b$-bit output provides $b/2$ bits of collision resistance.

Collision resistance is half the digest length, and preimage resistance is all of it. Those are three different security properties and they cost different amounts to break. Preimage: given a digest, find a message that produces it — about $2^b$ work. Second preimage: given a message, find a different one with the same digest — also about $2^b$. Collision: find any two messages that agree — about $2^{b/2}$, because the attacker gets to choose both sides and the birthday effect applies. So SHA-256 offers 256 bits against preimages and 128 against collisions, and both numbers are correct answers to different questions.

Which one governs depends entirely on whether an adversary controls both messages. A signature over a document, a certificate fingerprint, a Git commit identifier, or a deduplication key where an attacker can submit content — all of those need collision resistance, so the $b/2$ figure is the one that matters. An HMAC tag or a password verifier, where the attacker cannot choose the other side, is governed by preimage resistance and can safely be shorter. Getting this backwards is how a digest ends up half the size it needed to be.

The bound assumes the hash has no structural weakness, and history is not kind to that assumption. MD5's birthday bound is $2^{64}$; practical collisions were demonstrated in 2004 at a cost closer to $2^{24}$, and today a laptop finds them in seconds. SHA-1's bound is $2^{80}$; the SHAttered collision of 2017 cost about $2^{63}$, and the chosen-prefix collision of 2019 brought it within reach of a modest budget. In both cases the failure was cryptanalytic — a flaw in the compression function — and no arithmetic on this page could have predicted it. The birthday bound is a ceiling on a hash's collision resistance, never a floor. Treat it as the best a function could possibly do and watch the literature for whether it still does.

Practical guidance is short. For anything requiring collision resistance, use SHA-256 or better, which gives 128 bits — the level NIST SP 800-57 Part 1 Rev. 5 treats as the ordinary modern choice. Use SHA-384 or SHA-512 where 192 or 256 bits are wanted, or where a long-lived signature has to survive Grover's algorithm halving the preimage figure. Do not use MD5 or SHA-1 for anything where an adversary chooses the input, and note that both remain acceptable inside HMAC, where the construction does not depend on collision resistance — a distinction worth knowing before deleting them from a legacy codebase.