Two Files, One Fingerprint: Chosen-Prefix Collisions and How Hash Functions Really Break

The Hook: The Signature That Fits the Wrong Document

On December 30, 2008, a group of seven researchers stood on stage at the 25th Chaos Communication Congress in Berlin and displayed a certificate. It was not a stolen certificate, not one pulled from a compromised database, and nobody had captured a private key. It was a perfectly legitimately signed certificate from a real, then globally trusted certificate authority — with one difference: it allowed its holder to issue arbitrary further certificates. For any domain. For any bank. For any service on the internet.

The certificate authority had never intended to do that. It had signed something entirely harmless: an ordinary server certificate for an unremarkable test domain, paid for by credit card, total project cost 657 US dollars. It was simply that what it signed had the same MD5 hash as the certificate the researchers actually wanted. And a digital signature does not sign the document. It signs the document's hash.

That is the core of this article, and it is an insight still routinely missed in practice. Every digital signature, every software attestation, every Git commit, every integrity check rests on a silent assumption: that two different things cannot have the same fingerprint. That assumption is not a mathematical certainty. It is a computational assumption — a claim about how expensive it is to find a counterexample. And the price of that counterexample falls, year after year, with every publication and every generation of graphics cards.

What makes this article worthwhile is not the news that "MD5 is broken" — that is two decades old. It is the question underneath: what exactly breaks when a hash function breaks? Because between "somebody found two random files with the same hash" and "somebody can forge an arbitrary document" lie several attack classes with entirely different consequences. Anyone who cannot distinguish them will get the risk assessment wrong in every migration decision — in both directions.

Part 1: What a Hash Function Promises — and Which Part Matters

Three Properties, Three Degrees of Difficulty

A cryptographic hash function H takes an input of arbitrary length and produces a fixed-length output — 128 bits for MD5, 160 bits for SHA-1, 256 bits for SHA-256. Three properties are expected of it, and keeping them apart is essential, because they differ in how hard they are to break and in which attacks they enable.

Preimage resistance (the one-way property): given a hash value h, it is practically impossible to find any input m with H(m) = h. This is the property that protects password hashes.

Second-preimage resistance: given a message m₁, it is practically impossible to find a different message m₂ ≠ m₁ with the same hash. This is the property you need when somebody else's already existing document is to be forged.

Collision resistance: it is practically impossible to find any pair (m₁, m₂) with m₁ ≠ m₂ and H(m₁) = H(m₂). Here the attacker may choose both messages freely — and that is precisely what makes this the weakest of the three.

The practically most important point in this section is this: all known practical attacks on MD5 and SHA-1 break collision resistance only. Neither MD5 nor SHA-1 is preimage-broken. Nobody can reconstruct a matching document from a given MD5 hash, and nobody can produce a second, divergent document with the same hash for an already existing contract. That sounds reassuring and is partly reassuring — it is why old MD5 signatures that predate the attacks are not retroactively forgeable. But it is simultaneously irrelevant to what attackers actually do: they create both documents themselves, have the harmless one signed, and swap it for the dangerous one.

The Birthday Bound: Why Half the Output Length Is What Counts

Collision resistance has a fundamental, insurmountable ceiling. With an n-bit output there are 2ⁿ possible hash values. One might naively expect roughly 2ⁿ attempts to be needed to find a collision. That is wrong — by a square root.

The birthday paradox gives the correct bound: draw about 2^(n/2) random values and the probability that two of them coincide already exceeds 50 percent. The reason is that the number of pairs in a set of k elements grows quadratically with k — with k values there are k(k−1)/2 pairs, and each one has a 2⁻ⁿ chance of being a collision.

For MD5 this means collision resistance was never designed for more than 2⁶⁴ operations, not 2¹²⁸. For SHA-1: 2⁸⁰, not 2¹⁶⁰. These numbers are not weaknesses of the construction; they are the ceiling the output length sets. Any attack that stays under that ceiling is a genuine cryptanalytic achievement; any attack that merely reaches it is brute force with a lot of hardware.

From this follows the single most important design rule: security against collisions is half of what the output length suggests. A 256-bit hash function offers 128 bits of collision security. Anyone who picks a 128-bit output because "128 bits is surely secure" has in truth picked 64 bits of collision security — and that has been within weekend reach of a data center for years.

Merkle–Damgård: The Construction That Makes Collisions Extensible

