1 作业题目

本次实验主要是加深大家对 MD5 碰撞及其原理的理解，使用 SEED 实验环境中的工具及编程语言，完成以下任务：

  1. 使用 md5collgen 生成两个 MD5 值相同的文件，并利用 bless 十六进制编辑 器查看输出的两个文件，描述你观察到的情况；
  2. 参考 Lab3_task2.c 的代码，生成两个 MD5 值相同但输出不同的两个可执行 文件。
  3. 参考 Lab3_task3.c 的代码，生成两个 MD5 值相同但代码行为不相同的可执 行文件。
  4. 回答问题：通过上面的实验，请解释为什么可以做到不同行为的两个可执行 文件具有相同的 MD5 值？

2 实验步骤及结果

2.1 实验一-使用 md5collgen 生成两个 MD5 值相同的文件

首先在实验 Lab3 文件夹创建一个 prefix.txt，

然后执行命令：md5collgen -p prefix.txt -o out1.bin out2.bin

已经发现生成了对应文件 out1.bin 和 out2.bin

发现两文件的md5 值相同

然后执行命令：bless out1.bin和 bless out2.bin，查看两个文件的十六进制信息


经过对比发现，这两个 MD5 值相同的文件，out1.bin 、out2.bin 其十六进制内容
完全一致。

问题一：如果您的前缀文件的长度不是 64 的倍数，会发生什么情
况？

答 ：观察 out1.bin 的十六进制，会填 0 把前缀文件的长度补充到 64 的倍数。

问题二：创建一个正好有 64 字节的前缀文件，然后再次运行碰撞
工具，看看会发生什么

答 ：我们把二进制的 64 个字节 0 -63 放入 prefix2.txt，运行 md5collgen，再 用 hexdump -C 看一看这两个文件的值：

发现并没有像问题一 中的一样给第一个块里补充 0，而是把第一个块原封不动地 保留，用第二个块构造两个文件。

问题三：由md5colgen生成的两个输出文件的数据（128 字节）完全不同吗？请确定所有不同的字节


答 ：不是完全不同，共有 6 个字节不同

2.2 实验二- 生成两个 MD5 值相同但输出不同的两个可执行文件

因为我们在问题一 已经构造出了哈希值相等的 out1.bin 和 out2.bin 了，所以我们 直接在它们的基础上添加一句相同的话， 写入 out3.bin 来看看 1.bin 、2.bin 是否 依然具有相同的哈希值。

尽管我们的实验只有一组，不具有普遍性，但结合 md5sum 原理的理论推导已 经揭示了如果 MD5(M) = MD5(N)，则有 MD5(M || T) = MD5(N || T) 的特性成立， 我们只是加以验证。

2.3 实验三 ：生成具有相同 MD5 哈希的两个可执行文件

修改 Lab3_task2.c 为以下内容, 0x25 是 % 的 ascii 码，在二进制文件中定位 200
个 % 将不会很困难。

先编译一下 ，再执行查看输出结果

因为十六进制的位数过多，故将图片的首尾拼接，忽略中间部分，可以看到 20 0 个 % 的片段，

我们需要找到一个分界点，使得它前面的长度是 64 的倍数（根据上个实验可知 它会自动补零）， 它后面开始的 64 个字符全是 % 。这样把前面的部分扔到
md5collgen 中构造，把中间的 64 个 % 替换成新产生的两个块，就能得到两个 具有相同哈希值的可执行文件。
所以我们可以寻找它第一次进入这 200 个 % 的区域的断点，在这里分界。显然 00003020 就是我们要找的点，我们算出 0x3020 = 12320，然后取前 3020 个 字节组成 prefix：

我们查看一下 out1

直接看最后的部分，也就是新构造的部分

我们再把 ta 中从第 30c0 + 1 = 30c1 个字节（注意要把它转化为十进制 12481） 到最后一个字节的部分拿出来作为 suffix，并且分别拿 out1, out2 分别和 suffix
连接就能形成两个不同的可执行程序 1 和 2：

不过一开始它们是不可执行的，我们要用 ch mod +x 修改权限，修改完成后再 次运行，它就能输出数组里面的值，执行 file1 、file2 输出结果如图，有不同之
处， 因为数组中间修改了一部分：

再验证一下 1 和 2 的 md5 校验码相等：

所以我们构造是成功的。

2.4 实验四-生成两个 MD5 值相同但输出不同的两个可执行文件


将 Lab3_task3.c 构造如下：

再对该代码编译、运行，再次 bless Lab3_task3，找之前放的 200 个 A 和 200
个 B 在哪里。

arr1 的位置与任务二相同，截取前 12352 作为前缀并生成两个 md5 相同的文件：

截取后缀（从 GCC 开始）

把其中一个新前缀 p 的后 32(字符 A)+128(md5 填充物)=160 个字节截取出来作
为第二个数组的主体：

获取填充字节 0x00，由于数组 200 个字节，因此填充 40 个，注意两个数组间还
有 24 字节的填充，到最后一个填充字节十六进制是 0x3100，其十进制是 12544

将前 12544 字节裁切为 temp，再裁切 temp 的最后 24 个字节为 m24，即 24 个

填充字节 0x00。再裁切 m24 的 16 个 0x00 放入 temp,最后合并为 40 个填充字节
的 m40

开始拼接，并赋予权限：

补充解释：out1 里面除了 prefix 有 200 个 A ，然后m40+m24 是中间补在 A 、B
的 64 个 0x00，middle+m40 是第二个数组最后 200 个的位置，再加上 suffix 就
还原了原来的长度
对 1.out 、2.out 执行：

由图可得两个文件执行的函数不同(因为数组的值改变了)，但是 md5 值相同。

2.5 对实验四的解释

  • 不同行为：在最后生成的可执行程序中，第二个数组与源程序无关， 完全来自于第一个数组， 因为 middle 取自 out1； 因此经过填充后，两个文 件中第二个数组的与其中一个相同而与(md5collgen 产生的)另一个不相同导 致 if 判断产生不一样的结果，最后执行不 一样的函数。
  • 相同 md5：out1.bin 与 out2.bin 是由 md5collgen 产生的具有相同 md5 值的不同 prefix 文件，而两个文件后面的填充+middle+suffix 完全相同， 因此在迭代运算中保持着相同的 md5 导致最后计算结果一样。