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:
The MD5 Intermediate Hash Values:
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.
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.
Centrum Wiskunde & Informatica (CWI),
Amsterdam, The Netherlands
Pictures and website by Benne de Weger, TU/e.
|Latest Modification||August 22, 2009|