MD5, SHA-1 and the entire SHA-2 family share an internal structure, the Merkle–Damgård construction. The message is split into fixed-length blocks (512 bits for MD5 and SHA-1). There is an internal state, initialized to a fixed initial value (IV). Then a compression function is applied block by block: it takes the current state and the next message block and produces the new state. At the end, the state is the hash value.

This construction has a property that decides everything for our topic. Suppose there are two different messages m₁ and m₂ that, once processed, produce the same internal state. Then for any suffix s:

H(m₁ ‖ s) = H(m₂ ‖ s)

Because once the state is identical, the function processes the suffix identically in both cases and can no longer distinguish the prior history. A collision is therefore not a point event but a junction: two paths that merge and can afterward be continued together arbitrarily.

This is the mechanism behind essentially all real-world collision attacks. One does not find two complete, finished documents with the same hash. One finds two short, differing collision blocks — usually a few hundred bytes of binary noise — and appends the same arbitrarily long remainder to both. That is why the two PDFs in the 2017 SHAttered attack looked different yet shared a SHA-1 value: the difference sat in a handful of blocks controlling a JPEG object inside the PDF structure.

The second, related weakness of the same construction is length extension: anyone who knows H(m) and the length of m can, without knowing m, compute H(m ‖ padding ‖ s) for a self-chosen s — precisely because the hash value is the internal state. MD5, SHA-1 and SHA-256 are all affected; this is exactly why a naive H(secret ‖ message) is wrong as a message authentication code and HMAC is the right answer. SHA-3 (Keccak, standardized as FIPS 202 in 2015) uses a sponge construction instead and is not length-extendable; neither is SHA-512/256, the truncated variant.

Part 2: The Taxonomy of Breaking — Four Attack Classes

Here lies the real insight, and here practice conflates things most. "The hash function is broken" is not a binary statement. There is a ladder of attack classes that become exponentially more expensive and simultaneously exponentially more useful.

Identical-Prefix Collision

The attacker picks one common prefix P — or accepts an empty one — and then finds two different continuations C₁ ≠ C₂ such that H(P ‖ C₁) = H(P ‖ C₂). Both documents necessarily begin identically.

That suffices for spectacular demonstrations: two PDFs showing different content, two PostScript files, two programs with different behavior. The trick is always the same: you build a file format so that the common prefix contains a switch whose value lies in the collision blocks, and you place both variants of the content in the common suffix. The format then decides which variant is displayed.

For attacks on certificates or on documents signed by others it is not enough. There, the attacker does not determine the start of the document — the certificate authority or the format does.

Chosen-Prefix Collision — The Real Lever

Here it gets serious. The attacker specifies two different, freely chosen prefixes P₁ and P₂ and finds collision blocks C₁, C₂ with:

H(P₁ ‖ C₁) = H(P₂ ‖ C₂)

The difference is qualitative, not quantitative. Now the attacker may fill both beginnings with arbitrary content — say, two entirely different certificate field sets, two different PGP identities, two different file headers. After that everything merges and stays identical forever. That is precisely what turns a signed statement about one document into a valid signature for the other.

The 2008 Rogue CA demonstration and the 2012 Flame attack both rest on this. And it explains why the field reacted considerably more nervously to SHA-1 is a Shambles in January 2020 than to SHAttered in 2017: not because SHA-1 had become "even more broken," but because only the chosen-prefix variant turns a curiosity into a tool.

Freestart Collision — The Early Warning Signal

An intermediate step that enables practically nothing but says a great deal analytically: the attacker may choose not only the message blocks but also the internal initial state, which the real algorithm fixes. This is an attack on the compression function, not on the hash function. It produces no colliding files. But it shows that the differential paths work, and it allows a defensible cost estimate for the real attack. The SHAppening publication by Stevens, Karpman and Peyrin in October 2015 was exactly that — and it is why browser vendors pulled forward their SHA-1 deprecation schedules.

Second Preimage — The Rung That Has Not Fallen

Finding a second document with the same hash for a given, foreign document. For MD5 and SHA-1 this remains practically out of reach; the known attacks do not deliver it. This limit is why statements like "every MD5-signed document is forgeable" are false. What is true is: every document an attacker was allowed to help shape before it was signed is compromisable.

The Attack Classes at a Glance

