hash length extension attacks(hash长度拓展攻击)

Created2023-06-27Updated2023-06-27Visited

hash算法和hash长度拓展攻击

hash算法:hash算法又叫做散列算法。是一种把任意长度的字符串加密为固定长度的字符串的加密算法，此时该算法生成的密文就是散列值。简言之：hash算法就是一种通过单向函数加密明文生成信息摘要的算法。
由于hash的生成机制使得我们可以人为的在原先的明文基础上添加新的拓展字符，使得原本的加密链变长，进一步控制到加密链的最后一节；达到我们得以控制最终的结果。
推荐文章：
https://www.skullsecurity.org/2012/everything-you-need-to-know-about-hash-length-extension-attacks

MD5算法

MD5加密

MD5算法是典型的一种信息摘要算法，它是由md2、md3、md4演变来的。无论是哪种md算法都是将一个任意长度的字符串加密成为一串固定的密文。在这个加密过程中会将明文字符串转换为一个128位的信息摘要；接着把这个信息摘要转换为一个十六进制的字符串就会得到32位的字符串，此时的32位的字符串也就是我们平时见到的MD5密文。
ps:因为在MD5加密过程中经过了压缩、加密、hash算法，所以此时MD5加密的内容是不可逆的

MD5算法

初识MD5算法

1.把消息分成n个分组

2.对最后一个分组进行填充(很重要的一步)

3.将每一个分组划分成16个子分组，然后对每一个输入量进行运算；运算结果作为下一个分组的输入量

4.输出最终结果
整个算法的流程图如下

深入MD5算法

此时在计算时会初始化四个寄存器A、B、C、D，此时的他们分别都会有他们的初始值
初始值如下：
A: 01 23 45 67
B: 89 ab cd ef
C: fe dc ba 98
D: 76 54 32 10
此时md5算法是以512bit为一个块进行迭代计算；当在第一个块算完之后，四个寄存器的值都会被更新，如果还存在下一个块则会在现在的者四个寄存器上继续迭代计算；等到全部的块计算完毕之后，四个寄存器的十六进制连起来就是最终的MD5值。
然而我们不可能确保最后一个数据的长度是512bit；所以此时我们需要进行一个填充(当前数据长度不满足对512求余为448)
ps:为什么要求当前长度对512bit求余为448bit?
因为我们要留出64bit来存放原消息(当原消息长度超过64bit时取低64bit)
填充方法：
1.首先补一个1(Bin)
2.接着在后面补0(Bin)直到满足比特长度对512求余为448时即可
3.接着补64bit的长度；这个长度是在补1和0以前的长度；此时如果长度超过了64bit则取低64bit
此时补完的一块可能长这样

1
raw_data + '\x80' + '\x00'*n + '\x00\x00\x00\x00\x00\x00\x00\x00'

此时的raw_data的部分就是原始的数据；第二个部分’\80’是一开始补的一个二进制位1，接着补若干个\x00，直到整个长度达到56Byte(448bit),然后最后的8Byt
e就是raw_data的长度，此时如果raw_data的长度超过了2^64bit则取低的64bit
tips:在MD5算法中的补位这一个部分就是实现长度拓展攻击的关键

MD5加密demo测试

此时我们要对0123456789abcdef进行加密；第一步转成二进制此时我们可以得到128位的二进制；然后此时在转为十六进制
此时我们先在010中写下我们要加密字符串的十六进制

此时进行填充：
1.先在二进制下的第一位补一个1又因为八位的二进制可以转十六进制；所以10000000(Bin) = 80(Hex);所以此时我们补一个80上去


2.接下来依次补0；补到448bit也就是56Byte

3.补剩下的64bit(8Byte);此时原始明文为0123456789abcdef一共16Byte，有128bit；此时将128转为十六进制写入；然后后面的7Byte补0


然后接下来就会使用这64Byte的数据进行计算。计算信息的摘要需要用补位结果的数据进行运算，也就是补位后的512bit的消息，在计算时候有一个初始的向量，这里初始的向量是一个固定的值。
由于在计算机存储中采用的是小端存储方式，所以上面的初始化向量在程序中的初始化代码为后面的0x部分。
然后将刚才的512bit消息和初始化向量进行第一轮的运算，之后初始化向量会被新的值覆盖，最后一轮的向量经过高低位互换后就是计算出的MD5值。
高低位互换:

1
2
3
4
5
6
7
8
9
10
11
12
假如最后一轮的运算后的向量值为：
    A=0xabcdef12
    B=0xabcdef12
    C=0xabcdef12
    D=0xabcdef12
那么进行高低位互换之后得到的数值为：
12 ef cd ab
12 ef cd ab
12 ef cd ab
12 ef cd ab
进行拼接得到最后加密结果
12efcdab12efcdab12efcdab12efcdab

从算法方面看MD5加密

计算test的md5值:
补位完后

1
0x74657374800000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002000000000000000


将补位后的数据进行一次复杂计算得出

1
2
3
4
A=0xcd6b8f09
B=0x73d32146
C=0x834edeca
D=0xf6b42726

