当我如何使用相同的 MD5 哈希创建两个 PHP 文件时，有人问我一个问题：它适用于编译的二进制文件吗？
答案是肯定的，事实上，这就是我在这个演示中第一次得到这个想法的地方。
该示例使用 C 程序作为目标，并执行二进制操作，这略微模糊了它的工作方式。它还利用了 Wang 攻击的一个非常缓慢的旧实现来生成碰撞。为了更好、更快速地展示它是如何为即将到来的演讲工作的，我创建了一个非常简单的示例，使用 PHP 脚本在编译后操作二进制文件。
我已经把这里使用的所有代码都放在了github上。
下面是一个超级简单的 C 程序，它比较两个字符串，如果它们不匹配，它会打印出天使的 ASCII 艺术图片。如果它们确实匹配，你会得到一张魔鬼的照片。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 |
#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; } |
它可以用 gcc 编译并执行，只需执行程序将打印出天使，因为两个字符串在最后一个字母中不同。
现在我们有了编译的二进制文件，我们需要对它做一些处理。我们要做的是将 MD5 冲突插入到虚拟文本的长串 A 中。我们只需要插入两个 64 字节的块，但我们需要将其插入到块的开头，即当字节长度是 64 字节的倍数时。
|
1 2 3 |
longEgg$ gcc -o demo ./demo.c longEgg$ chmod a+x demo longEgg$ ./demo |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 |
<?php include __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 string while ('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)); |
当我们第一次在它上运行 php 脚本时，它会找到这样的位置并计算文件中该点 MD5 的四个链接变量的值。它打印出连接在一起的十六进制值作为哈希值。
|
1 2 3 4 |
$ php long_egg.php I want to replace 128 bytes at position 3008 in /var/www/html/md5collisions/longEgg/demo Chainring variable up to that point is <strong>a2330164cee76a94d8779f4a2bdfa6a2</strong> Run fastcoll to generate a 2 block collision in MD5 |
现在，我们可以获取该值并搜索与该初始状态的 MD5 冲突。最好的 MD5 碰撞查找器是 Marc Stevens fastcoll。它通常可以在几秒钟内使用 Wang 攻击的变体找到碰撞。下载后，您需要对其进行编译。github 上的代码中应该有一个 Makefile。运行它指定初始状态和输出文件如下所示。
-o 选项指定输出文件，因此将创建两个新文件 a 和 b，其中包含 2 个二进制数据块。此时，这些块仅作为二进制文件中的 MD5 冲突起作用。第二次运行 php 脚本将创建原始编译二进制文件的两个副本，并将冲突插入到适当的位置。
所以现在我们又创建了两个文件，天使和魔鬼。运行其中每个都应该给出不同的输出。
但它们应该具有相同的 MD5 值。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
$ wget https://www.win.tue.nl/hashclash/fastcoll_v1.0.0.5-1_source.zip $ unzip fastcoll_v1.0.0.5-1_source.zip $ make $ chmod a+x fastcoll $ ./fastcoll -i <strong>a2330164cee76a94d8779f4a2bdfa6a2</strong> -o a b MD5 collision generator v1.5 by Marc Stevens (http://www.win.tue.nl/hashclash/) Using output filenames: 'a' and 'b' Using initial value: a2330164cee76a94d8779f4a2bdfa6a2 Generating first block: ................................ Generating second block: S11................................... Running time: 7.81061 s 再次运行 long_egg.php 会产生 devil 和 angel 文件 |
|
1 2 3 4 5 |
$ php long_egg.php I want to replace 128 bytes at position 3008 in /var/www/html/md5collisions/longEgg/demo Chainring variable up to that point is <strong>a2330164cee76a94d8779f4a2bdfa6a2</strong> Just output new file /var/www/html/md5collisions/longEgg/devil with hash 7422a71a481c82148d65fe6ef473ae66 Just output new file /var/www/html/md5collisions/longEgg/angel with hash 7422a71a481c82148d65fe6ef473ae66 |
$ chmod +x angel devil
|
1 2 3 4 5 6 7 |
$ openssl md5 angel devil MD5(angel)= 7422a71a481c82148d65fe6ef473ae66 MD5(devil)= 7422a71a481c82148d65fe6ef473ae66 $ openssl sha1 angel devil SHA1(angel)= 1f331a6428652fda09cbd6da559c869eb68ca55e SHA1(devil)= 0830389dad66341145289b77359a320c6606f620 |
如果 运行 fastcoll 缺少库 libboost_filesystem.so.1.75.0 ，需要 找到库，加入路径：
|
1 |
export LD_LIBRARY_PATH=/usr/local/lib/:$LD_LIBRARY_PATH |