Problem with testing MD5 collisions

Question

I am trying to test MD5 collisions presented in “Collisions for Hash Functions MD4, MD5, HAVA” (PDF) by Xiaoyun Wang, Dengguo Feng, Xuejia Lai, Hongbo Yu; 2004.

I wrote a PHP script to test it, but it doesn't produce the expected hash output. I tested everything several times and found no errors in my code. I don't know what is wrong. Please help me to find the reason and test the collisions.

Here is my PHP script:

<?php

$M='2dd31d1 c4eee6c5 69a3d69 5cf9af98 87b5ca2f ab7e4612 3e580440 897ffbb8
634ad55 2b3f409 8388e483 5a417125 e8255108 9fc9cdf7 f2bd1dd9 5b3c3780';

$N1='d11d0b96 9c7b41dc f497d8e4 d555655a c79a7335 cfdebf0 66f12930 8fb109d1
797f2775 eb5cd530 baade822 5c15cc79 ddcb74ed 6dd3c55f d80a9bb1 e3a7cc35';

function fix_word_length($str) { //we need this because some hex words u see r less than 8 chars (e.g. the first hex word: 2dd31d1) / this pads them on the left with '0's

    return str_pad($str, 8, '0', STR_PAD_LEFT);

}

function convert2binary($str) {

    $str=str_replace("\n", ' ', $str); //replaces line feed chars with space
    $str=explode(' ', $str); //this converts each hex word to an array element / sorry for the name, but str is really an array after this operation
    $str=array_map('fix_word_length', $str); // pad hex words with a length less than 8 chars by '0's on their left
    $str=implode('', $str); //joins all hex words together again (with spaces between them removed). / str is now a string again
    return pack('H*', $str); // convert hex encoding to raw/binary and return it

}

$M=convert2binary($M);
$N1=convert2binary($N1);

echo md5($M.$N1);

?>

The output hash is 8da3a17b43e0e134bdc17557ffef15ff instead of the 9603161ff41fc7ef9f65ffbca30f9dbf mentioned in the article.

Answer 1

This was pretty vexing, but for some reason I could only create the "big endian" results given by table 2 in this paper.

I get the same result as you for the first message ($M.$N0) : 8da3a17b43e0e134bdc17557ffef15ff and a different value for the second message.

---

The following code seems to work for a test vector given in table 2:

<?php

$M0='02dd31d1 c4eee6c5 069a3d69 5cf9af98 87b5ca2f ab7e4612 3e580440 897ffbb8
         0634ad55 02b3f409 8388e483 5a417125 e8255108 9fc9cdf7 f2bd1dd9 5b3c3780';
    $M1='d11d0b96 9c7b41dc f497d8e4 d555655a c79a7335 0cfdebf0 66f12930 8fb109d1
     797f2775 eb5cd530 baade822 5c15cc79 ddcb74ed 6dd3c55f d80a9bb1 e3a7cc35';

$N0='02dd31d1 c4eee6c5 069a3d69 5cf9af98 07b5ca2f ab7e4612 3e580440 897ffbb8
         0634ad55 02b3f409 8388e483 5a41f125 e8255108 9fc9cdf7 72bd1dd9 5b3c3780'; 
    $N1='d11d0b96 9c7b41dc f497d8e4 d555655a 479a7335 0cfdebf0 66f12930 8fb109d1
     797f2775 eb5cd530 baade822 5c154c79 ddcb74ed 6dd3c55f 580a9bb1 e3a7cc35'; 


function convert2binary($D) {
      // removes whitespace
      $D = preg_replace('/\s+/', '', $D);
      // reorders 4 bytes at the time
      $D = preg_replace('/(..)(..)(..)(..)/', '\4\3\2\1', $D);
      // hex2bin for older PHP
      $D = pack('H*', $D);
      return $D;
}

$M0 = convert2binary($M0);
$M1 = convert2binary($M1);
echo md5($M0.$M1) . PHP_EOL;

$N0 = convert2binary($N0);
$N1 = convert2binary($N1);
echo md5($N0.$N1) . PHP_EOL;

?>

Which should show the result:

a4c0d35c95a63a805915367dcfe6b751
a4c0d35c95a63a805915367dcfe6b751

I took the liberty to perform the padding manually. There seems little need to creating a specialized method for this (and my PHP skills leave something to be desired).

---

Note that cryptographers are often pretty sloppy when it comes to these kind of things, the test vectors don't seem very well defined (but at least they are documented).