Short chosen-prefix collisions for MD5 and the creation of a rogue CA certificate

M.M.J. Stevens, A. Sotirov, J.R. Appelbaum, A.K. Lenstra, D. Molnar, D.A. Osvik, B.M.M. Weger, de

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

113 Citations (Scopus)
143 Downloads (Pure)

Abstract

We present a refined chosen-prefix collision construction for MD5 that allowed creation of a rogue Certification Authority (CA) certificate, based on a collision with a regular end-user website certificate provided by a commercial CA. Compared to the previous construction from Eurocrypt 2007, this paper describes a more flexible family of differential paths and a new variable birthdaying search space. Combined with a time-memory trade-off, these improvements lead to just three pairs of near-collision blocks to generate the collision, enabling construction of RSA moduli that are sufficiently short to be accepted by current CAs. The entire construction is fast enough to allow for adequate prediction of certificate serial number and validity period: it can be made to require about 249 MD5 compression function calls. Finally, we improve the complexity of identical-prefix collisions for MD5 to about 216 MD5 compression function calls and use it to derive a practical single-block chosen-prefix collision construction of which an example is given.
Original languageEnglish
Title of host publicationAdvances in Cryptology - CRYPTO 2009 (29th Annual International Cryptology Conference, Santa Barbara CA, USA, August 16-20, 2009. Proceedings)
EditorsS. Halevi
Place of PublicationBerlin
PublisherSpringer
Pages55-69
ISBN (Print)978-3-642-03355-1
DOIs
Publication statusPublished - 2009

Publication series

NameLecture Notes in Computer Science
Volume5677
ISSN (Print)0302-9743

Fingerprint

Dive into the research topics of 'Short chosen-prefix collisions for MD5 and the creation of a rogue CA certificate'. Together they form a unique fingerprint.

Cite this