The table contains the actual instruction for any risk assessment. The question is never "is MD5 or SHA-1 in use," but: may an attacker help shape any part of the data before it is hashed and signed? If the answer is yes, the usage is untenable. If it is no — say, a checksum over a file produced entirely under your own control, whose hash you compare against a reference you created yourself — the risk is considerably lower than the headlines suggest. It simply does not disappear, because history points in one clear direction.

Part 3: MD5 — The Chronicle of a Death Foretold

1993 to 1996: The Warnings Nobody Wanted to Hear

MD5 was specified in 1992 by Ronald Rivest (RFC 1321) and within a few years was the internet's default hash function. The first cracks appeared early. Bert den Boer and Antoon Bosselaers found a pseudo-collision in 1993 — a collision of the compression function under two different start states. In 1996 Hans Dobbertin published a collision for the compression function itself: a freestart collision in the terminology above.

The field's reaction was the right one: Dobbertin's result was treated as a clear warning, and MD5 was no longer recommended for new designs. Practice reacted as usual: MD5 stayed everywhere, because nothing you could point at was broken. Between "cryptographers consider it no longer defensible" and "there is a colliding file you can show people" lay eight years. In those eight years MD5 was built into tens of thousands of products, protocols and database schemas.

2004/2005: Wang and Yu

At CRYPTO 2004 Xiaoyun Wang announced a real MD5 collision; the worked-out method appeared in 2005 as How to Break MD5 and Other Hash Functions by Xiaoyun Wang and Hongbo Yu at EUROCRYPT 2005 (LNCS 3494, pp. 19–35, DOI 10.1007/11426639_2). The paper describes a differential cryptanalysis with hand-constructed difference paths and states the computational effort not as an operation count but simply as time: about 15 minutes to one hour on the hardware of the day.

That was the moment MD5 ended as a collision-resistant function. Not in practice — in practice it took years more — but as a defensible assumption.

2007 to 2008: From Collision to Rogue CA

The decisive advance was not faster but structural. Marc Stevens, Arjen Lenstra and Benne de Weger showed in 2007 how to construct chosen-prefix collisions for MD5 and thereby produce colliding X.509 certificates for different identities. Only this step turns a laboratory result into an attack on a trust infrastructure.

The demonstration followed in December 2008. Alexander Sotirov, Marc Stevens, Jacob Appelbaum, Arjen Lenstra, David Molnar, Dag Arne Osvik and Benne de Weger requested an ordinary server certificate from RapidSSL — a Verisign brand that still signed with MD5 at the time. The request was constructed so that the to-be-signed portion of the real certificate collided with that of a second CA certificate they had built. The real CA's signature could then be copied onto the rogue certificate and remained valid.

What makes this attack instructive is not the cryptography but everything alongside it. A chosen-prefix attack requires predictability: the attacker must know the exact content the CA will sign before computing the collision. That included two fields nobody normally treats as security parameters:

• The serial number. RapidSSL counted sequentially. The researchers treated this as a remote counter, analyzed 9,251 certificates, found that typically 800 to 1,000 certificates were issued from Thursday night to Sunday night, and purchased certificates deliberately to push the counter just below the target value.
• The validity period. RapidSSL issued certificates exactly six seconds after purchase confirmation. Clicking six seconds before the desired start time produced exactly the predicted timestamp.

The computation ran on a cluster of more than 200 PlayStation 3 consoles in the "PlayStation Lab" at EPFL in Lausanne. The birthdaying phase took about 18 hours and around 30 GB of memory distributed across the consoles; the second phase ran on a quad-core PC in three to ten hours. Three attempts failed on timing prediction; the fourth succeeded. Because a certificate could be reissued free of charge up to twenty times, total costs stayed at 657 US dollars. The work received the best-paper award at CRYPTO 2009. The rogue CA certificate was deliberately backdated to 2004 and thus expired before anyone could abuse it.

I am of the opinion that this attack remains the most instructive example of the limits of threat modeling: the vulnerability was not MD5 alone, but MD5 in combination with a predictable serial number and a predictable timestamp. Each of those three details was considered uncritical on its own. There is no proof for this assessment, but the three factors are cleanly documented in the publication.

2012: Flame — When Somebody Meant It

Everything described so far was research with advance notice. In 2012 a forged Microsoft certificate was found in the Flame malware, usable to distribute malicious code via Windows Update — an attack on one of the most sensitive signature paths in existence.

