up:: Migration Architecture MOC

Lessons from Past Crypto Migrations

Lessons from past crypto migrations are the historical evidence for how long it really takes to remove a cryptographic algorithm once it is known to be weak, and the answer is consistently a decade or more. The MD5 and SHA-1 hash deprecations, the DES-to-AES cipher transition, and the RC4 removal each ran for ten to twenty years between the first serious break and the algorithm’s practical retirement. The reason matters for the post-quantum transition: none of these stalled on the cryptography, which was settled early. They stalled on finding every deployment, on ecosystem coordination, on backward compatibility, and on the absence of a forcing deadline, which is exactly the profile of the migration ahead.

The short version:

• The historical pattern is a decade-plus lag between “this algorithm is broken” and “this algorithm is gone,” across every major deprecation.
• MD5 was shown collidable in 2004 and used to forge a real CA certificate in 2008, yet lingered in deployed systems for years after.
• SHA-1 got a practical collision in 2017 (SHAttered), but NIST set the full phase-out deadline at the end of 2030, a 13-year runway after the break.
• DES was superseded by AES in 2001 and formally withdrawn in 2005, and Triple-DES took even longer to disappear from the field.
• RC4 was prohibited in TLS by RFC 7465 in 2015, decades after its weaknesses were known, because it was embedded everywhere.
• Migrations stall on deployment and coordination, not on the math, and a hard deadline is what finally moves them, which is the case for the post-quantum mandates.

The four migrations, side by side, show the same decade-plus shape:

Algorithm	Decisive break	Formal removal or deadline	Runway
MD5	Full collision, 2004; forged CA cert, 2008	RFC 6151 guidance, 2011; lingered years after	~7+ years and beyond
SHA-1	SHAttered practical collision, February 2017	NIST phase-out by December 31, 2030	~13 years
DES to AES	56-bit key brute-forceable, late 1990s	AES standard 2001; DES (FIPS 46-3) withdrawn May 2005	~4 years post-AES, longer for Triple-DES
RC4	Practical TLS plaintext recovery, early 2010s	RFC 7465 prohibition, February 2015	~decade-plus from known weakness

Think of a recalled part in a machine that shipped in millions of units over decades. Confirming the part is defective is the fast, decisive step. Locating every unit still running it, sourcing a replacement that fits, and swapping it without breaking the machines it sits inside is the slow part that takes years, and cryptography is that recalled part buried inside software, firmware, and protocols nobody fully mapped.

How long did the MD5 migration actually take?

MD5 is the clearest case of a break arriving early and removal arriving late. Ron Rivest published MD5 in 1992 as RFC 1321, and by August 2004 Xiaoyun Wang and colleagues announced practical collisions for the full algorithm, breaking its collision resistance outright. That was the decisive cryptographic verdict, and it landed in 2004. The real-world consequences took years more to force action: in December 2008, a research team used MD5 collisions to forge a working intermediate certificate-authority certificate, demonstrating that the weakness was not academic but a live path to impersonating any website. The same month, the CMU Software Engineering Institute stated plainly that MD5 was cryptographically broken and unsuitable for further use, and RFC 6151 followed in 2011 to update its security guidance.

Even with a break in 2004 and a public CA forgery in 2008, MD5 stayed in deployed protocols, legacy signatures, and certificate chains for years afterward, because removing it meant finding and changing every place it was embedded. The lesson is the shape of the timeline: the cryptographic break was fast and unambiguous, and the removal was slow and uneven, gated entirely by deployment reach rather than by any remaining doubt about the algorithm.

Source: NIST/Wikipedia consolidated on the RFC 1321 (1992) publication, Wang et al. August 2004 collision, Sotirov et al. December 2008 rogue-CA forgery, and RFC 6151 (2011): datatracker.ietf.org/doc/html/rfc6151 [OPERATOR VERIFY: the 2004 collision and 2008 rogue-CA dates are widely cited but confirm against the original Wang et al. and Sotirov et al. papers if a hard cite is needed].

Why did SHA-1 take more than a decade to phase out?

