Short Chosen-Prefix Collisions for MD5 and the Creation of a Rogue CA Certificate

Marc Stevens; Alexander Sotirov; Jacob Appelbaum; Arjen Lenstra; David Molnar; Dag Arne Osvik; Benne de Weger

Paper 2009/111

Short Chosen-Prefix Collisions for MD5 and the Creation of a Rogue CA Certificate

Marc Stevens, Alexander Sotirov, Jacob Appelbaum, Arjen Lenstra, David Molnar, Dag Arne Osvik, and Benne de Weger

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 °exible 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 2^{49} MD5 compression function calls. Finally, we improve the complexity of identical-prefix collisions for MD5 to about 2^{16} MD5 compression function calls and use it to derive a practical single-block chosen-prefix collision construction of which an example is given.

Note: Accompanying websites: www.win.tue.nl/hashclash/rogue-ca/ www.win.tue.nl/hashclash/SingleBlock/

Metadata

Available format(s): PDF
Category: Secret-key cryptography
Publication info: Published elsewhere. Crypto 2009 proceedings version
Keywords: MD5 collision attack certificate PlayStation3
Contact author(s): b m m d weger @ tue nl
History: 2009-06-03: revised; 2009-03-11: received; See all versions
Short URL: https://ia.cr/2009/111
License: CC BY

BibTeX

@misc{cryptoeprint:2009/111,
      author = {Marc Stevens and Alexander Sotirov and Jacob Appelbaum and Arjen Lenstra and David Molnar and Dag Arne Osvik and Benne de Weger},
      title = {Short Chosen-Prefix Collisions for {MD5} and the Creation of a Rogue {CA} Certificate},
      howpublished = {Cryptology {ePrint} Archive, Paper 2009/111},
      year = {2009},
      url = {https://eprint.iacr.org/2009/111}
}