MD5长度拓展攻击

VVkladg0r2024-05-132024-05-13

Hash长度拓展攻击

介绍

MD5是一种广泛使用的哈希函数，它产生一个128位（16字节）的哈希值。通常呈现为一个32字符的十六进制数。它是一种单项函数，这意味着从MD5哈希值是不可能（在实践中）直接得到原始数据的。换句话说，MD5不是加密过程；它是一个单向散列函数，没有一个反向的过程能够从散列值中恢复出准确的原始输入。

哈希长度扩展攻击（也称为哈希长度扩充攻击或者Hash Extension Attack）是一种针对使用Merkle-Damgard构造的哈希函数（如MD5, SHA-1, SHA-256）的加密攻击。Merkle-Damgard构造是一种创建哈希函数的方法，其典型结构包括一个基本的压缩函数和一个填充方案，确保输入数据的长度是特定倍数。

哈希长度扩展攻击的原理基于以下几点：

可预见的填充： Merkle-Damgård实现使用一个预定义的方式来填充消息，以确保信息长度符合要求。通常填充以一个bit的’1’开始，然后是一串’0’，最后是一个表示原始消息长度的64位（对于MD5和SHA-1）或128位（对于某些SHA-2函数）的二进制数。攻击者知道这个填充方案。

状态保持：哈希函数在处理信息的时候，会将信息分成固定大小的块，然后通过压缩函数逐块处理。每块处理结束后，压缩函数的输出会成为下一块处理的输入（称为”链式状态”或”中间哈希值”）。最终块处理完成后产生的输出便是整个消息的哈希值。

不需要初始状态：在进行哈希计算时，攻击者并不需要知道原始消息的具体内容，只需知道原始消息哈希的中间状态或最终状态。

想象一下，有一个秘密盒子（哈希函数），这个盒子可以把任何东西（数据）变成一堆乱码（哈希值），而且这个过程是单向的，就是说你不能从乱码再变回原来的东西。

通常，当你把一些东西放进这个盒子时，如果想要让盒子正常工作，你需要在东西的后面放些填充物，比如棉花。这个填充过程是按照一定的规则来的，比如先放一点特别的棉花，再放一些普通的棉花，最后放一点标记原来东西大小的棉花。

哈希长度扩展攻击就是有人发现了这个秘密：他们不需要知道你原来放进去的是什么，只要知道最后的乱码和你放进去东西的大小，他们就能在不打开盒子的情况下，在你的东西后面加上更多的东西和填充物，然后算出这个新组合的乱码。

这样他们就能假装知道你最初放进去的东西，实际上他们只是在你的东西后面加了些自己的东西，然后算出了一个看起来合理的乱码。

这种攻击之所以可行，是因为填充规则是公开的，而且这个秘密盒子在处理东西时有一些可以预测的特点。所以，如果别人知道你的乱码和你放进去东西的大小，他们就可能利用这些信息进行攻击。

哈希长度扩展攻击(hash length extension attacks)是指针对某些允许包含额外信息的加密散列函数的攻击手段。该攻击适用于在消息与密钥的长度已知的情形下，所有采取了 H(密钥 ∥ 消息) 此类构造的散列函数。MD5和SHA-1等基于Merkle–Damgård构造的算法均对此类攻击显示出脆弱性。

如果一个应用程序是这样操作的：

准备了一个密文和一些数据构造成一个字符串里，并且使用了MD5之类的哈希函数生成了一个哈希值（也就是所谓的signature/签名）
让攻击者可以提交数据以及哈希值，虽然攻击者不知道密文
服务器把提交的数据跟密文构造成字符串，并经过哈希后判断是否等同于提交上来的哈希值

这个时候，该应用程序就易受长度扩展攻击，攻击者可以构造出{secret || data || attacker_controlled_data}的哈希值。

-——————————————————————-

系统会自动生成一串任意的字节串secret，以及一串明文c1然后进行哈希加密，

m1=hash(secret+c1)

我们可以得到加密后的密文m1，

然后我们需要提供一个密文m2，以及一串明文c2

使得

m2=hash(secret+c2)

#一般来说，c1 in c2,c2实际上为c1的拓展部分，我们需要把明文的长度拓展一下，进行攻击

然后即可得到flag

分块
哈希计算进行加密时，通常是将明文信息以类似块密码的形式进行分组，对各个组块依次加密，每一块一般为512 bit，也就是64 bytes，每组的明文部分为56 bytes，剩下的8 bytes表示这块明文消息未填充前的长度

