I’ve written a little recently (and less recently!) about Post Quantum Encryption and how action is needed NOW.
How the timeline of QVE’s unravelling and collapse will take place is almost impossible to say. But we might usefully draw some lessons from the collapse in confidence of the MD5 hashing algorithm.
Let’s look at the timeline and some important milestones, from the introduction of MD5 to its complete deprecation.
1991: MD5 Introduced
- Yes, it really was that recent, just 34 years ago!
- Ron Rivest (RSA Data Security) publishes MD5 as an improved version of MD4.
- It becomes widely adopted for checksums, PGP signatures (original PGP keys, now known as “legacy PGP keys” – using a single RSA keypair for both signature and encryption functions), SSL certificates, and password storage.
1993–1995: MD4 fractures, MD5 suspect
- 1993: Den Boer and Bosselaers demonstrate partial weaknesses in MD5’s design. Pseudocollisions are the first significant signs of weakness in MD5. These are not full collisions, but a sound starting point for future attacks.
- 1995: Hans Dobbertin breaks MD4 completely and warns that MD5 shares similar structural flaws, the two being very much of the same family.
- 1996: RSA Laboratories’ Cryptobytes newsletter formally acknowledges Dobbertin’s findings; MD4 is broken, and MD5 “should be considered vulnerable”, and therefore not to be relied upon. It recommends migration to SHA-1, which the American NSA had recently standardised (having subtly modified the original SHA by inserting a one-bit rotation into the message schedule of SHA to produce SHA-1, because it removed a structural weakness in the diffusion properties that made SHA vulnerable to differential cryptanalysis – although the rest of the world did not realise this for a decade or so after this)
- We’re only two years into the lifetime of MD5 and already it is looking shaky.
1996–2003: Slow Decline in Confidence
- The cryptographic community gradually moves away from MD5 for high-security use, though many software ecosystems continue using it.
- 2003: Wang Xiaoyun’s team in China begins developing new differential techniques that can find collisions in weakened hash variants, foreshadowing disaster.
2004: Practical Collision Demonstration
- August 2004: Wang, Feng, Lai, and Yu publish a paper showing practical collisions in MD5. The first credible, reproducible break of a widely used modern hash. The finding makes front-page news in crypto circles.
- August 2004: A small claim to fame for myself.
- Sitting beside a pool in Barcelona, took the above work, and then published a transplanted PGP signature using original RSA keys (which used an MD5 hash for signatures).This highlighted the fragility of legacy MD5 signatures just as the algorithm’s security fell apart.
- I wrote this up on LinkedIn in 2018, which you can find here complete with links to all the files should you wish to test it yourself, and also some fun 2008 US election predictions made using MD5 too.
- This effectively marked MD5’s death in theory, though it lingered in practice for years.
2005–2007: Collisions Widespread & Weaponised
- 2005: Practical tools appear allowing anyone to generate MD5 collisions within hours on commodity hardware.
- 2006–2007: “Chosen-prefix” collisions are demonstrated, allowing two arbitrary documents with different contents but the same MD5 hash to be constructed, and enabled the fun with the US Election Results Predictions from 2008. This rendered digital signature systems using MD5 completely untrustworthy.
2008: Catastrophic Exploits
- January 2008: Multiple “predicted” files appear (like the 2008 US Presidential Election forecasts), all sharing the same MD5 hash; a public demonstration of collision reproducibility. It became an educational meme for how weak MD5 had become.
- December 2008: Stevens et al use a chosen-prefix collision to forge a valid SSL certificate authority certificate signed by RapidSSL. This proved that MD5’s weakness could be used to subvert the global trust infrastructure.
2009–2012: Institutional Rejection
- 2009: Microsoft, Mozilla, and OpenSSL officially deprecate MD5 in certificates and signatures.
- 2011–2012: NIST removes MD5 from FIPS-approved algorithms for any form of digital signature, key derivation, or HMAC construction.
2013–2017: Total Abandonment
- Major vendors remove MD5 as a signature option.
Most systems (TLS, SSH, PGP) reject MD5 signatures by default. - Remaining use is limited to file checksums and non-security integrity checks.
2019–Present: Legacy Use Only
- MD5 is now classed as cryptographically broken and unsuitable for any security use. Collision generation can be done on a laptop in milliseconds.
- It remains occasionally used for non-cryptographic checksums (such as deduplication or corruption detection), but never for authentication or trust. It is faster to run than stronger hashing algorithms, and if the use case does not include anyone attempting to subvert it, then it can still be useful
Summary
It took approximately 13-19 years from the first hints of weakness for the algorithm to be fully deprecated.
Post Quantum Cryptography was being discussed in the late 2000s – I’m not sure when it first surfaced, but certainly by 2009. And that is already at least 16 years ago.
Now is NOT a good time to place any bets of any significant value or importance upon the continued ability of QVE to provide long-term confidentiality protection.
Sophie Baskerville 