Marc Stevens analyzed the certificate with a technique he called counter-cryptanalysis: you examine a message for the traces a collision attack unavoidably leaves behind. The result was remarkable: the certificate had been produced by a chosen-prefix collision — but by a variant that had not been published in the literature at that point. A reconstruction in Max Fillinger's master's thesis (ILLC/CWI, 2013, supervised by Marc Stevens and Christian Schaffner) estimated the attack's expected cost at at least 2⁴⁶·⁶ calls to the MD5 compression function.

The lesson is uncomfortable and rarely stated this plainly: at the time of Flame, a practically usable chosen-prefix method existed that public research did not know about. Published attack costs are therefore an upper bound on what attackers can do, never a lower bound. Anyone who aligns migration planning with the latest conference publication is systematically planning too late.

Part 4: SHA-1 — The Same Film, in Slow Motion

SHA-1 was standardized in 1995 (FIPS 180-1), 160-bit output, birthday bound 2⁸⁰. The story of its breaking is the same as MD5's, only stretched over twenty years — which makes it unusually well documented.

2005 — the theory. Xiaoyun Wang, Yiqun Lisa Yin and Hongbo Yu published Finding Collisions in the Full SHA-1 at CRYPTO 2005 (LNCS 3621, pp. 17–36, DOI 10.1007/11535218_2): an attack in fewer than 2⁶⁹ hash operations, the first below the 2⁸⁰ bound for the complete 80-step SHA-1. Theoretically broken, practically out of reach. NIST issued its deprecation in 2011.

2015 — SHAppening. Stevens, Karpman and Peyrin demonstrated a freestart collision; Git's documentation puts this attack at 2⁵⁷ operations. No files, but a defensible extrapolation — and the realization that the cost of a real attack was lower than generally assumed. The certificate ecosystems consequently pulled forward their SHA-1 sunset deadlines.

2017 — SHAttered. Marc Stevens, Elie Bursztein, Pierre Karpman, Ange Albertini and Yarik Markov presented The first collision for full SHA-1 (CRYPTO 2017; ePrint 2017/190): two differently rendering PDF files with identical SHA-1 values. Effort: roughly 2⁶³·¹ compression-function calls, corresponding to about 6,500 CPU years and 100 GPU years — by the authors' account more than 100,000 times faster than brute force. It was an identical-prefix collision; the chosen-prefix variant was still missing.

2019 — the bridge. Gaëtan Leurent and Thomas Peyrin showed at EUROCRYPT 2019, in From Collisions to Chosen-Prefix Collisions – Application to Full SHA-1, how to get from an ordinary collision to a chosen-prefix collision: effort between 2⁶⁶·⁹ and 2⁶⁹·⁴ depending on assumptions about the cost of the near-collision blocks, against a previous best known 2⁷⁷·¹. The authors closed with the recommendation to abandon SHA-1 as quickly as possible.

2020 — Shambles. The same authors implemented the attack and published SHA-1 is a Shambles: First Chosen-Prefix Collision on SHA-1 and Application to the PGP Web of Trust at the 29th USENIX Security Symposium (pp. 1839–1856). Measured in SHA-1 equivalents on an Nvidia GTX 970, the cost of an identical-prefix collision fell from about 2⁶⁴·⁷ to 2⁶¹·², and that of a chosen-prefix collision from about 2⁶⁷·¹ to 2⁶³·⁴. With rented GPU capacity this corresponded to roughly USD 11,000 for a collision and roughly USD 45,000 for a chosen-prefix collision. The attack as actually carried out ran for two months on 900 Nvidia GTX 1060 cards.

The application struck the PGP web of trust. The authors created two PGP keys with different identities whose SHA-1 certificates collided: a certification of the first key could be transferred to the second — a working identity forgery inside the web of trust. The legacy GnuPG branch still used SHA-1 by default for identity certifications; after notification, the modern branch rejects SHA-1 signatures. The issue was tracked as CVE-2019-14855.

The Collapse in Cost, in One Table

Fifteen years in which an attack fell from "theoretically conceivable" to "the price of a mid-range car." And the curve is not dominated by new mathematics; half of it is hardware getting cheaper with no contribution from cryptanalysis at all. Any hash function whose collision security sits at 64 bits today is therefore finished for the foreseeable future — regardless of whether anyone keeps researching it.

Part 5: Why "Deprecated" Does Not Mean "Removed"

