哈希长度扩展攻击

哈希长度扩展攻击利用了 MD5 ,SHA1 等加密算法的缺陷,可以在不知道原始密钥的情况下计算出一个对应的 hash 值。

0x00 引言

做题的时候看到了这个问题,挺好玩的,记录一下。

题目中的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
<?php
$auth = false;
$role = "guest";
$salt = ;
if (isset($_COOKIE["role"])) {
$role = unserialize($_COOKIE["role"]);
$hsh = $_COOKIE["hsh"];
if ($role==="admin" && $hsh === md5($salt.strrev($_COOKIE["role"]))) {
$auth = true;
}
else {
$auth = false;
} else {}
$s = serialize($role);
setcookie('role',$s);
$hsh = md5($salt.strrev($s));
setcookie('hsh',$hsh);
}
if ($auth) {
echo "<h3>Welcome Admin. Your flag is "
}
else {
echo "<h3>Only Admin can see the flag!!</h3>";
}
?>

一篇不错的文章:https://blog.skullsecurity.org/2012/everything-you-need-to-know-about-hash-length-extension-attacks

0x01 简单了解hash函数

哈希函数以区块为单位操作数据。诸如MD5, SHA1, SHA256的区块长度都是512 bits 。大多数 message 的长度不会刚好可以被哈希函数的区块长度整除。因此 message 就必须被填充( padding )至区块长度的整数倍。

这里简单说一下MD5的加密原理,详细的描述可以参考 RFC1321

MD5是输入不定长度信息,输出固定长度128-bits的算法。即使原文中出现一个微小的变化,其散列结果也会发生巨大变化。空文的散列为:

1
MD5("") = d41d8cd98f00b204e9800998ecf8427e

MD5算法包括几个步骤:1. 补位;2. 补长度;3. 初始化MD缓冲区;4. 处理字块消息。它以512bit为一个块进行迭代运算,第一个块计算完成后四个寄存器的值就会更新,如果还存在下一个块,就在此基础上继续进行迭代计算,全部完成后,把四个寄存器中的十六进制连接起来,就是最后的md5值。简单讲一下这几个步骤:

1 - 补位
如果当前的数据长度不满足对 512bit 求余为 448bit ,即len(message) % 512 != 448时,需要补位至满足这个条件。
补位方式:

  1. 首先补一个1(二进制位上的1,而非十进制位上的)
  2. 在后面补0(也是二进制位上的),直到满足条件(数据比特长度对 512 求余为 448)

注意,如果消息长度已经达到 448bit ,也要进行补位,补位是必须的。

2 - 补长度
即补 64bit 的长度,这个长度是在补 1 和 0 以前的长度,如果长度超出了 64bit,那么就取低 64bit。

引用一下lightless文章里的说法。完成补位与补长度的操作后,一个块可能是这个样子的:

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

第一个 raw_data 的部分就是原始的数据,第二个部分’\x80’是一开始补的一个二进制位 1,接着补若干个 \ x00,直到整个长度达到 56Byte,最后的 8Byte 就是 raw_data 的长度,如果 raw_data 的长度超过了 2^64bit,则取低 64bit.

附1,2步的文档介绍

Step 1. Append Padding Bits

The message is “padded” (extended) so that its length (in bits) is
congruent to 448, modulo 512. That is, the message is extended so
that it is just 64 bits shy of being a multiple of 512 bits long.
Padding is always performed, even if the length of the message is
already congruent to 448, modulo 512.

Padding is performed as follows: a single “1” bit is appended to the
message, and then “0” bits are appended so that the length in bits of
the padded message becomes congruent to 448, modulo 512. In all, at
least one bit and at most 512 bits are appended.

Step 2. Append Length

A 64-bit representation of b (the length of the message before the
padding bits were added) is appended to the result of the previous
step. In the unlikely event that b is greater than 2^64, then only
the low-order 64 bits of b are used. (These bits are appended as two
32-bit words and appended low-order word first in accordance with the
previous conventions.)

