MD5 collisions become practical
Summary
On 17 August 2004 Xiaoyun Wang, Dengguo Feng, Xuejia Lai and Hongbo Yu published actual collisions for the hash functions MD4, MD5, HAVAL-128 and RIPEMD in the IACR’s cryptology archive, presented at the CRYPTO 2004 conference. Two different inputs with the same MD5 value could now actually be computed instead of merely suspected in theory. For signatures and certificates, this marked the beginning of the end of MD5.
Why collisions matter
A cryptographic hash function should make it practically impossible to find two different inputs with the same result. Signatures usually sign only the hash value of a document; if there are collisions, a signature can under certain circumstances be transferred to a different document.
Weaknesses of MD5 had been known since the mid-1990s, but a concrete collision was missing. Wang and colleagues delivered it and showed that related functions were affected too. In 2008 researchers used MD5 collisions to create a rogue certificate authority, and in 2012 the spyware Flame used a forged Microsoft certificate on the same basis.
Ideas
- Theoretical weaknesses eventually become practical.
- Hash functions for signatures must be collision-resistant.
- Migrating to new algorithms takes years longer than breaking them.
- MD5 is still fine for checksums without an attacker, not for security.
Insights
- Four years passed between the 2004 paper and the practical attack on certificates in 2008, during which certificate authorities kept using MD5. Warnings alone are not enough; shutdown dates work.
- The same pattern repeated with SHA-1: theoretical break in 2005, practical collision in 2017.
Facts
- IACR ePrint 2004/199, received on 16 August 2004, last revision of 17 August 2004.
- Collisions were shown for MD4, MD5, HAVAL-128 and RIPEMD.
- In 2008 researchers used MD5 collisions to create a rogue certificate authority.
References
Remarks
- The linked page contains the abstract and the PDF of the paper.
Recommendations
- Remove MD5 and SHA-1 from signatures, certificates and password stores; use SHA-256 or SHA-3.
- For passwords, do not use fast hash functions at all but Argon2, scrypt or bcrypt.
Links to the original source and the Web Archive open in a new tab.