Between the cryptographic verdict and an algorithm's actual disappearance, practice routinely puts fifteen to thirty years. For MD5 the clock started in 1996 and is still running; for SHA-1 in 2005, and NIST has set December 31, 2030 as the end date for its own use (announcement of December 15, 2022). By then FIPS 180-5 is to be published, removing the SHA-1 specification, SP 800-131A and further publications are to be revised, and a transition strategy for the CMVP and CAVP validation programs is to be released.

The reasons for this stickiness are structural, not negligent:

Hash values are identifiers, not just checksums. In Git the SHA-1 hash is an object's name. Changing the algorithm there is not a configuration switch but a renaming of the entire history. The same holds for deduplication keys in storage systems, for cache keys, and for every database column where a hash serves as a primary key.

Signatures point backward. An artifact signed with SHA-1 in 2009 cannot be re-signed after the fact without the original key. Verifiers must therefore support old schemes even when they long since stopped producing them — and every such support is a potential downgrade path.

The costs are fully visible, the benefit is not. A migration causes measurable effort and potential outages. The benefit consists of incidents that do not happen. This pattern — visible costs against invisible benefit — is the same one at work in the post-quantum migration, only there with an even more distant deadline.

Counter-Cryptanalysis: The Countermeasure Nobody Notices

There is an elegant answer for the case where SHA-1 cannot yet be removed. Marc Stevens and Dan Shumow described in 2017, in Speeding up detection of SHA-1 collision attacks using unavoidable attack conditions (USENIX Security 2017; ePrint 2017/173), how to detect whether a message originates from a collision attack. The basis is "unavoidable conditions": properties every feasible attack of a given class must satisfy. If such a condition is absent, the message can be classified as harmless immediately.

The numbers make the technique practical for everyday use: the improved detection is about 16 times faster than the version without unavoidable conditions, and SHA-1 with collision detection is on average only about 1.96 times the cost of plain SHA-1 — a factor under two for the certainty that an object does not stem from a collision attack. The sha1collisiondetection implementation (sha1dc) was adopted by Git and GitHub among others; that is precisely why Git hosts could reject the SHAttered PDFs without changing their object names.

This is conceptually notable: you do not repair the hash function, you detect the attacks. The limit of this approach is both obvious and stated in the paper: the conditions apply to known attack classes, derived from a conjecture about differential paths. Flame showed that attackers can use classes that are not yet published. Counter-cryptanalysis buys time; it does not replace migration.

Git: The Migration You Can Watch Live

Git is the most visible case. The official breaking-changes documentation names the switch for Git 3.0: "The default hash function for new repositories will be changed from 'sha1' to 'sha256'." The stated rationale cites NIST's 2011 deprecation and explicitly the four attacks — SHAppening (2⁵⁷), SHAttered (2⁶³), the 2019 birthday-near-collision attack (2⁶⁸ for chosen-prefix) and Shambles (2⁶³ for chosen-prefix).

Two details of that announcement matter more in practice than the headline. First, no release date is given; the project explicitly states that the prerequisite is the readiness of the ecosystem — libraries, tools and forges must support the SHA-256 object format. Second, it says explicitly: "There is no plan to deprecate the 'sha1' object format at this point in time." The rationale is also remarkably candid: protections against known attacks are in place, but more are expected, and it is "only a matter of time" before SHA-1 is considered completely broken.

That is, incidentally, a good model for any migration of your own: switch the default for new things, keep being able to read the old, build detection in for the transition period, and make the end date depend on the maturity of the surrounding ecosystem rather than on a wished-for deadline.

Part 6: What You Can Concretely Do in 2026

The One Question That Orders Any Inventory

A hash inventory that merely lists algorithms is nearly worthless, because it treats every occurrence identically. It becomes useful when each occurrence carries three pieces of information:

1. Which algorithm?
2. May an attacker help shape the hashed data before it is hashed? (This is the question from Part 2 — it decides whether a collision becomes an attack at all.)
3. Is a trust decision made on this hash, or merely a transmission check?

Only that combination yields a priority. An MD5 value that compares a downloaded file against a checksum from the same vendor over the same TLS channel protects against transmission errors and is adequate for that — it simply does nothing against a vendor or mirror that controls both values. A SHA-1 value in a signature path for software, certificates or identities, by contrast, belongs in the highest urgency tier, because all three conditions coincide there.

A Decision Matrix by Purpose

The last row matters because it contains the most common category error: for passwords the issue is not collision resistance but the computational cost per attempt. SHA-256 is no improvement there, just the same problem with a different output length.

Which Successors — and the Length-Extension Question