填充
在明文消息的最后一块一般是不满足56ytes时就对这个最后一块进行padding填充，填充至56 bytes的位置，，填充方式为，在16进制下，我们需要在消息后添加一个80，然后加0，直至56 bytes时

变量计算
哈希加密的在分块之后，每块在进行加密运算之前都会有一个链变量(key)，有每一个链变量与该块进行运算，除了第一块，每一块相对应的链变量都是前一块进行哈希计算后的字符串生成的，也就是说，每一块都对下一块有影响，（有点类似于CBC了），而第一块会有一个初始的链变量，为（无需考虑计算过程的细节）

A=0x67452301

B=0xefcdab89
C=0x98badcfe

D=0x10325476

而最后一块生成的链变量需要进行高低位互换（如：aabbccdd -> ddccbbaa），再拼接在一起就是我们计算出来的哈希值

代码验证：

from hashlib import md5,sha256
import os
flag=b'flag{welcome}'
secrets=os.urandom(15)
m=b'admin'
k1=sha256(secrets+m+m).hexdigest()
print(k1)
key=input("输入key的16进制")
cipher=input("输入哈希值")
s1=secrets+m+bytes.fromhex(key)
'''经过多次尝试后发现，在python中，输入16进制字符串时对格式最友好的
如果输入为类似\x00\x00\x00\x00\x00\x80的字符串，
进行encode转为字节串会生成\\x00\\x00\\x00\\x00\\x00\\x80的错误形式
即使转为urlcode在转回来的时候也会有误差，可能是我python环境的问题
'''
'''
在使用hashpump时
signnature：已知的hash加密的字符串
data:hash加密字符串中明文中已知的部分
key length: 未知的字符串长度
add:自己想添加的附值
'''
k2=sha256(s1).hexdigest()
print(k2)
if cipher==k2:
    print(flag)

工具梭哈

当然，此攻击已经有很多成熟的工具了，不用再这么麻烦的自己写脚本跑。

这里使用hashump就行

1、HashPump安装

HashPump是一个借助于OpenSSL实现了针对多种散列函数的攻击的工具，支持针对MD5、CRC32、SHA1、SHA256和SHA512等长度扩展攻击。而MD2、SHA224和SHA384算法不受此攻击的影响，因其部分避免了对状态变量的输出，并不输出全部的状态变量。

（至于别的文章提到了MD4、RIPEMD-160、SHA-0、WHIRLPOOL等也可以构造长度扩展攻击，等以后再研究。）

git clone https://github.com/bwall/HashPump
不行就 git clone https://gitee.com/ljcppp/HashPump.git
apt-get install g++ libssl-dev
cd HashPump
make
make install

至于想在python里实现hashpump，可以使用hashpumpy这个插件：

（注意还是得先安装了libssl-dev）

pip install hashpumpy

推荐在linux里使用，使用方法可以这样获取：

python
>>> import hashpumpy
>>> help(hashpumpy.hashpump)

2、HashPump用法

这里以一个实验吧题目为例，关键的代码大概如下：

<?php
$secret="XXXXXXXXXXXXXXX"; // This secret is 15 characters long for security!
$username="admin";
$password = $_POST["password"];
if($COOKIE["getmein"] === md5($secret . urldecode($username . $password))){
    echo "Congratulations! You are a registered user.\n";
    die ("The flag is ". $flag);
}else{
    die("Your cookies don't match up! STOP HACKING THIS SITE.");
}
?>

在题目里可以得到:

md5($secret."adminadmin")的值为571580b26c65f306376d4f64e53cb5c7

稍微整理下我们已经知道的：

$secret是密文，长度为15，如果再算上后面第一个admin，长度就是20
而数据是admin
签名（哈希值）是571580b26c65f306376d4f64e53cb5c7

这时候我们使用HashPump，附加数据至少1位以上：

./hashpump

# hashpump
Input Signature: 571580b26c65f306376d4f64e53cb5c7
Input Data: admin
Input Key Length: 20
Input Data to Add: pcat

或者直接

hashpump -s 571580b26c65f306376d4f64e53cb5c7 -d admin -k 20 -a pcat

就会得到

3e67e8f0c05e1ad68020df30bbc505f5
admin\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\xc8\x00\x00\x00\x00\x00\x00\x00pcat

第一个是新的签名，把它设置到cookies的getmein里。

第二个先把\x替换为%后，post提交

password=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%00pcat

就可以通过了。

-——

ps.提供一个基于HashPump的在线网站：

http://sakurity.com/lengthextension

（可能得翻了墙才可以访问，附加数据至少一位以上，message length为密文+数据的总长度，看不到”submit”键请刷新或者换浏览器）