Title: Chosen-prefix collisions for MD5 and applications

Authors: Marc Stevens; Arjen K. Lenstra; Benne De Weger

Addresses: Cryptology Group, CWI, P.O. Box 94079, 1090 GB Amsterdam, The Netherlands. ' Laboratory for Cryptologic Algorithms, École Polytechnique Fédérale de Lausanne, Station 14, CH-1015 Lausanne, Switzerland. ' EiPSI, Faculty of Mathematics and Computer Science, TU Eindhoven, P.O. Box 513, 5600 MB Eindhoven, The Netherlands

Abstract: 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 2³⁹ 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 P||S and P′||S′ collide under MD5. The practical attack potential of this construction of chosen-prefix 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 attacks; differential analysis; certification authority; Playstation 3; cryptographic hash functions; hash values; cryptography; information security.

DOI: 10.1504/IJACT.2012.048084

International Journal of Applied Cryptography, 2012 Vol.2 No.4, pp.322 - 359

Published online: 30 Sep 2014 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article