Paper 2006/360

Target Collisions for MD5 and Colliding X.509 Certificates for Different Identities

Marc Stevens, Arjen Lenstra, and Benne de Weger

Abstract

We have shown how, at a cost of about $2^{52}$ calls to the MD5 compression function, for any two target messages $m_1$ and $m_2$, values $b_1$ and $b_2$ can be constructed such that the concatenated values $m_1\|b_1$ and $m_2\|b_2$ collide under MD5. Although the practical attack potential of this construction of \emph{target collisions} is limited, it is of greater concern than random collisions for MD5. In this note we sketch our construction. To illustrate its practicality, we present two MD5 based X.509 certificates with identical signatures but different public keys \emph{and} different Distinguished Name fields, whereas our previous construction of colliding X.509 certificates required identical name fields. We speculate on other possibilities for abusing target collisions.

Note: Version 1.1, contains an appendix about differential path construction. The EuroCrypt 2007 proceedings version will have the title "Chosen-prefix Collisions for MD5 and Colliding X.509 Certificates for Different Identities". It contains a lot more details on the method of finding chosen-prefix collisions for MD-5, and somewhat less on the certificates. See www.win.tue.nl/hashclash.

Metadata
Available format(s)
PDF
Category
Applications
Publication info
Published elsewhere. Accepted at EuroCrypt 2007
Keywords
Hash collisionsX.509 certificates
Contact author(s)
b m m d weger @ tue nl
History
2007-03-05: last of 2 revisions
2006-10-25: received
See all versions
Short URL
https://ia.cr/2006/360
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2006/360,
      author = {Marc Stevens and Arjen Lenstra and Benne de Weger},
      title = {Target Collisions for MD5 and Colliding X.509 Certificates for Different Identities},
      howpublished = {Cryptology ePrint Archive, Paper 2006/360},
      year = {2006},
      note = {\url{https://eprint.iacr.org/2006/360}},
      url = {https://eprint.iacr.org/2006/360}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.