SHA-1 shows the same pattern with better-documented dates. Theoretical weaknesses were known for years, and NIST’s SP 800-131A deprecated SHA-1 for generating new digital signatures back in 2011. The decisive practical break came on February 23, 2017, when researchers from Google and CWI Amsterdam announced SHAttered, the first practical SHA-1 collision, which took roughly nine quintillion SHA-1 computations, about 6,500 CPU-years and 110 GPU-years run in parallel, thousands of times faster than brute force. After that, no reasonable observer could defend SHA-1 for collision-sensitive use.

Yet the removal ran on a long clock. On December 15, 2022, more than five years after SHAttered, NIST announced it would transition away from SHA-1 for all applications by December 31, 2030, setting a phase-out runway of roughly 13 years from the practical break to the mandated end. The gap is the lesson: the break was conclusive in 2017, and the ecosystem still needed until 2030 to remove SHA-1 everywhere, because it was embedded in certificates, signatures, legacy protocols, and countless systems that each had to be found and changed. A conclusive break does not equal a fast removal.

Source: shattered.io, “SHAttered” (February 23, 2017), shattered.io; NIST, “NIST Transitioning Away from SHA-1 for All Applications” (December 15, 2022; phase-out by December 31, 2030, per SP 800-131A), csrc.nist.gov/news/2022/nist-transitioning-away-from-sha-1-for-all-apps.

What did the DES-to-AES transition teach?

The DES-to-AES transition is the reference case for replacing a symmetric cipher across an ecosystem, and it teaches that even a clean, well-run migration with a strong successor takes years. DES was published as a standard in 1977, and its 56-bit key was understood to be brute-forceable by the late 1990s. NIST ran an open competition and selected Rijndael as the Advanced Encryption Standard in October 2000, publishing it as AES in FIPS 197 on November 26, 2001, which gave the world a vetted, superior replacement. NIST then formally withdrew DES (FIPS 46-3) on May 19, 2005, roughly four years after AES was standardized.

Two lessons stand out:

1. Even a ready successor and a formal withdrawal buy years, not speed. The interval from “DES is weak” through “AES is standard” to “DES is withdrawn” spanned years, and Triple-DES, the interim strengthening of DES, took much longer still to disappear from payment systems and legacy infrastructure.
2. The migration went smoothly partly because it was structurally easy. AES was a drop-in symmetric replacement that did not require re-architecting trust the way a public-key migration does.

The post-quantum transition has no such luxury: its public-key replacements change key sizes, message sizes, and certificate structures, so the DES-to-AES timeline is closer to a best case than a typical one.

Source: NIST, “Advanced Encryption Standard (AES),” FIPS 197 (November 26, 2001), csrc.nist.gov/pubs/fips/197/final; NIST, “Withdrawal of FIPS 46-3, FIPS 74, and FIPS 81” (May 19, 2005), csrc.nist.gov/news/2005/withdrawal-of-fips-46-3-fips-74-and-fips-81.

Why was RC4 so hard to remove from TLS?

RC4 is the case of an algorithm whose weaknesses were known for a very long time and which still took years to prohibit, because it was woven through the entire web. RC4 biases and statistical weaknesses were documented across the 2000s and grew into practical plaintext-recovery attacks against TLS by the early 2010s. Despite that, RC4 stayed in wide use because it was fast, universally implemented, and a convenient fallback that servers and clients kept offering for compatibility. The formal removal came with RFC 7465, “Prohibiting RC4 Cipher Suites,” published in February 2015, which stated that TLS clients MUST NOT include RC4 cipher suites in the ClientHello and servers MUST NOT select one.

The lesson is that a permitted fallback is a slow poison. RC4 survived long past its known weakness precisely because it remained configured and offered even where better options existed, which is the same failure mode a modern TLS inventory finds when a configuration permits an obsolete protocol version that a single handshake never negotiates. Removing an embedded algorithm required a hard, standards-level prohibition, and even then deployed systems took time to comply, because the algorithm had to be found and disabled in every configuration that still allowed it.

Source: IETF, “Prohibiting RC4 Cipher Suites,” RFC 7465 (February 2015), datatracker.ietf.org/doc/html/rfc7465.

What do these migrations predict for the post-quantum transition?

