find_md5_prefix_collision

A simple utility to facilitate finding MD5 prefix collisions.  The
prefix is required to be a multiple of 64 bytes.  The MD5 calculation
operates on 64 byte blocks so an appropriate initial vector can be
calculated quite easily.

To build, execute:

$ make

Program usage:

Usage: ./find_md5_prefix_collision [options] <file>
  -h, --help       print this usage and exit
  -v, --verbose    be more verbose
  -b, --badchars   check for bad characters
  -t, --tunnel     use Vlastimil Klima's md5_vk1_single
  -s, --seed <val> use 'val' as seed to md5_vk1_single


Included is the 'md5coll' program by Patrick Stach available from
http://www.stachliu.com/md5coll.c.  A couple of minor modifications
were made so that the calculated collisions are placed in a file.

An improved method that utilizes tunnels as described at
http://cryptography.hyperlink.cz/MD5_collisions.html is available.
However, you must retrieve the file yourself since the license doesn't
allow distribution or commercial use.

Do something like this:

$ wget http://cryptography.hyperlink.cz/2006/program_v1_pd.zip
$ unzip -o program_v1_pd.zip md5_vk1_single.c
$ touch md5_vk1_single.c
$ make

The tunnel approach is many times faster so it is recommended.  

The badchars option checks for characters that should be excluded so
that the prefix can be included in a HTML page, specifically a
Javascript string.

For example, to calculate a collision using the included rand.dat:

$ ./find_md5_prefix_collision --tunnel --seed EAB2D21D rand.dat 
found collisions using seed EAB2D21D;
file1=collision1_md5_EAB2D21D.BIN, file2=collision2_md5_EAB2D21D.BIN

$ for i in 1 2; \
  do cat rand.dat collision${i}_md5_EAB2D21D.BIN > file$i.dat; \
  done

$ md5 file1.dat file2.dat
MD5 (file1.dat) = 0f7fee4df9edf50537c6287d0b64692f
MD5 (file2.dat) = 0f7fee4df9edf50537c6287d0b64692f

$ sha1 file1.dat file2.dat
SHA1 (file1.dat) = fe10e7719adceaabef307043c9143ab6a49f0c3c
SHA1 (file2.dat) = 71a84fca2fc8ddfa7392aae8667944a84bb26111

Or, to generate a collision without "bad" characters: 

$ ./find_md5_prefix_collision -v -b -t -s 21213252 prefix.html
reading from file: prefix.html
file size: 64
calculating MD5 initial values
using seed: 0x21213252
...snipped...
found collisions using seed 21213254; 
file1=collision1_md5_21213254.BIN, file2=collision2_md5_21213254.BIN

$ for i in 1 2; do \
  cat prefix.html collision${i}_md5_21213254.BIN suffix.html > p${i}.html; \
  done

$ md5 p1.html p2.html
MD5 (p1.html) = 437bc978477414cc9b8f5e18e602e0ed
MD5 (p2.html) = 437bc978477414cc9b8f5e18e602e0ed

$ sha1 p1.html p2.html
SHA1 (p1.html) = 47106834a45a3cb157455c5cef8e958050412095
SHA1 (p2.html) = ce1fc4039e08eeaca2d07ca38daf4456111e8c2b


Compatibility:
Developed and tested on FreeBSD i386.  Compiles and runs on Linux i686.