Nytro Posted May 9, 2015 Report Posted May 9, 2015 How to make two binaries with the same MD5 hash One question I was asked when I demo'd creating two PHP files with the same hash is; does it work on compiled binaries? Well the answer is yes in fact that is where I first got the idea from, in this demo. That example uses a C program as both the target and also to do the binary manipulation, which slightly of obscures the way it works. It also makes use of an old very slow implementation on the Wang attack to generate the collisions. To better and more quickly show how it works for an upcoming talk I have created a really simple example using a PHP script to manipulate a binary once compiled. I have put all the code used here on github. Below is the super simple C program it compares two strings and if they don't match it prints out an ASCII art picture of an angel. If they do match you get a picture of a devil. [TABLE=class: lines highlight][TR][TD=class: line-numbers] [/TD][TD=class: line-data]#include <string.h>#include <stdio.h>#define DUMMY "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA" \ "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA" \ "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA" \ "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA" \ "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA" \ "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"int angel();int devil();char *dummya = DUMMY "A";char *dummyb = DUMMY "B";int main() { if (strcmp(dummya, dummyb) != 0) { return angel(); } else { return devil(); }}int angel() { fprintf(stdout, ". ,\n"); fprintf(stdout, ")). -===- ,((\n"); fprintf(stdout, "))). ,(((\n"); fprintf(stdout, "))))). .:::. ,((((((\n"); fprintf(stdout, "))))))))). :. .: ,(((((((('\n"); fprintf(stdout, "`))))))))))). : - : ,((((((((((((\n"); fprintf(stdout, "))))))))))))))))_:' ':_((((((((((((((('\n"); fprintf(stdout, " `)))))))))))).-' \\___/ '-._(((((((((((\n"); fprintf(stdout, " `))))_._.-' __)( )(_ '-._._(((('\n"); fprintf(stdout, " `))'---)___)))'\\_ _/'((((__(---'(('\n"); fprintf(stdout, " `))))))))))))|' '|(((((((((((('\n"); fprintf(stdout, " `)))))))))/' '\\((((((((('\n"); fprintf(stdout, " `)))))))| |((((((('\n"); fprintf(stdout, " `))))))| |(((((('\n"); fprintf(stdout, " /' '\\\n"); fprintf(stdout, " /' '\\\n"); fprintf(stdout, " /' '\\\n"); fprintf(stdout, " /' '\\\n"); fprintf(stdout, " '---..___..---'\\\n"); return 0;}int devil() { fprintf(stdout, " _.---**""**-.\n"); fprintf(stdout, "._ .-' /|`.\n"); fprintf(stdout, " \\`.' / | `.\n"); fprintf(stdout, " V ( ; \\\n"); fprintf(stdout, " L _.- -. `' \\\n"); fprintf(stdout, " / `-. _.' \\ ;\n"); fprintf(stdout, ": __ ; _ |\n"); fprintf(stdout, ":`-.___.+-*\"': ` ; .' `. |\n"); fprintf(stdout, " |`-/ `--*' / / /`.\\|\n"); fprintf(stdout, ": : \\ :`.| ;\n"); fprintf(stdout, "| | . ;/ .' ' /\n"); fprintf(stdout, ": : / ` :__.'\n"); fprintf(stdout, " \\`._.-' / |\n"); fprintf(stdout, " : ) : ;\n"); fprintf(stdout, " :----.._ | /\n"); fprintf(stdout, " : .-. `. /\n"); fprintf(stdout, " \\ `._ /\n"); fprintf(stdout, " /`- /\n"); fprintf(stdout, " : .'\n"); fprintf(stdout, " \\ ) .-'\n"); fprintf(stdout, " `-----*\"'\n"); return 0;}[/TD][/TR][/TABLE] view raw demo.c hosted with ? by GitHub It can be compiled with gcc and executed simply by doing[TABLE][TR][TD=class: gutter]123[/TD][TD=class: code]longEgg$ gcc -o demo ./demo.clongEgg$ chmod a+x demolongEgg$ ./demo[/TD][/TR][/TABLE] Executing the program will print out the angel since the two strings differ in the last letter. Now we have our compiled binary we need to do a bit of mucking about with it. What we are going to do is insert a MD5 collision into the long string of A's of the dummy text. We only need to insert two blocks of 64 bytes but we need to insert it at the beginning of a block i.e. when the byte length is a multiple of 64 bytes. [TABLE=class: lines highlight][TR][TD=class: line-numbers] [/TD][TD=class: line-data] <?phpinclude __DIR__.'/MD5.php';$inFile = __DIR__.'/demo';$dummyText = str_pad('', 64, 'A');function replaceDummyText($input, $replacment, $position){ return substr_replace($input, $replacment, $position, strlen($replacment));}function findDummyText($filestring, $dummyText){ $pos = 0; $chunks = str_split($filestring, 64); foreach ($chunks as $chunk) { if ($chunk == $dummyText) { break 1; } $pos++; } return $pos*64;}// read in the original binary file in$filestring = file_get_contents($inFile);// find the place where we have the dummy string and its at start of a 64 byte block$pos = findDummyText($filestring, $dummyText);printf('I want to replace %d bytes at position %d in %s'.PHP_EOL, 128, $pos, $inFile);$firstPart = substr($filestring, 0, $pos);//find the IV up to the point we want to insert then print that out$iv = md5_hash($firstPart);printf('Chaining variable up to that point is %s'.PHP_EOL, $iv);if (!file_exists(__DIR__.'/a')) { print('Run fastcoll to generate a 2 block collision in MD5'.PHP_EOL); return;}// replace the dummy text at the correct location$good = replaceDummyText($filestring, file_get_contents(__DIR__.'/a'), $pos);$bad = replaceDummyText($filestring, file_get_contents(__DIR__.'/b'), $pos);// find the secod dummy string$secondDummyTextStart = strpos($good, str_pad('', 191, 'A'));// serach back from where we inserted the collision first time so we can grab the whole// 192 bytes and use it to replace the second stringwhile ('A' == substr($filestring, $pos-1, 1)) { --$pos;}//the 192 butes of str1$replacement = substr($good, $pos, 192);// replace str1 with 192 bytes cut from of the files// the file it came from will then compare str1 and str2 to 0$good = replaceDummyText($good, $replacement, $secondDummyTextStart);file_put_contents(__DIR__.'/devil', $good);printf('Just output new file %s with hash %s'.PHP_EOL, __DIR__.'/devil', md5($good));$bad = replaceDummyText($bad, $replacement, $secondDummyTextStart);file_put_contents(__DIR__.'/angel', $bad);printf('Just output new file %s with hash %s'.PHP_EOL, __DIR__.'/angel', md5($bad));[/TD][/TR][/TABLE] view raw long_egg.php hosted with ? by GitHub When we run the php script over it the first time it finds such a location and calculates the value of the four chaining variables of MD5 at that point in the file. It prints out the hex values concatenated together as a hash. We can now take that value and search for an MD5 collision with that initial state. The best MD5 collision finder is Marc Stevens fastcoll. It can typically find collisions in a couple of seconds using a a variant of the Wang attack. After downloading it you will need to compile it. There should be a Makefile for it in the code on github. Running it specifying the initial state and output files is shown below.[TABLE][TR][TD=class: gutter]12345[/TD][TD=class: code]longEgg$ wget https://www.win.tue.nl/hashclash/fastcoll_v1.0.0.5-1_source.ziplongEgg$ unzip fastcoll_v1.0.0.5-1_source.ziplongEgg$ makelongEgg$ chmod a+x fastcolllongEgg$./fastcoll -i c15cfe39c40e47f5b8ae31e6658fd1bd -o a b[/TD][/TR][/TABLE] The -o option specifies the output files and so will create two new files a and b which contain 2 blocks of binary data. These blocks only work as MD5 collisions within the binary at that point. Running the php script for a second time will create two copies of the original compiled binary with the collisions inserted in the appropriate places. [TABLE][TR][TD=class: gutter]1234[/TD][TD=class: code]longEgg$ I want to replace 128 bytes at position 6528 in colliding_binaries/demolongEgg$ Chaining variable up to that point is c15cfe39c40e47f5b8ae31e6658fd1bdlongEgg$ Just output new file /Users/nmchugh/longEgg/devil with hash dea9dc288b6c56626997ce86ca8eb6dalongEgg$ Just output new file /Users/nmchugh/longEgg/angel with hash dea9dc288b6c56626997ce86ca8eb6da[/TD][/TR][/TABLE] So now we have created two more files angel and devil. Running each of those should give different outputs. But they should have the same MD5 value. [TABLE][TR][TD=class: gutter]123[/TD][TD=class: code]longEgg$ md5 angel devil MD5 (angel) = dea9dc288b6c56626997ce86ca8eb6daMD5 (devil) = dea9dc288b6c56626997ce86ca8eb6da[/TD][/TR][/TABLE]Posted by Nathaniel McHugh at 1:38 PM Sursa: http://natmchugh.blogspot.co.uk/2015/05/how-to-make-two-binaries-with-same-md5.html Quote