For new designs three options are defensible, and the choice between them has a concrete technical reason:

• SHA-256 / SHA-384 (SHA-2 family): broadly implemented, hardware-accelerated on practically every current CPU, 128 and 192 bits of collision security respectively. Downside: Merkle–Damgård, hence length-extendable.
• SHA-512/256: the SHA-512 variant truncated to 256 bits. Not length-extendable, and often faster than SHA-256 on 64-bit hardware without hash acceleration.
• SHA-3 / SHAKE (FIPS 202, 2015): sponge construction, structurally different design, not length-extendable. In software without acceleration usually slower than SHA-2.

I would take SHA-256 as the default and SHA-3 where structural diversification away from SHA-2 is explicitly wanted. There are no serious collision attacks against SHA-2 — the best known results concern reduced round counts — but the history in Parts 3 and 4 suggests that algorithm agility is itself the real protection. Concretely: never store a hash value bare, always with an algorithm identifier (the multihash pattern sha256:…), and write every verification function so that a second algorithm can be supported in parallel without changing the data model.

What Does Not Work

Three widespread pseudo-solutions are worth knowing, because they regularly appear as workarounds:

Concatenating two hash functions. MD5(m) ‖ SHA1(m) is not as strong as the sum of the lengths suggests. Antoine Joux showed in 2004 that Merkle–Damgård constructions permit multicollisions whose generation is barely more expensive than that of a single collision — and that the security of a concatenation therefore reduces largely to that of the stronger individual function. A concatenation is considerably more expensive and barely more secure.

More iterations. MD5(MD5(m)) does not remove the collision attack: if m₁ and m₂ already collide in the first pass, they collide in the second as well.

Truncating or extending the hash to make it "different." A collision of the full output is also a collision of every prefix of the output. Truncation reduces security; it never increases it.

Part 7: The Overarching Principle

The breaking of MD5 and SHA-1 is not a cryptographic special topic. It is the most cleanly documented example of a class of risk that occurs in every architecture: assumptions whose validity depends on a price that monotonically falls.

A hash function never promises "impossible." It promises "too expensive." That price drops from two independent directions: through cryptanalysis, which arrives in unpredictable jumps, and through hardware, which gets cheaper steadily and predictably. The second factor alone finishes off any 64-bit security margin — with no new insight required. Anyone who makes a security assumption is thereby also making an implicit statement about an expiry date, and in most systems that date is written down nowhere.

From this follows a design posture that reaches well beyond hash functions. A system should not try to pick the right algorithm — over twenty years that is not possible. It should be built so that changing the algorithm is a routine operation. The actual mistake with MD5 was not deploying it in 1995; back then it was the state of the art. The mistake was deploying it in a way that made exiting it twenty years later require a migration of the data model.

The Central Takeaway

The load-bearing insight of this article is not "MD5 and SHA-1 are broken," but: a collision only becomes an attack when the attacker was allowed to help shape part of the data before it was hashed. That one question — not the algorithm's name — separates the acute problem from the technical-debt entry.

From this follow four steps you can take in any project. First: inventory every place where a hash carries a trust decision — signature verification, certificate chain, artifact release, identity mapping — and note for each whether an outside party contributes parts of the input. That list, not the algorithm list, is the priority list. Second: remove MD5 and SHA-1 entirely from all signature and certification paths; where SHA-1 must still be verified, enable collision detection (sha1dc) and log every hit as a security incident. Third: from now on store no hash value without an algorithm identifier, and write every verification so it can accept two algorithms in parallel — this is the step that turns the next migration from a project into a configuration change. Fourth: check whether a hash output of 128 bits or less carries a collision assumption anywhere; 64 bits of collision security is no longer a margin, it is a deadline.

A Question to Reflect On

The 2008 Rogue CA demonstration did not work because MD5 was weak. It worked because MD5 was weak and the serial number was sequential and the timestamp was predictable to the second. Each of those three details had been classified as harmless within its own area of responsibility — entirely correctly, as long as it was viewed in isolation. The attack arose in the gaps between three correct individual assessments.

The question that follows is more uncomfortable than it sounds: every architecture has properties nobody tracks as security properties — predictable IDs, precise timestamps, deterministic ordering, stable formatting. They appear in no threat model, because they belong to no single component owner. Who in your system actually examines the combinations, once every individual component has been assessed correctly? Because in experience that examination is not performed in a review. It is performed by an attacker who is the first to look at all three parts at once.

