长度扩展攻击

Hash 长度扩展攻击：已知明文长度和明文的杂凑值，但明文本身未知，通过构造扩展消息，可以计算出明文连接扩展消息的杂凑值。

引言

在 BaseCTF 第二周遇到的一道题目，题目部分如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
<?php
session_start();
highlight_file(__FILE__);

// ...

if (!isset($_SESSION['random'])) {
    $_SESSION['random'] = bin2hex(random_bytes(16)) . bin2hex(random_bytes(16)) . bin2hex(random_bytes(16));
}

$random = $_SESSION['random'];
echo md5($random);
echo '<br />';

$name = $_POST['name'] ?? 'user';
if (substr($name, -5) !== 'admin') {
    die('不是管理员也来凑热闹?');
}

$md5 = $_POST['md5'];
if (md5($random . $name) !== $md5) {
    die('伪造? NO NO NO!');
}
?>

这里给出了一个96字节的明文，但是内容未知。然后给出这个明文的 MD5 值。然后要求你附加一段文字，文字以 admin 结尾，使得明文加上附加文字的 MD5 能被求出来。这里就设计到了本文介绍的 Hash 长度扩展攻击。

本文在介绍部分就以 MD5 来介绍 Hash 长度扩展攻击，实际上 SHA1，SHA2的算法也都受该攻击的影响，只是影响的方式都大同小异，相信聪明的你举一反三就一定会了。

MD5 算法

该攻击过程是杂凑函数填充过程中由于自身的逻辑导致的，所以在以 MD5 为例子介绍 Hash 长度扩展攻击前，我们来看一下 MD5 算法的具体实现过程。

MD5 实现

上图展示了 MD5 算法的过程，我们从上至下、从左至右地看这张图。

填充

MD5 的第一步就是对明文进行填充，使得其长度为512比特的倍数，从而可以切分成长为64字节（等于512比特，下面都用字节来表示了）的分组。那么填充什么呢？

按照 RFC1321 的标准

  1. 在明文末尾填充 0x80 （1字节）
  2. 在最后一个分组的最后8字节填充明文的长度，注意！！！这里用的比特长度，所以字节要乘以8（8字节）
  3. 其余部分填充 0x00

来点小练习：

Q1：假如最后一个分组长度为32字节，填充多少 0x00（仅限 0x00 填充部分，下同）？

A1：64-32-1-8 = 23字节

Q2：假如最后一个分组长度为56字节，填充多少 0x00？

A2：64-56-1-8 = -1字节？如果填了 0x80 后填不下长度，那么就新开一个分段填充长度，所以是 63 字节。

Q3：假如最后一个分组长度为55字节，填充多少 0x00？

A3：64-55-1-8 = 0字节，刚刚好！

分组计算

这里我不想赘述 MD5 中对每个分组中计算的具体过程，如果好奇可以看 RFC1321 标准，或者其他博客。我们只需要将这段过程记为 \(\textbf{H}_C(\textbf{B_i},\textbf{V})\) ，其中 \(\textbf{B_i}\) 是明文的当前分组，\(\textbf{V}\) 是一个向量，有一个初始值。对所有的分组计算完成后，\(\textbf{V}\) 就是该段明文的 MD5 杂凑值。那么 MD5 计算方法如下：

1
2
3
4
5
6
def MD5:
    V = IV
    for B_i in B:
        _V = H_C(B_i, V)
        V += _V
    return V

MD5 长度扩展攻击

下面介绍攻击过程，先看下图：

长度扩展攻击

名词量爆炸，不是吗？捋一下相关的名词：

  • 原填充：明文在计算 MD5 过程中的填充
  • 扩展消息：你希望添加的消息，但是请注意，这里的扩展消息并不是直接添加在明文后面的
  • 伪造消息：等于原填充+扩展消息，这才是直接添加在明文后面的内容
  • 扩展填充：将明文+伪造消息变为一个新的明文，为计算新明文的 MD5 而添加的填充

可以看到，扩展填充里面的长度为 明文+(原填充+扩展消息) = 明文+伪造消息 的总长度。

老规律，还是来点例题（你不给例题我知道题怎么做啊）

Q1：明文长为96字节，扩展消息长为5字节，请问扩展填充中有多少 0x00，长度为多少？

A1：首先计算原填充，一看1+23+8=32字节，总消息长为96+32+5=133字节，最后一个分组5字节，填充50个 0x00，长度为133*8=1064

Q2：明文长为55字节，扩展消息长为120字节，请问扩展填充中有多少 0x00，长度为多少？

A2：首先计算原填充，一看1+0+8=9字节，总消息长为55+9+120=184字节，最后一个分组56字节，填充63个 0x00，长度为184*8=1472

Q3：明文长为56字节，扩展消息长为0字节，请问扩展填充中有多少 0x00，长度为多少？

A3：首先计算原填充，一看1+63+8=72字节，总消息长度为56+72+0=128字节，最后一个分组为64字节，填充55个 0x00，长度为128*8=1024

计算结果

相信明白图1和图2后，聪明的你已经知道该怎么计算添加扩展消息后的 MD5 值了吧。如下图：

长度扩展攻击过程

我们将明文 MD5 值作为向量的初始值 \(\textbf{V}\)，然后把 伪造消息+扩展填充 每64字节分成一组 \(\textbf{B_i}\)，送到 \(\textbf{H}_C(\textbf{B_i},\textbf{V})\) 中，就得到了扩展后的 MD5 值。

小工具

这里我写了一个小工具来生成你需要的攻击负载以及对应的杂凑值。（但愿它没有问题）

请输入正确的十六进制的 MD5 值
以后再说吧
安全 竞赛
长度扩展攻击
https://blog.bcb.pub/2024/08/30/ctf/notes/length-extension-attack/
作者
BadCodeBuilder
发布于
2024年8月30日
许可协议