SeedLab——MD5 collision

task 1

# Task

生成两个不同的文件，但是这两个文件具有相同的md5哈希值。也就是最简单的哈希碰撞。

md5collgen的原理如下图所示。其接受一个相同的前缀内容prefix，并为其生成两个填充与P和Q，P与Q内容不同，但是最后拼接得到prefix1与prefix2（64字节的倍数）的md5散列值是相同的。

MD5（Message Digest Algorithm 5）是一种常用的哈希函数，它将输入的数据按照64字节一组进行切分，并在这些分组上进行迭代地计算。核心是压缩函数，它接受64字节的数据分组和前一次迭代的输出作为输入，并输出128位的中间哈希值（IHV），这个输出将在下一次迭代中参与计算。如果当前迭代是最后一次，IHV就是最终的哈希值。在第一次迭代中，IHV的输入是一个初始化的固定值。

尽管MD5是一种广泛使用的哈希算法，但它并不是完全抗碰撞的。MD5生成的哈希值是128位（16字节）长，相对较短。因此，他的抗碰撞性并不强，在有限的位数内，存在多个不同的输入数据可能生成相同的哈希值。

# Steps

vim编辑test文件，将hello, world!写入。

使用md5collgen生成两个md5相同的文件out1和out2。

md5collgen -p test -o out1 out2

使用differ out1 out2比较两个文件的差异，发现两个文件不同。然后使用md5sum指令分别计算两个文件的md5值，哈希值相同。

使用hexdump查看两个二进制文件的内容，可以看到内容并不相同。

综上，生成了两个具有相同md5值但是内容不同的文件

– Question 1. If the length of your prefix file is not multiple of 64, what is going to happen?

如果前缀长度不是64的倍数，对结果无影响。最终md5collgen生成的填充域加上前缀prefix的长度一定是64字节的倍数。如下图所示，生成一个60字节长度的文件并对其进行md5碰撞。

使用bless查看其中一个生成的文件，可以看到填充域为132字节长度。最终生成的文件一定是64字节的倍数。

– Question 2. Create a prefix file with exactly 64 bytes, and run the collision tool again, and see what happens.

如图，截取一个64字节的文件，并对其进行md5碰撞。

使用bless查看其中一个生成的文件，可以看到填充域为128字节长度。

– Question 3. Are the data (128 bytes) generated by md5collgen completely different for the two output files? Please identify all the bytes that are different.

经过观察和比较，生成的填充字节并非完全不同，只有少数字节不相同。

task 2

# Task

生成两个输出不同但是md5散列值相同的文件。源代码如下所示，编译源文件得到可执行文件task2。

#include <stdio.h>
unsigned char xyz[200] = {
	// content is up to you
};
int main()
{
    int i;
    for (i=0; i<200; i++){
        printf("%x", xyz[i]);
    }
    printf("\n");
}

编译后的可执行文件内容如下所示，白色的区域为xyz的内容。要生成两个输出不同但是md5散列值相同的文件，就要对xyz内容下手。截取0到m字节（必须在xyz内）区域内容作为prefix前缀，然后使用md5collgen以prefix作为前缀生成两个内容不同但是md5相同的文件prefix1和prefix2。打开bless查看prefix1文件，观察得到填充区域的字节长度n。

接下来截取后缀部分，由于前缀生成了n字节的填充域，因此后缀的长度为文件总长度-n-m字节。简而言之，上述过程就是把对前缀进行md5碰撞产生的填充域替换了xyz中的一部分。

最后把前缀与后缀拼接在一起即可得到输出结果不同但是md5散列值相同的两个可执行文件了。

# Steps

在bless中打开可执行文件，选中xyz字符串。

查看selection确定字符串的位置，范围为0x3020（12320）到0x30e7（12519）。

将编译后的task2截取从第1个到12352字节范围的内容并写入prefix。然后使用md5collgen命令以prefix为前缀进行md5碰撞，生成两个内容不同但是md5值相同的prefix1和prefix2。使用bless查看prefix1，发现填充了128个字节。

head -c 12352 task2 > prefix
md5collgen prefix -o prefix1 prefix2

查看bless中的prefix1，发现生成了128字节的填充域，因此将第12352+128+1之后的字节截取作为后缀suffix

tail -c +12481 task2 > suffix

将suffix与prefix1和prefix2重新拼接并执行，发现无执行权限，通过chmod +x增加执行权限。

cat suffix >> prefix1
cat suffix >> prefix2

