Chosen-prefix collisions for MD5 and applications. (1st January 2012)

• Record Type: Journal Article
• Authors: Stevens, Marc; Lenstra, Arjen K.; de Weger, Benne
• Is Part Of: International journal of applied cryptography. Volume 2:Number 4(2012)
• Page Start: 322
• Page End: 359
• Publication Date: 2012-01-01
• Subjects: MD5 -- chosen-prefix collision attack -- differential analysis -- certification authority -- playstation 3; Data encryption (Computer science) -- Periodicals; Cryptography -- Periodicals; Computer security -- Periodicals; 652.8
• Languages: English
• ISSNs: 1753-0563

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 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 chosenprefix 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 onhttp://www.win.tue.nl/hashclash/ChosenPrefixCollisions/ .