Skip to main content
No Access

Chosen-prefix collisions for MD5 and applications

Published Online:pp 322-359https://doi.org/10.1504/IJACT.2012.048084

We present a novel, automated way to find differential paths for MD5. Its main application is in the construction of chosen-prefix collisions. We have shown how, at an approximate expected cost of 239 calls to the MD5 compression function, for any two chosen message prefixes P and P′, suffixes S and S′ can be constructed such that the concatenated values PS and P′║S′ collide under MD5. The practical attack potential of this construction of chosenprefix collisions is of greater concern than the MD5-collisions that were published before. This is illustrated by a pair of MD5-based X.509 certificates one of which was signed by a commercial Certification Authority (CA) as a legitimate website certificate, while the other one is a certificate for a rogue CA that is entirely under our control (cf. http://www.win.tue.nl/hashclash/rogue-ca/). Other examples, such as MD5-colliding executables, are presented as well. More details can be found on http://www.win.tue.nl/hashclash/ChosenPrefixCollisions/.

Keywords

MD5, chosen-prefix collision attack, differential analysis, certification authority, playstation 3

References

  • 1. Bellovin, S.M. , Rescorla, E.K. (2006). ‘Deploying a new hash algorithm’. Proceedings of the Network and Distributed System Security Symposium, NDSS 2006. (accessed on 8 February 2012), San Diego, California, USA, The Internet Society, available at http://www.isoc.org/isoc/conferences/ndss/06/proceedings/papers/deployingnewhashalgorithm.pdf Google Scholar
  • 2. den Boer, B. , Bosselaers, A. (1994). ‘Collisions for the compression function of MD5’. 765, in EUROCRYPT ’93, Lecture Notes in Computer Science, 293-304 Google Scholar
  • 3. Bundesnetzagentur für Elektrizität, Gas, Telekommunikation, Post und Eisenbahnen (2007). ‘Bekanntmachung zur elektronischen Signatur nach dem Signaturgesetz und der Signaturverordnung (übersicht über geeignete Algorithmen)’. Bundesanzeiger. (accessed on 8 February 2012), 19, 376, available at ühttp://www.bundesnetzagentur.de/cln 1931/DE/Sachgebiete/QES/Veroeffentlichungen/Algorithmen/algorithmen node.html Google Scholar
  • 4. de Cannière, C. , Rechberger, C. (2006). ‘Finding SHA-1 characteristics: general results and applications’. 4284, in AsiaCrypt 2006, Lecture Notes in Computer Science, 1-20 Google Scholar
  • 5. Clark, W. , Liang, J. (1973). ‘On arithmetic weight for a general radix representation of integers’. IEEE Transactions on Information Theory. 19, 6, 823-826 Google Scholar
  • 6. Cooper, D. , Santesson, S. , Farrell, S. , Boeyen, S. , Housley, R. , Polk, W. ‘Internet X.509 public key infrastructure certificate and certificate revocation list (CRL) profile’. Internet Engineering Task Force, Request For Comments. 2008, 05, (accessed on 8 February 2012), RFC 5280, available at http://www.ietf.org/rfc/rfc5280.txt Google Scholar
  • 7. Daum, M. (2005). ‘Cryptanalysis of hash functions of the MD4-Family’. PhD thesis Google Scholar
  • 8. Daum, M. , Lucks, S. ‘Attacking hash functions by poisoned messages, ‘The story of Alice and her boss’. 2005, 06, (accessed on 8 February 2012), available at http://th.informatik.uni-mannheim.de/People/lucks/HashCollisions/ Google Scholar
  • 9. Dobbertin, H. (1996). ‘Cryptanalysis of MD5 compress’. (accessed on 8 February 2012), EUROCRYPT’96 Rump Session, May, available at http://www-cse.ucsd.edu/bsy/dobbertin.ps Google Scholar
  • 10. Gauravaram, P. , McCullagh, A. , Dawson, E. (2006). ‘Collision attacks on MD5 and SHA-1: is this the ‘sword of Damocles’ for electronic commerce?’. (accessed on 8 February 2012), AusCERT 2006 R&D Stream, May, available at http://www2.mat.dtu.dk/people/P.Gauravaram/AusCert-6.pdf Google Scholar
  • 11. Gebhardt, M. , Illies, G. , Schindler, W. (2005). ‘A note on practical value of single hash collisions for special file formats’. (accessed on 8 February 2012), NIST First Cryptographic Hash Workshop, October/November, available at http://csrc.nist.gov/groups/ST/hash/documents/Illies NIST 05.pdf Google Scholar
  • 12. Halevi, S. , Krawczyk, H. (2006). ‘Strengthening digital signatures via randomized hashing’. 4117, in CRYPTO 2006, Lecture Notes in Computer Science, 41-59 Google Scholar
  • 13. Hawkes, P. , Paddon, M. , Rose, G. (2004). ‘Musings on the Wang et al. MD5 collision’. Cryptology ePrint Archive. (accessed on 8 February 2012), Report 2004/264, available at http://eprint.iacr.org/2004/264 Google Scholar
  • 14. Hoffman, P. , Schneier, B. ‘Attacks on cryptographic hashes in internet protocols’. Internet Engineering Task Force, Request For Comments. 2005, 11, (accessed on 8 February 2012), RFC 4270, available at http://www.ietf.org/rfc/rfc4270.txt Google Scholar
  • 15. Kaminsky, D. ‘MD5 to be considered harmful someday’. 2004, 12, (accessed on 8 February 2012), available at http://dankaminsky.com/2004/12/06/46/ Google Scholar
  • 16. Kelsey, J. , Kohno, T. (2006). ‘Herding hash functions and the Nostradamus attack’. 4004, in EUROCRYPT 2006, Lecture Notes in Computer Science, 183-200 Google Scholar
  • 17. Klima, V. (2005). ‘Finding MD5 collisions on a notebook PC using multi-message modifications’. Cryptology ePrint Archive. (accessed on 8 February 2012), Report 2005/102, available at http://eprint.iacr.org/2005/102 Google Scholar
  • 18. Klima, V. (2006). ‘Tunnels in hash functions: MD5 collisions within a minute’. Cryptology ePrint Archive. (accessed on 8 February 2012), Report 2006/105, available at http://eprint.iacr.org/2006/105 Google Scholar
  • 19. Lenstra, A.K. , de Weger, B.M.M. (2005). ‘On the possibility of constructing meaningful hash collisions for public keys’. (accessed on 8 February 2012), 3574, in ACISP 2005, Lecture Notes in Computer Science, 267-279, Full version available at http://www.win.tue.nl/ bdeweger/CollidingCertificates/ddl-full.pdf Google Scholar
  • 20. McDonald, C. , Hawkes, P. , Pieprzyk, J. (2009). ‘SHA-1 collisions now 252’. (accessed on 8 February 2012), EUROCRYPT 2009 Rump session, available at http://eurocrypt2009rump.cr.yp.to/837a0a8086fa6ca714249409ddfae43d.pdf Google Scholar
  • 21. Mendel, F. , Rechberger, C. , Rijmen, V. (2007). ‘Update on SHA-1’. (accessed on 8 February 2012), CRYPTO 2007 Rump session, available at http://rump2007.cr.yp.to/09-rechberger.pdf Google Scholar
  • 22. Menezes, A. , van Oorschot, P.C. , Vanstone, S.A. (1996). Handbook of Applied Cryptography. CRC Press Google Scholar
  • 23. Mikle, O. (2004). ‘Practical attacks on digital signatures using MD5 nessage digest’. Cryptology ePrint Archive. (accessed on 8 February 2012), Report 2004/356, available at http://eprint.iacr.org/2004/356 Google Scholar
  • 24. National Institute of Standards and Technology NIST (2008). FIPS PUB 180-3: Secure Hash Standard. Google Scholar
  • 25. van Oorschot, P.C. , Wiener, M.J. (1999). ‘Parallel collision search with cryptanalytic applications’. Journal of Cryptology. 12, 1, 1-28 Google Scholar
  • 26. Primmer, R. , D’Halluin, C. (2005). ‘Collision and preimage resistance of the centera content address’. (accessed on 8 February 2012), EMC Corporation, Technical report, available at http://www.robertprimmer.com/home/TechPapersfiles/CenteraCollisionProbs.pdf Google Scholar
  • 27. Rechberger, C. (2006). unpublished result Google Scholar
  • 28. Rivest, R. ‘The MD5 Message-Digest Algorithm’. Internet Engineering Task Force, Request For Comments. 1992, 04, (accessed on 8 February 2012), RFC 1321, available at http://www.ietf.org/rfc/rfc1321.txt Google Scholar
  • 29. Stevens, M. (2006). ‘Fast collision attack on MD5’. Cryptology ePrint Archive. (accessed on 8 February 2012), Report 2006/104, available at http://eprint.iacr.org/2006/104 Google Scholar
  • 30. Stevens, M. ‘On collisions for MD5’. 2007, 06, (accessed on 8 February 2012), TU Eindhoven MSc thesis, available at http://www.win.tue.nl/hashclash/On%20Collisions%20for%20MD5%20-%20M.M.J.%20Stevens.pdf Google Scholar
  • 31. Stevens, M. , Lenstra, A.K. , de Weger, B.M.M. (2007). ‘Chosen-prefix collisions for MD5 and colliding X.509 certificates for different identities’. 4515, in EUROCRYPT 2007, Lecture Notes in Computer Science, 1-22 Google Scholar
  • 32. Stevens, M. , Sotirov, A. , Appelbaum, J. , Lenstra, A.K. , Molnar, D. , Osvik, D.A. , de Weger, B.M.M. (2009). ‘Short chosen-prefix collisions for MD5 and the creation of a rogue CA certificate’. 5677, in CRYPTO 2009, Lecture Notes in Computer Science Google Scholar
  • 33. Stevens, M. (2012). ‘Attacks on hash functions and applications’. (accessed on 8 February 2012), Universiteit Leiden PhD thesis, to appear, available at http://marc-stevens.nl/research Google Scholar
  • 34. Wang, X. , Feng, D. , Lai, X. , Yu, H. (2004). ‘Collisions for hash functions MD4, MD5, HAVAL-128 and RIPEMD’. Cryptology ePrint Archive. (accessed on 8 February 2012), Report 2004/199, available at http://eprint.iacr.org/2004/199 Google Scholar
  • 35. Wang, X. , Yao, A. , Yao, F. (2005a). ‘New collision search for SHA-1’. (accessed on 8 February 2012), CRYPTO 2005 Rump session, available at http://www.iacr.org/conferences/crypto2005/r/2.pdf Google Scholar
  • 36. Wang, X. , Yin, Y.L. , Yu, H. (2005b). ‘Finding collisions in the full SHA-1’. 3621, in CRYPTO 2005, Lecture Notes in Computer Science, 17-36 Google Scholar
  • 37. Wang, X. , Yu, H. (2005). ‘How to break MD5 and other hash functions’. 3494, in EUROCRYPT 2005, Lecture Notes in Computer Science, 19-35 Google Scholar
  • 38. Xie, T. , Liu, F. , Feng, D. (2008). ‘Could the 1-MSB input difference be the fastest collision attack for MD5?’. Cryptology ePrint Archive. (accessed on 8 February 2012), Report 2008/391, available at http://eprint.iacr.org/2008/391 Google Scholar