然后执行prefix1和prefix2，发现输出长度不同，因此结果不同。

利用md5sum命令计算prefix1和prefix2的md5值，发现md5值相同。

综上，生成了两个哈希值相同但是执行结果不同的可执行文件。sh脚本文件如下。

#!/bin/bash
head -c 12352 task2 > prefix
md5collgen prefix -o prefix1 prefix2
tail -c +12481 task2 > suffix
cat suffix >> prefix1
cat suffix >> prefix2

task 3

# Task

生成md5值相同但是代码行为不同的两个可执行文件。

#include <stdio.h>
#include <string.h>
unsigned char X[200] = {
    'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 
    'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 
    'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 
    'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 
};
unsigned char Y[200] = {
    'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 
    'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 
    'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 
    'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 
};
int main()
{
    if(memcmp(X, Y, 200) == 0){
        printf("run begin code\n");
    }else{
        printf("run malicious code\n");
    }
    return 0;
}

将源代码编译，文件内容如下所示。

首先截取0到m字节（落在x中）的内容作为前缀。然后对prefix进行md5碰撞得到md5散列值相同但是内容不同的两个文件prefix1和prefix2。目标文件1的生成过程如下，将生成的填充域P替换掉X和Y中的对应的区域，这样在代码执行比较时X与Y的内容相同。

目标文件2的生成过程如下，将prefix2的填充域Q放入目标文件2的X对应区域，同时将prefix1的填充域放入Y的对应区域以保证两个文件的md5散列值相同。

这样就可以得到md5散列值相同但是代码行为不同的两个可执行文件了。

# Steps

编译task3并运行

[09/26/23]seed@VM:~/lab3$ gcc task3.c -o task3
[09/26/23]seed@VM:~/lab3$ ./task3
run benign code

使用bless打开该可执行文件，找到X和Y的位置。

X: 12304 ~ 12359
Y: 12544 ~ 12583

目标是生成两个MD5值相同但输出不同的两个可执行文件，构造两个md5相同但是内容不同的文件prefix1和prefix2。

head -c 12352 task3 > prefix
md5collgen prefix -o prefix1 prefix2

使用bless查看prefix1和prefix2，发现md5collgen在末尾填充了128个字节。

将prefix1的最后128字节的填充值取出

tail -c 128 prefix1 > fill

将原文件除去prefix的内容取出（12352+128+1）作为后缀suffix。

tail -c +12481 task3 > suffix

将suffix前面96字节的内容取出（X Y被替换区域中间的内容），并将suffix从第225（96+128+1）字节开始的内容写入suffix1（Y被替换区域之后所有内容）

head -c 96 suffix > middle
tail -c +225 suffix > suffix1

将填充值补充到middle之后，再将后缀suffix1填充到middle之后，最后将middle与分别与prefix1和prefix2拼接在一起就可以的到两个可执行文件prefix1和prefix2了。

cat fill >> middle
cat suffix1 >> middle
cat middle >> prefix1
cat middle >> prefix2

最后得到两个可执行文件prefix1和prefix2，执行这两个文件并检查md5值，可以看到输出结果不同但是md5值相同。

综上，生成了两个哈希值相同但是执行结果不同的可执行文件。sh脚本文件如下。

#!/bin/bash
gcc task3.c -o task3
head -c 12352 task3 > prefix
md5collgen prefix -o prefix1 prefix2
tail -c 128 prefix1 > fill
tail -c +12481 task3 > suffix 
head -c 96 suffix > middle
tail -c +225 suffix > suffix1
cat fill >> middle
cat suffix1 >> middle
cat middle >> prefix1
cat middle >> prefix2

Overall

md5的输出是128位（16字节）的结果，该算法的输入空间远远大于输出空间，这意味着不同的输入数据可能会映射到相同的输出空间，所以发生碰撞就在所难免。

我们通过截取文件内容，并利用工具构造碰撞填充域，然后将填充域替换可执行文件中的变量区域，这样就完成了prefix+填充域（长度为64字节的倍数）对于prefix+其他内容（长度为64字节的倍数）的替换，由于填充之后内容长度为64字节的倍数，根据md5算法的特性，替换前后迭代到当前位置的IHV是相同的，因此整个文件内容的md5散列值是相同的。所以我们可以通过构造填充域、适当的拼接内容来绕过md5算法对于文件完整性和真实性的保护，比如让做到不同行为的两个可执行文件具有相同的MD5值。

------本页内容已结束，喜欢请分享------

---