MD5 trick

[vlastimil.klima at volny.cz]

The trick could be shortly expressed as follows:
"Give me three files and I will give you another three with the
same MD5 hash"

Of course, it is a trick. Yesterday I updated my paper 
"Tunnels in Hash Functions: MD5 Collisions Within a Minute"
(http://eprint.iacr.org/2006/105.pdf) 
and MD5 collision program
(http://cryptography.hyperlink.cz/2006/web_version_1.zip).

Now, the average time of MD5 collision is 17 seconds 
on PC Intel Pentium 4 (3.2 MHz).

I asked Ondrej Mikle to write the program "pack3". 
Thanks to him, you can find the progrm on
http://cryptography.hyperlink.cz/2006/selfextract.zip  
Usage: pack3 file1 file2 file3 file4 file5 file6 will 
create two packages, package1.exe and package2.exe. 
Both will have the same MD5 sum, while 
package1.exe will extract files 1-3 
and package2.exe will extract files 4-6.

It enables attacking SW distribution process for instance. A
department, distributing SW (to clients, web, etc.) could
distribute package2, whilst it is signed by SW developing
department as package1.

The trick is here very easy, because it is the attacker, who
creates colliding packages. 

A toy scenario: 
The SW development department sends the source to the distributing
department. It adds a readme or help files and returns the complete
package (package1) to the SW development department. Of course, SW
development department runs package1.exe and checks byte by byte
that the original source files aren´t changed. Now it signs it.

Another one: 
The third party prepares a contract. The contract is sent to both
buyer (package1) and seller (package2) and signed by both parties. 

The structure of package1,2 is trivial. The first part is common,
the second part contains colliding blocks and the third part
contains the table of files file1 file2 file3 file4 file5 file6.
Package.exe decompresses file1 file2 file3 or file4 file5 file6
according to a specified bit value in the second part. 

Because now it is very quick to generate MD5 collision for any
chosen IV, it is possible to write the first part arbitrarily and
then generate a collision. 

Note that the number of files could be arbitrary and there are more
clever scenarios. The program serves only as a toy example how to
get arround the necessity of creating the second preimage.
Vlastimil Klima



---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com