1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The messages in the article are processed without padding. When you call the md5() function in PHP it performs padding, so you won't get the same hashes as in the article. If your code is working correctly then the two messages will still collide because the collision occurs before the padding. So my suggestion would be to try both messages and check that you get the same hash for both. $\endgroup$ – user13741 Mar 6 '15 at 18:22
  • $\begingroup$ I tested it. Hashes are not the same. $\endgroup$ – user40602 Mar 6 '15 at 18:35
  • $\begingroup$ Just a question did the representation Little or Big Endian has been considered ? Some trouble sometimes are resolved when changing the representation on different machine. $\endgroup$ – Robert NACIRI Mar 6 '15 at 21:47
  • 1
    $\begingroup$ @RobertNACIRI As a matter of fact, the first published "MD5 collision" was actually not really an MD5 collision at all, because the authors had mixed up byte ordering. By reversing the byte ordering of the published collision, the result would produce a collision not for MD5, but rather for MD5 with the IV replaced with an IV with opposite byte ordering. A real collision was published a few days later, so ensure the one you are looking at is the correct collision. $\endgroup$ – kasperd Mar 7 '15 at 0:48
  • $\begingroup$ Ah, yes, try this paper, table 2. I've been able to successfully run result for H*, funny enough after reverting the hex values 4 bytes at a time. $\endgroup$ – Maarten - reinstate Monica Mar 7 '15 at 1:56
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I had 2 bash scripts that had the same hash but printed out something differently. Pretty good practice. Then I archived them and McAfee happily removed the entire backup archive because it thought it had found a virus (instead of just putting the file in the zip archive in quarantine). Thank you McAfee & IT dept... $\endgroup$ – Maarten - reinstate Monica Mar 7 '15 at 2:27
  • $\begingroup$ It’s their way of thanking you for using their product… ;) Honestly, stuff like that is one of the reasons I abandoned them. (Besides… from an infosec perspective, their product should’ve put your whole ZIP into quarantine. But then again, Let’s not expect more from that company than it is able to handle.) $\endgroup$ – e-sushi Mar 7 '15 at 20:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.