说在前面
这个lab的题目在某些情况下可能被改版成了这样：
①. 使用md5collgen生成两个MD5值相同的文件，并利用bless十六进制编辑器查看输出的两个文件，描述你观察到的情况；
②. 参考Lab3_task2.c的代码，生成两个MD5值相同但输出不同的两个可执行文件。
③. 参考Lab3_task3.c的代码，生成两个MD5值相同但代码行为不相同的可执行文件。
④. 回答问题：通过上面的实验，请解释为什么可以做到不同行为的两个可执行文件具有相同的MD5值？
但并不影响，内容相似，仍可参考本博客进行学习。
实验环境
虚拟机环境：SEED-labs-ubuntu 20.04
使用软件：Oracle VM VirtualBox7.1.0
实验用到的工具：md5collgen，Bless Hex editor
虚拟机安装配置可参考该博客： SEED-labs-ubuntu 20.04 虚拟机环境搭建
实验环境初始化
在项目网站上根据自己的设备类型下载对应的 Labsetup文件，解压后移动到虚拟机中
项目网站 SEED Labs 2.0 MD5 Collision Attack Lab
注：该文件夹中只有一个 md5collgen
实验详情
TASK1
任务描述
在这项任务中，我们将生成两个具有相同 MD5 哈希值的不同文件。这两个文件的开头部分必须相同，即共享相同的前缀。我们可以使用 md5collgen 程序来实现这一目标，该程序允许我们提供一个包含任意内容的前缀文件。该程序的工作原理如图 1 所示。下面的命令为给定的前缀文件 prefix.txt 生成两个输出文件 out1.bin 和 out2.bin：
$ md5collgen -p prefix.txt -o out1.bin out2.bin
我们可以使用 diff 命令检查输出文件是否不同。我们还可以使用 md5sum 命令检查每个输出文件的 MD5 哈希值。请参阅以下命令。
$ diff out1.bin out2.bin
$ md5sum out1.bin
$ md5sum out2.bin
由于 out1.bin 和 out2.bin 是二进制文件，我们无法使用文本查看器程序（如 cat 或更多）来查看它们；我们需要使用二进制编辑器来查看（和编辑）它们。我们已经在虚拟机中安装了一个名为 bless 的十六进制编辑器软件。请使用这种编辑器查看这两个输出文件，并描述你的观察结果。此外，您还应回答以下问题：
- 问题 1：如果前缀文件的长度不是 64 的倍数，会发生什么情况？
- 问题 2：创建一个长度正好为 64 字节的前缀文件，然后再次运行碰撞工具，看看会发生什么。
- 问题 3：md5collgen 生成的数据（128 字节）在两个输出文件中是否完全不同？请找出所有不同的字节。
任务分析
从本质上来说，MD5值是有限的（2的128次方个），然而程序是无穷的，因此两个不同行为程序完全可能有相同的md5值，碰撞不可避免。本题便是利用 MD5碰撞生成器 md5collgen 来制造MD5碰撞来生成两个MD5值相同但内容不同的文件。
MD5 碰撞生成器：简单来说，用户选择一个前缀文件（64位的倍数长度），碰撞生成器根据选定的前缀生成两个不同的文件，这两个文件在前缀之后的内容不同，但整个文件的MD5哈希值相同。
根据MD5碰撞生成器的性质，我们只需撰写一个前缀文件，然后用其生成两个文件即可完成任务。
完成步骤
◇ 使用md5collgen生成两个MD5值相同的文件
1.编写前缀文件 prefix.txt，为后面的实验做准备。
2.输入下面的命令使用 md5collgen 将前缀文件 prefix.txt 作为前缀生成两个文件 out1.bin out2.bin。
3.通过下面三个命令对out1.bin 和 out2.bin 两个文件进行对比，来检查利用md5collgen 和 前缀文件 prefix.txt 生成的这两个文件 是不一样的文件且MD5值相同。通过输出结果我们可以看出 out1.bin 和 out2.bin 两个文件是不一样的，但是其MD5编码是一样的。证明我们成功使用 md5collgen 生成两个 MD5值相同的文件。
◇观察输出的两个MD5值相同的文件
注：题目建议使用虚拟机中的 Bless Hex editor 来以十六进制的形式查看两个输出的文件。但是作为一个程序员更希望能够在终端中解决一切，所以我在这里补充一个方法，使用 hexdump 命令也可以以十六进制和ASCII码形式显示二进制文件的内容。
hexdump -C out1.bin
在后面的实验中经常会对文件的内容进行比较，但是肉眼比较看起来会很麻烦，这里补充一个在线的文本比较工具，可以帮助我们快速进行文本比较。
在线文本比较工具
1.首先观察两个二进制文件，观察后发现两个文件内容确实不相同，再次证明两个文件确实是两个内容不相同，MD5值相同的文件。
Q1：如果您的前缀文件的长度不是 64 的倍数，会发生什么情况？
我在本任务中撰写的 prefix.txt 的内容长度为6 不为 64的倍数。用 Bless Hex editor 打开两个输出文件 out1.bin 和 out2.bin。观察后我们会发现，输出文件会自动填充‘0’，将前缀部分填充至长度为64的倍数长度。
Q2：创建一个正好有 64 字节的前缀文件，然后再次运行碰撞工具，看看会发生什么。
1.按照题目要求重新撰写一个精确的64位前缀文件 prefix.txt，如下图所示。
注： 仔细看的话，可以发现我的前缀文件里面只输入了63个字符，并不是题目要求的64个。其实我一开始是在前缀文件中输入了64个字符的，但是用Bless Hex editor打开前缀文件输出的两个文件后，可以看到在前缀部分中我输入的最后一个字符后多了一个 0X0A 相当于在前缀文件中输入了65个字符，并且在该字符后一直补零至前缀部分的长度变为128位（64位的2倍）。
查阅资料后得知，Linux 使用换行符 0x0A（Line Feed, LF）表示行的结束，在文本文件中，每一行通常会以一个换行符结束，这是一种约定，旨在确保文件的标准化和易于处理。所以在文本文件中我们只需要输入63个字符，再加上一个默认的换行符就可以得到一个精确的64位的前缀文件。
2.使用命令使用 md5collgen 将64位的前缀文件 prefix.txt 作为前缀生成两个文件 out1.bin out2.bin。可以观察到现在前缀部分不会补零了。
Q3：由 md5collgen 生成的两个输出文件的数据（128 字节）完全不同吗？请确定所有不同的字节。
仔细观察后可知，两个输出文件并不是所有的数据（128字节）都不同。
小结： 总结一下观察的结果，我们可以发现两文件的前缀相同，文件内容有少许不同。我们可以通过 md5collgen的原理来理解这一现象，当输入的文件长度不是64字节的倍数时先补0 使长度为64字节的倍数，再添加128字节的数据分别生成两个MD5值相同的输出文件，这两个输出文件就是在这128字节中存在部分差异。
TASK2
任务描述
在本任务中，我们将尝试了解 MD5 算法的一些特性。这些特性对于我们在本实验室中开展进一步的任务非常重要。MD5 是一种相当复杂的算法，但从高层来看，它并不复杂。如图 2 所示，MD5 将输入数据分成 64 字节的数据块，然后在这些数据块上迭代计算哈希值。MD5 算法的核心是一个压缩函数，它有两个输入，一个是 64 字节的数据块，另一个是上一次迭代的结果。压缩函数会产生一个 128 位的 IHV，即 “中间哈希值”；然后将此输出输入下一次迭代。如果当前迭代是最后一次迭代，IHV 将是最终哈希值。第一次迭代的 IHV 输入（IHV0）是一个固定值。
根据 MD5 的工作原理，我们可以推导出 MD5 算法的以下属性：给定两个输入 M 和 N，如果 MD5(M) = MD5(N)，即 M 和 N 的 MD5 哈希值相同，那么对于任意输入 T，MD5(M || T) = MD5(N ||T)，其中 || 表示连接。
也就是说，如果输入 M 和 N 具有相同的哈希值，那么给它们添加相同的后缀 T 就会得到两个具有相同哈希值的输出。这一特性不仅适用于 MD5 哈希算法，也适用于许多其他哈希算法。在本任务中，你的任务是设计一个实验来证明 MD5 的这一特性。
您可以使用 cat 命令将两个文件（二进制文件或文本文件）连接成一个文件。下面的命令将文件 2 的内容与文件 1 的内容连接起来，并将结果放到文件 3 中。
$ cat file1 file2 > file3
任务分析
任务内容简单来说，可以分为三点：
- 找到两个内容不同但是 MD5 值相同的文件。
- 给找到的两个文件拼接相同的后缀。
- 验证拼接后的两个文件 MD5 值相同。
第一点很好解决，因为我们在完成第一问时就生成了两个内容不同但是 MD5值相同的文件，out1.bin 和 out2.bin。
第二点，我们直接加上相同的后缀即可。
第三点，使用第一问的命令进行检查即可。
完成步骤
1.输入下面的命令后，发现MD5值相同，即证明完成。
TASK3
任务描述
在这项任务中，您将得到以下 C 程序。你的任务是创建两个不同版本的程序，使其 xyz 数组的内容不同，但可执行文件的哈希值相同。
#include <stdio.h>
unsigned char xyz[200] = {
/* The actual contents of this array are up to you */
};
int main()
{
int i;
for (i=0; i<200; i++){
printf("%x", xyz[i]);
}
printf("\n");
}
您可以选择在源代码级别工作，即生成上述 C 程序的两个版本，这样在编译后，它们对应的可执行文件具有相同的 MD5 哈希值。不过，直接在二进制级别上工作可能更容易。你可以在 xyz 数组中放入一些任意值，将上述代码编译成二进制。然后使用十六进制编辑器直接在二进制文件中修改 xyz 数组的内容。
要在二进制文件中找到数组内容的存储位置并不容易。不过，如果我们在数组中填入一些固定值，就能很容易地在二进制文件中找到它们。例如，下面的代码在数组中填充了 0x41，这是字母 A 的 ASCII 值。
unsigned char xyz[200] = {
0x41, 0x41, 0x41, 0x41, 0x41, 0x41, 0x41, 0x41, 0x41, 0x41,
0x41, 0x41, 0x41, 0x41, 0x41, 0x41, 0x41, 0x41, 0x41, 0x41,
0x41, 0x41, 0x41, 0x41, 0x41, 0x41, 0x41, 0x41, 0x41, 0x41,
... (omitted) ...
0x41, 0x41, 0x41, 0x41, 0x41, 0x41, 0x41, 0x41, 0x41, 0x41,
}
指导: 在数组内部，我们可以找到两个位置，从这里可以将可执行文件分为三部分：前缀、128 字节区域和后缀。前缀的长度必须是 64 字节的倍数。文件划分示意图见图 3。
我们可以在前缀上运行 md5collgen，生成两个具有相同 MD5 哈希值的输出。让我们用 P 和 Q 表示这些输出的第二部分（各 128 字节）（即前缀后的部分）。因此，我们可以得到以下结果：
MD5 (prefix || P) = MD5 (prefix || Q)
根据 MD5 的属性，我们可以知道，如果在上述两个输出中添加相同的后缀，结果数据也将具有相同的哈希值。基本上，对于任何后缀都是如此：
MD5 (prefix || P || suffix) = MD5 (prefix || Q || suffix)
因此，我们只需用 P 和 Q 替换数组（两个分割点之间）的 128 个字节，就能创建两个具有相同哈希值的二进制程序。它们的结果是不同的，因为它们各自打印出了内容不同的数组。
工具： 你可以使用 bless 查看二进制可执行文件，并找到阵列的位置。在分割二进制文件时，我们可以使用一些工具从特定位置分割文件。head 和 tail 命令就是这类有用的工具。你可以查看它们的使用手册，学习如何使用它们。下面我们举三个例子：
$ head -c 3200 a.out > prefix
$ tail -c 100 a.out > suffix
$ tail -c +3300 a.out > suffix
上述第一条命令将 a.out 的前 3200 字节保存为前缀。第二条命令将 a.out 的最后 100 个字节保存到 suffix 中。第三条命令将 a.out 文件从第 3300 个字节开始到结尾的数据保存到 suffix 中。通过这两条命令，我们可以将二进制文件从任意位置分割成若干块。如果需要将某些片段粘合在一起，我们可以使用 cat 命令。
如果使用 bless 将一个二进制文件中的数据块复制并粘贴到另一个文件中，菜单项 “Edit -> Select Range ”非常方便，因为你可以使用起点和范围选择数据块，而不用手动计算选择了多少字节。
任务分析
由上一个任务可知，我们可以使用一个相同的前缀来生成内容不同但MD5值相同的两个文件。我们可以参考这个原理来完成本任务。
想要输出的内容不同，只需要让我们的数组的内容不同，因此我们可以把在数组之前的内容截取出来作为前缀，再利用MD5碰撞生成器生成两个MD5值相同的文件，将他们在前缀后随机生成的128字节的内容作为新的数组的内容，再接上原本数组后面的内容。实现生成两个MD5值相同但输出不同的可执行文件。
完成步骤
1.按照题目提示撰写文件 Lab3_task2.c 如下图所示。
2. 编译并运行该文件，输出正常。
3.用 Bless Hex editor 打开编译后的文件，找到数组所在位置。
4.将数组前的内容提取出来做前缀，数组后的内容提取出来做后缀。即 0x0000-0x301f 为 prefix，0x30e8-425f为 suffix。十六进制转换为十进制计算后得到，前缀为前12319个字节，后缀为从12521个字节往后的内容。使用下面的命令将前缀 prefix 和后缀 suffix 提取出来。
注： 这里提供一个在线进制转换工具 在线进制转换工具
5.使用 prefix 前缀文件使用 md5collgen 工具生成两个输出文件 out1.bin 和 out2.bin。
6. 我们模仿第一问的方式对这两个输出文件进行检查，看看是否符合我们的设想。检查后可以确认，它们是两个内容不同但MD5值相同的文件。并且可以观察到它们各自生成的128字节的内容是不同的，符合我们的设想。
7. 将之前提取的后缀文件 suffix 链接到这两个输出文件的尾部得到 test1 和 test2。
8. 运行两个文件，可以看到输出的结果不同。
注： 在运行时，我们会遇到 Permission denied 的报错，这是因为我们没有给文件设置执行权限。可使用命令来添加权限：
chmod +x filename
9.检查两个文件的 MD5值，发现是一样的。至此我们成功生成两个MD5值相同但输出不同的两个可执行文件。
TASK4
任务描述
在前面的任务中，我们成功创建了两个程序，它们的 MD5 哈希值相同，但行为却不同。不过，它们的区别仅在于打印出的数据不同，执行的指令序列仍然相同。在这项任务中，我们希望实现一些更重要、更有意义的目标。
假设您创建了一个能做好事的软件。你把软件送到一个值得信赖的权威机构进行认证。权威机构对你的软件进行了全面测试，得出结论认为你的软件确实在做好事。权威机构会向你颁发证书，证明你的程序是好的。为防止您在获得证书后更改程序，证书中还包括程序的 MD5 哈希值；证书由权威机构签名，因此您不能更改证书或程序上的任何内容，否则签名无效。
您想让自己的恶意软件获得权威机构的认证，但如果只是将恶意软件发送给权威机构，您实现这一目标的可能性为零。不过，您注意到权威机构使用 MD5 生成哈希值。你有了一个想法。你计划编写两个不同的程序。一个程序会一直执行良性指令并做好事，而另一个程序则会执行恶意指令并造成破坏。你要想办法让这两个程序共享相同的 MD5 哈希值。
然后，您将良性版本发送给权威机构进行认证。由于该版本做了好事，它将通过认证，你将获得一份包含良性程序哈希值的证书。由于你的恶意程序具有相同的哈希值，因此该证书对你的恶意程序也有效。因此，您已成功为恶意程序获取了有效证书。如果其他人相信权威机构颁发的证书，他们就会下载你的恶意程序。
本任务的目标是发起上述攻击。也就是说，你需要创建两个共享相同 MD5 哈希值的程序。但是，一个程序将始终执行良性指令，而另一个程序将执行恶意指令。在您的工作中，执行什么良性/恶意指令并不重要；只要证明这两个程序执行的指令是不同的就足够了。
指导： 创建两个完全不同的程序来生成相同的 MD5 哈希值是相当困难的。md5collgen 生成的两个哈希对齐程序需要共享相同的前缀；此外，正如我们从前面的任务中看到的，如果我们需要在 md5collgen 生成的输出中添加一些有意义的后缀，那么添加到两个程序中的后缀也需要相同。这就是我们使用的 MD5 碰撞生成程序的局限性。虽然有其他更复杂、更先进的工具可以解除某些限制，例如接受两个不同的前缀 [2]，但它们需要更强的计算能力，因此不在本实验的研究范围内。我们需要找到一种方法，在限制范围内生成两个不同的程序。
实现上述目标的方法有很多。我们提供了一种方法作为参考，但鼓励学生提出自己的想法。教师可以考虑奖励学生自己的想法。在我们的方法中，我们创建了两个数组 X 和 Y。我们比较这两个数组的内容；如果它们相同，则执行良性代码；否则，执行恶意代码。请看下面的伪代码：
Array X;
Array Y;
main()
{
if(X’s contents and Y’s contents are the same)
run benign code;
else
run malicious code;
return;
}
我们可以用一些值来初始化数组 X 和 Y，这些值可以帮助我们找到它们在可执行二进制文件中的位置。我们的任务是更改这两个数组的内容，从而生成具有相同 MD5 哈希值的两个不同版本。在一个版本中，X 和 Y 的内容相同，因此良性代码会被执行；在另一个版本中，X 和 Y 的内容不同，因此恶意代码会被执行。我们可以使用与任务 3 中类似的技术来实现这一目标。图 4 展示了两个版本的程序。
从图 4 中我们可以知道，只要相应地生成 P 和 Q，这两个二进制文件就具有相同的 MD5 哈希值。在第一个版本中，我们使数组 X 和 Y 的内容相同，而在第二个版本中，我们使它们的内容不同。因此，我们只需改变这两个数组的内容，而无需改变程序的逻辑。
任务分析
我们参考题目提供的代码，程序的运行逻辑为，当两个字符串相同时执行善意代码，当两个字符串不相同时执行恶意代码。所以我们的任务应该是生成两个可执行文件，一个当中的两个字符串相同，另一个当中的两个字符串不相同。我们可以将第一个字符串之前的内容截取出来作为前缀，使用MD5碰撞发生器生成两个MD5值相同的文件，将其后生成的128位的字符串作为新的第一个字符串，并将原本第一个字符串后面的内容拼接到新生成的两个文件上，并根据需要修改拼接部分当中的第二个字符串的内容。从而完成生成两个MD5值相同但代码行为不相同的可执行文件的任务。
完成步骤
注： 在这一问中需要寻找某一范围内64的倍数。可以使用下面的python代码辅助寻找。
left = xxx
right = xxx
for i in range(left,right+1):
if i%64==0:
print(i)
1.参考题目提供的代码，构造原始代码 Lab3_task3.c。X和Y两个字符串内容一样。当字符串相同时，执行良性代码；当字符串不同时，执行恶意代码。
2. 编译并运行该文件。可以看到现在两个字符串内容相同，执行善意代码。
3.用 Bless Hex editor 打开编译好的可执行文件，找到两个字符串的位置。我们可以看到两个字符串之间隔了一些0（共24字节）。
4.这里由于我们要关心打印的内容，所以不能像上一任务一样直接去截取前缀，让系统自动补全 0 至为64的倍数，所以我们在截取时要使截取的长度为64的倍数。0x3020-0x30e8 为第一个字符串的范围，0x3020转换为10进制为12320，距其最近的64的倍数为12352，所以我们截取前12352个字节为 prefix。在截取前缀后，我们使用 md5collgen 工具生成两个 MD5值相同的输出文件 prefix1 和 prefix2。
5. 我们截取第一个字符串之后的内容为后缀 suffix ，为保证我们空出来给第一个字符串的内容的长度为128字节，与由prefix生成的两个输出文件后的生成的部分的长度 128字节相同，我从 12481的位置开始截取后缀。
6. 将截取的后缀文件与刚生成的 prefix1 和 prefix2 拼贴。
7.在 bless 中编辑 prefix1 和 prefix2。使prefix1 中的 x 与 y 相同；使 prefix2 中的 x 和 y 不相同。为了保证两个文件的MD5值是相同的，我们需要保证它们的 prefix 和 suffix 部分的值是相同的，如下图所示，将红色框的部分（prefix1的x，和prefix1的y，prefix2的y）均替换为 prefix1 的 x 的值。
注： 在使用 bless hex editor 时我发现可以直接在其中编辑二进制文件，所以我没有使用各种裁剪拼贴的方式，而是直接在 bless 进行编辑完成的后面的步骤。
把prefix1 的 y 部分内容替换成 x 部分的内容。
把prefix2 的 y 部分内容替换成 prefix1 的 x 部分的内容。
8.运行修改后的 prefix1 和 prefix2 后发现，结果符合我们的预期。
9. 检查两个文件的MD5值，发现相同，至此我们成功生成两个MD5值相同但代码行为不相同的可执行文件。
参考资料
[1] John Black, Martin Cochran, and Trevor Highland. A study of the md5 attacks: Insights and improvements. In Proceedings of the 13th International Conference on Fast Software Encryption, FSE’06, pages
262–277, Berlin, Heidelberg, 2006. Springer-Verlag.
[2] Marc Stevens. On collisions for md5. Master’s thesis, Eindhoven University of Technology, 6 2007.
[3] Marc Stevens, Elie Bursztein, Pierre Karpman, Ange Albertini, and Yarik Markov. The first collision
for full SHA-1. CWI Amsterdam and Google Research, https://shattered.io/, 2017.
[4] SEED：MD5 Collision Attack Lab
[5] Seed Labs ——MD5 Collision Attack Lab
[6] 【SEED Labs 2.0】MD5 Collision Attack Lab
[7] MD5碰撞原理简单介绍及其实现
如果存在错误或者不准确的地方欢迎在评论区指出，如果对你有帮助的话希望能点赞，转发😀这是对我莫大的鼓励。
扫一扫
2874
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
