We present a novel, automated way to find differential paths for MD5. Its main application is in the construction of \emph{chosen-prefix collisions}. We have shown how, at an approximate expected cost of $2^{39}$ 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.\ \url{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 \url{http://www.win.tue.nl/hashclash/ChosenPrefixCollisions/}.

Additional Metadata
Keywords MD5 chosen-prefix attack differential analysis certification authority playstation 3
MSC Cryptography (msc 94A60)
THEME Software (theme 1)
Publisher Inderscience Publishers
Journal International Journal of Applied Cryptography
Project Cryptanalysis of Widely-used Hash Function Standards and Beyond
Grant This work was funded by the The Netherlands Organisation for Scientific Research (NWO); grant id nwo/617.001.201 - Cryptanalysis of Widely-used Hash Function Standards and Beyond
Stevens, M.M.J, Lenstra, A.K, & de Weger, B. (2012). Chosen-Prefix Collisions for MD5 and Applications. International Journal of Applied Cryptography, 2(4), 322–359.