June 2, 2009

A Single Block Chosen Prefix Collision for MD5

Marc Stevens, CWI, in collaboration with LACAL, EPFL

 
Shorter collisions We present a new collision for MD5. Its main new feature is its shortness. Previous collision construction methods needed two 512-bit blocks (Wang's original collisions [WY]) or more than two (our previous chosen-prefix collisions used 8 + ε or even more collision blocks, recently reduced to 3 + ε). Here the ε stands for a few (up to 96) birthday bits. We now need only 1 + ε, i.e. a single collision block plus some birthday bits, for a chosen-prefix collision.
 
A Single Block Collision Here is an example of a chosen-prefix collision of only a single collision block.

Binary files for download: sbcpc1.bin, sbcpc2.bin

Contents of the files in readable hexadecimals:

sbcpc1.binsbcpc2.bin
appropriately chosen 416-bit prefix
4F64656420476F6C4E65616C204B6F62
6472656963680A4F6C69747A0A4E6561
64656420476F6C646C204B6F626C6974
72656963680A4F647A0A4E65616C204B
656420476F6C64726F626C69747A0A4E
656963680A4F646565616C204B6F626C
6420476F 69747A0A
96 birthday bits
D8050D00 75B80E00
19BB9318924CAA9635F3D2C909AF1BAD
single 512-bit collision block
DCE35CB835B349E1DCE35CB835B349E1
44E98C50C22CF46144E88C50C22CF461
244A4064BF1AFAEC244A40E4BF1AFAEC
C5820D428AD38D6BC5820D428AD38D6B
EC89A5AD51E29063EC89A5AD51E29063
DD79B16CF67C1297DD79B16CF6FC1197
8647F5AF123DE3AC8647F5AF123DE3AC
F844085CD025B956F84408DCD025B956

The MD5 Intermediate Hash Values:

sbcpc1.binsbcpc2.bin
initial IHV
0123456789ABCDEFFEDCBA9876543210
different IHVs after one block containing the chosen prefix and birthday bits
06CCFA8EF494FEAF2C19237B0AF2B560 E6CBFA8ED4DCACDA0C19E37DEAF1B562
colliding IHVs after one collision block
913C7645059581F957075EFDEAA7ACBF
MD5 hash value after padding and MD-strengthening
D320B6433D8EBC1AC65711705721C2E1

The paper [SSALMOW] contains (a.o.) a description of the method by which this collision is constructed. See also the full paper [SLW].

Finding the birthday bits took 47 hours (expected was 3 days) on the cluster of 215 Playstation 3 game consoles at LACAL, EPFL. This is roughly equivalent to 400,000 hours on a single PC core. The single near-collision block construction took 18 hours and 20 minutes on a single PC core.
 
Pictures As usual we have made pretty pictures visualizing the collision.

This picture shows the differences in the IHVs only.



And this picture shows the differences in the internal states of the compression after each step as well.

 
References
[SLW] Marc Stevens, Arjen Lenstra and Benne de Weger,
"Chosen-prefix Collisions for MD5 and Applications",
submitted to the Journal of Cryptology, available from LACAL, EPFL.
[SSALMOW] Marc Stevens, Alexander Sotirov, Jacob Appelbaum, Arjen Lenstra, David Molnar, Dag Arne Osvik and Benne de Weger,
"Short chosen-prefix collisions for MD5 and the creation of a rogue CA certificate",
in: Shai Halevi (ed.), "Advances in Cryptology - CRYPTO 2009", Proceedings of Crypto 2009, Springer LNCS 5677, 2009, pp. 55-69.
[WY] Xiaoyun Wang and Hongbo Yu,
"How to Break MD5 and Other Hash Functions"
In: Ronald Cramer (editor), "Advances in Cryptology - EUROCRYPT 2005",
volume 3494 of Lecture Notes in Computer Science, pages 19-35,
Springer Verlag, Berlin, 2005.
 
Author
Marc Stevens
Centrum Wiskunde & Informatica (CWI),
Amsterdam, The Netherlands
http://homepages.cwi.nl/~stevens/
 
Collaborators
LACAL, EPFL
Lausanne, Switzerland
http://lacal.epfl.ch/

Pictures and website by Benne de Weger, TU/e.
 
Latest Modification August 22, 2009
 
Vanity Counter