Problem with testing MD5 collisions 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:

&lt;?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);

?&gt;


The output hash is 8da3a17b43e0e134bdc17557ffef15ff instead of the 9603161ff41fc7ef9f65ffbca30f9dbf mentioned in the article.
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:

&lt;?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;

?&gt;


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).