数据小于512位，所以将ABCD通过小端规则转换就是MD5值：098f6bcd4621d373cade4e832627b4f6
ps:如果我输入的数据不是test而是一串很长的字符，换算出来大于512小于1024，就需要计算两次，第一次先计算前512位的ABCD的值，算出来后再用这个ABCD去计算后面512位的的ABCD的值，最后算出来的ABCD经过拼接就是这串字符的MD5了

hash长度拓展攻击

hash扩展长度攻击demo

1
2
3
4
已知secret为'secret'(攻击者未知)
数据data为'data'(攻击者已知)
加密方式为MD5(secret+data)此时也可以叫做加盐
追加字符为wann

此时按照流程

1
填入数据 --> 填补补位 --> 写入数据长度 --> 补0


然后此时攻击者进行追加内容wann

此时在继续计算它的MD5值时便有两种方法了

1
2
法一：直接使用MD5算法计算(服务端采用此方法)
法二：通过第一个块结束开始，使用我们已经从签hash中获得的状态并从该状态开始对追加内容进行hash(攻击者采用)

服务器的计算：

我们知道服务器会在字符串前面加上secret；所以此时我们向它发送字符串减去secret

服务器在该字符串前面附加密钥

设此时服务器根据签名 6ee582a1669ce442f3719c47430dadee 检查我们发送的数据；那么此时我们作为攻击者需要弄清楚如何生成签名

攻击者的计算(此时我们从一个问题开始)

假设我们发现了这样的一个下载文件的接口：

1
/download?name=test.pdf&sig=6543109bb53887f7bb46fe424f26e24a

经过测试发现sig可能是这个文件的某种校验签名，如果想通过这个接口下载其他文件就会失败，因为sig的校验无法通过。同时还会发现md5(name) !==sig，很明
显在校验算法中添加了盐，如果我们想下载任意的文件比如test.pdf%00/../../../../etc/passwd，正常情况下是没办法的，因为有盐，所以我们无法构造自己
的签名值，但是如果服务端使用了类似下面的校验代码，那么就会存在被绕过的风险。

1
if($sig === md5($salt.name))

此时回到我们的hash长度扩展攻击，我们可以利用md5的一些trick绕过这个限制。这个问题实际上变成了：如何在不知道 salt/key/secret 的情况下，计算出一
个文件名的合法 hash 值。
此时设这个合法的数据是test.pdf -> 6543109bb53887f7bb46fe424f26e24a
攻击
1.此时实施攻击的第一步便是将test.pdf这个部分补足到64Byte

1
2
len(secret) + len("test.pdf") + len(padding) + 8 == 64Byte
padding：为补齐的一部分

2.假设我们已经知道了 secret 的长度是 10，那么可以计算出，padding 的长度是 64-8-10-8; 这个 padding 中，第一个字节是 “\x80”，所以补0的长度是 64-8-10-8-1=37。所以我们的例子就会被补成这个样子：

1
secret + "test.pdf" + "\x80" + "\x00"*37 + "\x90\x00\x00\x00\x00\x00\x00\x00"

3.最后的 8byte 是 len(secret+”test.pdf”)，换成16进制就是\x90。这个长度已经是64Byte了，所以如果再向后面附加内容，那么就是一个新的计算块了。
这段过程用代码写出来：

1
2
3
4
5
fake_filename = "test.pdf{padding}"
padding = "\x80{zero}\x90\x00\x00\x00\x00\x00\x00\x00".format(zero="\x00"*(56-18-1))
fake_filename = fake_filename.format(padding=padding) + "/../../../../etc/passwd"
# print(fake_filename)
print("fake_filename length: " + str(len(fake_filename)))

从算法方面看hash长度拓展攻击

计算步骤

依旧是$str=”test”
此时经过补位后得到

1
$str=0x74657374800000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002000000000000000


此时我们继续在后面加上一个wann

1
$str=0x7465737480000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000200000000000000077616e6e


此时得$str大于512bit，此时程序会自动将这串数据补为1024bit

1
$str=0x7465737480000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000200000000000000077616e6e800000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002002000000000000

此时我们将$str分成两部分

1
74657374800000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002000000000000000

和

1
77616e6e800000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002002000000000000

这个时候程序计算前一部分的ABCD的值

1
2
3
4
A=0xcd6b8f09
B=0x73d32146
C=0x834edeca
D=0xf6b42726

到了第二部分，此时第二部分的计算会使用第一部分的ABCD去计算的；此时可以得到新的ABCD

1
2
3
4
5
A=0x226359e5
b=0x99df12eb
C=0x6853f59e
D=0xf5406385

最后算出来的MD5是e5596322eb12df999ef55368856340f5

发现问题

我们看到了，将原数据按长度拆分后，第一轮计算的结果会作为幻数用在第二轮计算中。而在我们的问题中，第一轮计算的结果我们是已知的，也就是说，我们知道了第二轮计算的幻数，可以进行接下来的运算。
因为知道第一个字符串$a的长度，此时我们就可以构造第二个字符串$b的值；也就是说我们手动在第二个字符串$b的前端添加一些特定数据，使得第一轮计算因为我们添加数据后符合一轮计算的原数据长度而只计算出第一个字符串的hash值。这样我们就可以利用这个结果作为我们二轮计算的幻数进行下面的计算，从而预测最终的md结果。

