A cryptographic hash function takes input of any length and produces a fixed-length digest. Three properties are usually asked of it. Preimage resistance: given a digest, you cannot find an input that produces it. Second preimage resistance: given one input, you cannot find a different input with the same digest. Collision resistance: you cannot find any two inputs that produce the same digest.
The third is the weakest requirement, and it is the one that falls first. It is also the one people misread, because a collision is not an attack on a document that already exists. The attacker produces both halves.
The birthday bound sets the ceiling
For an n-bit digest, finding a collision by brute force takes about 2n/2 attempts rather than 2n, because you are looking for any matching pair rather than a match to a specific target. The reasoning is the same as the party-of-23 birthday problem. Twenty-three people is enough for a coincidence between any two of them, while matching your birthday specifically needs a much larger room.
That halving is why digest length is quoted at twice the security level anyone wants. A 128-bit digest gives 64 bits of collision resistance, which was already uncomfortable by the late 1990s and is trivially reachable now. This is the generic bound, achievable against any hash function whatsoever. A break means finding collisions faster than that.
Identical prefix and why it stayed academic
Wang and Yu published practical MD5 collisions in 2004. The output was two blocks of essentially random-looking bytes with the same digest. That form of result is an identical-prefix collision: both documents share whatever came before the colliding blocks, then differ, and the attacker controls very little about what the differing parts say.
To weaponise that, you need a file format that tolerates a chunk of unreadable bytes and lets its visible content depend on them. It can be done. It is fiddly, it constrains the attacker to formats with the right structure, and it always begins with the same shared prefix, which means the attacker has to author both documents from a common starting point.
Nobody is forging a signature on a contract that already exists with an identical-prefix collision. That is why MD5 remained in production for years after 2004. Practitioners could read the papers and correctly conclude that the demonstrated attack did not reach their deployment.
Chosen prefix is the one that matters
A chosen-prefix collision removes the shared-beginning constraint. The attacker starts with two arbitrary, different prefixes, then computes a pair of suffixes such that the two complete files hash to the same value. Now one document can be a legitimate certificate request for a domain you own, and the other can be a certificate authority certificate for a name you do not.
Stevens, Lenstra and de Weger published chosen-prefix MD5 collisions in 2007. In December 2008, a team including Stevens, Sotirov, Appelbaum, Lenstra, Molnar, Osvik and de Weger demonstrated the consequence: they obtained a legitimate certificate from a CA still signing with MD5, and produced a colliding intermediate CA certificate carrying the same signature. The computation ran on a cluster of roughly 200 PlayStation 3 consoles. The result was a certificate authority whose signature browsers would accept, created by someone who was not a certificate authority.
Four years later the same primitive turned up in the wild. The Flame malware, found in 2012, carried a forged Microsoft code-signing certificate produced with a chosen-prefix MD5 collision against a Terminal Server licensing certificate. That let it present itself as a Windows Update package. Whoever built it had done cryptanalytic work that had not appeared in public.
Identical prefix: the attacker writes two documents from a common start and can produce a pair that collide. Chosen prefix: the attacker starts from two documents that are already different and makes them collide. The first is a curiosity in most deployments. The second forges credentials.
SHA-1 followed the same arc, ten years later
Theoretical attacks on SHA-1 appeared in 2005, well below the 280 generic bound. Migration advice followed, and NIST deprecated SHA-1 for digital signature generation after 2013. Deployment moved slowly, as it does.
In February 2017, CWI Amsterdam and Google published SHAttered, the first practical identical-prefix SHA-1 collision: two PDF files with different visible content and the same digest. The published cost was roughly 263.1 SHA-1 computations, which the authors described as around 6,500 CPU-years and 110 GPU-years of work.
In January 2020, Leurent and Peyrin published the chosen-prefix version, under the name SHAmbles, at an estimated rental cost in the region of 45,000 US dollars. They demonstrated it against the PGP web of trust, constructing a case where a certification signature made over one identity appeared valid over another. That is the same shape as the 2008 certificate result, in a different trust system, at a price any moderately funded adversary can pay.
| Function | Digest | Collision status |
|---|---|---|
| MD5 | 128-bit | Chosen-prefix collisions in seconds on a laptop |
| SHA-1 | 160-bit | Chosen-prefix collisions at rentable cost |
| SHA-256 | 256-bit | No practical attack; length-extension applies |
| SHA-3 | 256-bit and up | No practical attack; sponge construction, no length extension |
| BLAKE3 | 256-bit default | No practical attack; tree mode, no length extension |
Where SHA-1 still lives, and why some of it is fine
Git identifies every object by SHA-1. Two colliding objects would be indistinguishable to the repository, which is a real integrity concern for signed commits and for supply-chain provenance generally. The response after SHAttered was to adopt a hardened variant, developed by Stevens and Shumow, which detects the structural signature of a collision attempt during hashing and refuses. A SHA-256 object format exists and adoption has been slow, for the compatibility reasons that make any identifier change slow.
Elsewhere, SHA-1 appears in constructions where collision resistance is not the property being relied on. HMAC-SHA-1 is the clearest case: HMAC's security argument does not require the underlying hash to be collision resistant, which is why HMAC-SHA-1 has not fallen alongside SHA-1 signatures, and why the default algorithm in TOTP authenticator apps remains sound. The same reasoning applies to several key-derivation uses.
"This hash is broken" and "this use of the hash is broken" are different claims. Which property the construction depends on decides which one applies.
That nuance is not a licence to keep it. New designs should not reach for SHA-1 anywhere, if only because auditors, scanners and procurement teams cannot evaluate the distinction at scale, and because NIST has set an end date: SHA-1 is to be phased out of federal use by the end of 2030.
What this history suggests about the next migration
The pattern is consistent across both functions. Theory arrives first and is correctly judged non-urgent. The identical-prefix demonstration arrives and is correctly judged to be a narrow threat. The chosen-prefix demonstration arrives and everything is suddenly urgent, at which point the migration takes years because identifiers are embedded in formats, protocols and databases that were never designed to change them.
The functions we now depend on will follow some version of that curve. This is the argument for cryptographic agility: a system that names its algorithms explicitly, versions its formats, and can accept a second algorithm alongside the first is one that migrates in a release cycle rather than a decade. Systems that hardcode digest lengths into wire formats and storage schemas are the ones still running SHA-1 in 2030.
The same reasoning drives the current post-quantum migration, where the warning arrived well before the capability. Whether an organisation uses that lead time is a design decision made long before the attack is announced.