They predict that the post-quantum migration will be governed by deployment reach and coordination rather than by the cryptography, and that it will take longer than the math alone suggests. Four consistent patterns carry directly forward:

1. The break is fast, the removal is slow. Every case settled the cryptographic verdict quickly and then spent a decade or more removing the algorithm from the field. The post-quantum standards are already published, so the “slow removal” phase is the whole game.
2. Embedded and fallback deployments are where it stalls. MD5 in certificate chains, SHA-1 in legacy protocols, RC4 as a permitted fallback: the algorithm survives wherever it is buried or optionally allowed. This is why a CBOM and honest discovery come first, and why migrations stall on visibility.
3. A hard deadline is what finally moves it. SHA-1’s 2030 date and DES’s formal withdrawal did more than any paper. The post-quantum mandates play that role now, which is why the deadlines are load-bearing rather than aspirational.
4. Agility shortens the next one. Each of these migrations was slow partly because the algorithm was hardcoded rather than swappable. Crypto-agility is the lesson institutionalized: build the estate so the next algorithm change is a configuration edit, and the removal phase stops taking a decade.

The one place the analogy understates the difficulty is scope. DES-to-AES swapped one symmetric primitive for another with the same shape, while the post-quantum transition replaces public-key algorithms with ones that have different key and message sizes and different certificate structures, so the coordination burden is heavier than any prior migration. The history says a decade is normal for the easy cases, which is the argument for starting the hard one now.

Common misconceptions

1. “Once an algorithm is broken, it disappears quickly.” History says the opposite. MD5, SHA-1, DES, and RC4 each took ten to twenty years to leave the field after the break was clear, because removal is a deployment problem.
2. “The hard part of a migration is the cryptography.” The cryptography was settled early in every case. The hard part was finding every deployment and coordinating the ecosystem to change it.
3. “A ready replacement makes the migration fast.” AES was ready and vetted, and DES still took years to withdraw and Triple-DES longer to vanish. A good successor helps, and it does not eliminate the deployment lag.
4. “Fallback support is harmless.” RC4 and permitted-but-obsolete TLS versions show that an optionally-allowed weak algorithm survives for years and stays exploitable, which is why configuration-level discovery matters.
5. “Deadlines are just bureaucracy.” The SHA-1 2030 date and the DES withdrawal were what actually forced removal. A hard deadline is the mechanism that ends a stall, which is the role the post-quantum mandates play.

Questions people ask

How long do cryptographic migrations really take? A decade or more from the decisive break to practical removal, consistently. SHA-1’s phase-out runs 13 years from SHAttered (2017) to the NIST deadline (2030), and MD5, DES, and RC4 all show the same order of magnitude.

Why do they stall if the algorithm is known to be broken? Because the algorithm is embedded in software, firmware, certificates, and protocols across the whole estate, and removing it is a discovery-and-coordination problem, not a cryptographic one. This is the same reason post-quantum migrations stall.

Was the DES-to-AES migration a good model for the post-quantum one? Partly. It shows even a clean migration takes years, but AES was a drop-in symmetric replacement, while post-quantum public-key algorithms change key sizes, message sizes, and certificate structures, so the coming migration is harder than DES-to-AES.

What finally forced these algorithms out? Hard deadlines and formal prohibitions: NIST’s SHA-1 2030 date, the DES withdrawal in 2005, RFC 7465’s RC4 ban in 2015. A conclusive break alone did not move deployed systems, and a deadline did.

What is the single most transferable lesson for post-quantum? Start on discovery now and build crypto-agility, because the removal phase is the decade-long part and the standards are already set. The history says the deployment problem, not the cryptography, decides the timeline.

Do these lessons apply if my organization is small? Yes in shape, though the timeline compresses with scope. The stall comes from embedded and fallback deployments and from the absence of ownership, both of which appear in small estates too, just with fewer places to hide.

---

Everything here is the map, given freely. When your team needs these lessons turned into a migration sequenced against your own estate, with the discovery done and the agility gaps closed before the deadline forces the pace, that’s the work I do, and there’s an alignment briefing for it.

Last verified 2026-07-12 · Maintained by Addie LaMarr, LaMarr Labs.