md5的hash长度扩展攻击操作实例

1
2
3
1.$a的MD5(098f6bcd4621d373cade4e832627b4f6)
2.$a的长度=4
3.$b我们可以任意控制

由1我们可以推出ABCD的值

1
2
3
4
A=0xcd6b8f09
B=0x73d32146
C=0x834edeca
D=0xf6b42726

我们构造$b的值，在前面添加特定长度的补全值： 

1
2
3
$b='\x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x20\x00\x00\x00\x00\x00\x00\x00'+'test'
ps:
其中\x80\x00\x00\x00\x00\x00\x00\x00这一类的数据是在md5计算的补位过程中填充的数据(padding)

此时因为我们不知道$a的具体内容只知道长度；此时我们假设$a=”aaaa”;则可以变成

1
$str='aaaa'+'\x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x20\x00\x00\x00\x00\x00\x00\x00'+'test'

然后：
1.由于大于512位，先补全为1024位，
2.将其分为两部分
3.计算第一部分的ABCD的值
4.再用第一部分算出来的ABCD拿来算第二部分的值。
这里由于第一部分的ABCD我们可以逆推出来，我们可以直接跳过前三部分直接进行第四部分的计算，只需要将标准的MD5的源码里面的初始的ABCD的值改为逆推出来的那个值。
此时我们使用初始的(假的)ABCD计算一下下面的MD5

1
0x74657374800000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002002000000000000

可以发现和上面正向计算出来的一样。
至此MD5的hash扩展攻击结束

攻击

攻击的要点在于：

攻击者可以控制message
攻击者需要知道key的长度，如不知道可以考虑暴力破解
攻击已经知道了包含key的一个消息的hash值
hash算法使用了Merkle–Damgård construction进行数据的压缩（比如MD5、SHA-1等）并采取 H(密钥 ∥ 消息) 构造
攻击可以达到的效果在于，如果知道一个原消息哈希值H(key∥M1)及其(key∥M1)长度，对于任意的字符串M2，攻击者可以计算出H(pad(key∥M1) + M2)的值，而不需要知道是key及M1是多少
利用场景

1
2
在 $hash = md5($secret.$key) 中已知 $hash 和 $key 以及 $secret 的长度时  
可以找到另一个 $_hash 和 $_key 使得 $_hash = md5($secrect.$_key) 成立

如何攻击

由于上面我们已经补全过数据了，现在已经是完整的块了，当我们继续在后面补充数据的时候，他在分块的时候就会直接帮我们把前面的数据分块，这部分会被hash算法先计算，由于算法初始值相同，计算的顺序相同，这一块的数据计算的结果就一定是固定的，也就是在我们没有补充数据之前的数据的hash结果，那么只要当我们后面补充的数据用这个hash结果的状态继续往后面执行，计算出来的evil_hash也一定会和服务器端hash(secret+“填充数据”+“任意可控数据”)的最终结果一样。从而可以导致该攻击。
更简单的说法是：攻击者的哈希计算过程，相当于从服务器计算过程的一半紧接着进行下去。

攻击流程

服务器端：
hash(secret+msg) =>一系列计算 hash_value
攻击者:
在知道secret+msg多长的情况下可以补全为一个完整的块，从而补全的这个块计算出来的结果我们可以拿到该状态，然后加入可控的邪恶数据，再利用原来服务器的hash_value来设置当前的hash状态，从而继续执行下去。
ps:通常来讲，攻击者不会知道服务器上原始secret的长度，所以可能需要枚举secret的长度直到成功

ps: https://github.com/CTF-Thanos/ctf-record/blob/master/shiyanbar/ctf1848/hash%E9%95%BF%E5%BA%A6%E6%94%BB%E5%87%BB.md

hash长度拓展攻击在ctf中的考点

http://ctf5.shiyanbar.com/web/kzhan.php
源码审计

此时的重点在于

此时通过$COOKIE[“getmein”]来获取名为getmein的Cookie值；后面的md5($secret.urldecode($username.$password))是对一个秘密字符串和经过url解码
的username和password连接而成的字符串进行md5加密
然后根据

我们可以知道第一个hash值：571580b26c65f306376d4f64e53cb5c7

然后根据hash扩展长度攻击我们即可伪造出第二个hash
已知信息

1
2
3
4
secret的长度为15，再加上第一个admin就是20
哈希值为571580b26c65f306376d4f64e53cb5c7
data为第二个admin
add数据为任意

此时我们使用hashpump来帮助我们生成payload

此时利用chatgpt帮助我们把\x全部替换成%：admin%80%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%c8%00%00%00%00%00%00%00hey

此时即可完成hash扩展长度攻击得到flag
原理：在知道secret+msg多长的情况下可以补全为一个完整的块，从而补全的这个块计算出来的结果我们可以拿到该状态，然后加入可控的邪恶数据，再利用原来服务器的hash_value来设置当前的hash状态，从而继续执行下去。