Cross-References in the Vault

• The Tree That Condenses Truth: Merkle Trees and the Art of Efficient Integrity Verification – the construction resting on exactly the assumption discussed here: a Merkle tree is only as strong as its hash function's collision resistance.
• The End of the Password: Passkeys, WebAuthn and the Anatomy of Phishing-Resistant Sign-In – the signature over challenge and origin presupposes a collision-resistant hash function; the example of algorithm agility in the data model.
• The Key That Dies After Every Message: The Signal Protocol, the Double Ratchet, and the Art of End-to-End Encryption – HKDF and HMAC as the correct use of hash functions, in contrast to the naive H(key ‖ msg).
• Harvest Now, Decrypt Later: Post-Quantum Cryptography and the Race Against the Quantum Computer – the same migration pattern with a more distant deadline: visible costs, invisible benefit, and agility as the real answer.
• The Backdoor at the Heart of Linux: The XZ Attack and the Anatomy of a Supply-Chain Compromise – the attack that alters the trust chain instead of breaking the cryptography; the other half of the same threat picture.
• Proving Without Revealing: Zero-Knowledge Proofs from Ali Baba's Cave to zk-SNARKs – proof systems whose soundness in practice also rests on collision resistance in the Fiat-Shamir step.
• When the Processor Guesses Too Much: Spectre, Meltdown, and the Sin of Speculative Execution – the same lesson one abstraction layer down: an assumption that holds until somebody recomputes the price of breaking it.

Sources

• Wang, X., Yu, H. (2005): How to Break MD5 and Other Hash Functions. In: Cramer, R. (ed.), Advances in Cryptology – EUROCRYPT 2005, LNCS 3494, Springer, pp. 19–35. DOI: 10.1007/11426639_2. https://link.springer.com/chapter/10.1007/11426639_2
• Wang, X., Yin, Y. L., Yu, H. (2005): Finding Collisions in the Full SHA-1. In: Shoup, V. (ed.), Advances in Cryptology – CRYPTO 2005, LNCS 3621, Springer, pp. 17–36. DOI: 10.1007/11535218_2. https://link.springer.com/chapter/10.1007/11535218_2
• Sotirov, A., Stevens, M., Appelbaum, J., Lenstra, A., Molnar, D., Osvik, D. A., de Weger, B. (2008/2009): MD5 considered harmful today – Creating a rogue CA certificate. Presented December 30, 2008 at the 25th Chaos Communication Congress, Berlin; scientific write-up received the best-paper award at CRYPTO 2009. https://marc-stevens.nl/research/hashclash/rogue-ca/
• Stevens, M., Bursztein, E., Karpman, P., Albertini, A., Markov, Y. (2017): The first collision for full SHA-1. CRYPTO 2017; Cryptology ePrint Archive, Paper 2017/190. https://eprint.iacr.org/2017/190
• Stevens, M., Shumow, D. (2017): Speeding up detection of SHA-1 collision attacks using unavoidable attack conditions. 26th USENIX Security Symposium; Cryptology ePrint Archive, Paper 2017/173. https://eprint.iacr.org/2017/173
• Leurent, G., Peyrin, T. (2019): From Collisions to Chosen-Prefix Collisions – Application to Full SHA-1. EUROCRYPT 2019; Cryptology ePrint Archive, Paper 2019/459. https://eprint.iacr.org/2019/459
• Leurent, G., Peyrin, T. (2020): SHA-1 is a Shambles: First Chosen-Prefix Collision on SHA-1 and Application to the PGP Web of Trust. 29th USENIX Security Symposium (USENIX Security 20), pp. 1839–1856. https://www.usenix.org/conference/usenixsecurity20/presentation/leurent
• Fillinger, M. J. (2013): Reconstructing the Cryptanalytic Attack behind the Flame Malware. Master of Logic Thesis MoL-2013-23, ILLC, University of Amsterdam / CWI; supervisors: M. Stevens, C. Schaffner. https://eprints.illc.uva.nl/912
• National Institute of Standards and Technology (2022): NIST Transitioning Away from SHA-1 for All Applications. CSRC News, December 15, 2022. https://csrc.nist.gov/News/2022/nist-transitioning-away-from-sha-1-for-all-apps
• Git project: Git – BreakingChanges Documentation. Section on Git 3.0 and the switch of the default hash function to SHA-256. https://git-scm.com/docs/BreakingChanges

← All articles