At this point the resulting message (after padding with bits and with
b) has a length that is an exact multiple of 512 bits. Equivalently,
this message has a length that is an exact multiple of 16 (32-bit)
words. Let M[0 … N-1] denote the words of the resulting message,
where N is a multiple of 16.

3 - 初始化MD缓冲区
在计算md5的时候会先初始化四个寄存器(A,B,C,D)且有各自的初始值:

1
2
3
4
word A: 01 23 45 67
word B: 89 ab cd ef
word C: fe dc ba 98
word D: 76 54 32 10

4 - 处理字块消息
必须用已经完成补位 & 补长度操作的字块来进行运算,具体细节不展开了,我们只需要知道经过一次消息摘要后,上面的寄存器值将会被新的值覆盖,而最后一轮产生的链变量经过高低位互换(如:aabbccdd -> ddccbbaa)后就是我们计算出来的 md5 值。

举个栗子🌰

  1. 假设待加密的字符串为 abc

  2. 把字符串转化为16进制形式 - 616263

  3. 补位。即在二进制形式的信息后面先添一个 1 ,然后接若干个 0 直到满足 len(message) % 512 == 448 这一条件。16进制下我们在 616263 后加一个 80 (即二进制的 10000000 ),把它按照规则补位到 448 bit ,也就是56字节。

  4. 补长度。完成补位后,第 57 个字节存储的是补位之前信息的长度。原来的信息为 abc ,3个字符,3个字节,24 bit,换成16进制后为 0x18 ,其后补充7个 0x00 以补满 64 字节。

  5. 利用完成前几步补足操作的数据进行复杂运算。取出 64 字节信息,第一轮运算中使用的链变量为初始链变量,之后每一次运算链变量都会被覆盖更新,最后一轮运算产生的链变量经过高低位互换后就是我们得到的 MD5 值。

0x02 哈希长度扩展攻击

MD5的补位操作正是实现长度扩展攻击的关键。

我们虽然不知道具体的 salt 值,但如果我们得到了其 hash 值以及一个可控的信息,我们就可以利用这些点进行哈希长度扩展攻击。我们得到的 hash 值正是最后一轮运算产生的链变量经过高低位互换后得到的结果,如果我们要把可控的信息进行下一轮运算,只需要知道上一轮信息产生的链变量。

回到开头贴的那份代码,关键语句为

1
2
3
if ($role==="admin" && $hsh === md5($salt.strrev($_COOKIE["role"]))) {    
$auth = true;
}

简单说一下思路:我们可以从 cookie 里拿到一段已知的 hash ,我们也知道需要校验的内容( admin ),salt 与其长度是未知的,但我们可以通过哈希长度扩展攻击来构造一段想利用的校验内容,即使不知道 salt 也可以得出它的 hash 值。

先将明文进行分组与填充,在其后添加我们想要增加的新内容,即新的校验内容,然后我们把原来得到的 hash 值逆为 key 值(注意 md5 中的值都是小端的),根据 MD5 加密原理,我们已经得到了 key ,就可以得出下一轮的 hash 值了(例如此处的 admin 的 hash 值。)

因为这个题里还有一个 strrev 函数(字符串反转),构造如下 payload:

1
2
3
4
原校验的内容:;"tseug":5:s
新添加的内容:;"nimda":5:s
hash值:3a4727d57463f122833d9e732f94e4e0
salt 长度未知,需要进行爆破

之前的 wp 里用的是 hash_extender 这个工具,这里使用的是 hashpump 。

\x 都换成 % ,可以得到

1
2
role = s%3a5%3a"admin"%3b%00%00%00%00%00%00%00%c0%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%00%80s%3a5%3a"guest"%3b
hsh = fcdc3840332555511c4e4323f6decb07

最后修改一下Cookie得到flag。

修复方法:用 hash($SECRET, hash($message)) 的方式,这样用户就不可控 message 了,另外使用 HMAC 也是可以的。

  1. 1. 0x00 引言
  2. 2. 0x01 简单了解hash函数
  3. 3. 0x02 哈希长度扩展攻击