哈希长度扩展攻击解析

JP_Morgen 2014-05-18

展开全文

这是 ISCC 上的一道题目，抄 PCTF 的，并且给予了简化。在利用简化过的方式通过后，突然想起利用哈希长度扩展攻击来进行通关。哈希长度扩展攻击是一个很有意思的东西，利用了 md5、sha1 等加密算法的缺陷，可以在不知道原始密钥的情况下来进行计算出一个对应的 hash 值。
这里是 ISCC 中题目中的 admin.php 的算法：

$auth = false; if (isset($_COOKIE["auth"])) { $auth = unserialize($_COOKIE["auth"]); $hsh = $_COOKIE["hsh"]; if ($hsh !== md5($SECRET . strrev($_COOKIE["auth"]))) { //$SECRET is a 8-bit salt $auth = false;

}

} else { $auth = false; $s = serialize($auth);

setcookie("auth", $s);

setcookie("hsh", md5($SECRET . strrev($s)));

}

了解哈希长度扩展攻击

哈希长度扩展攻击适用于加密情况为： hash($SECRET, $message) 的情况，其中 hash 最常见的就是 md5、hash1。我们可以在不知道 $SECRET 的情况下推算出另外一个匹配的值。如上例所给的 PHP 代码：

我们知道 md5($SECRET . strrev($_COOKIE["auth"])) 的值我们知道 $hsh 的值我们可以算出另外一个 md5 值和另外一个 $hsh 的值，使得$hsh == md5($SECRET . strrev($_COOKIE["auth"]))

这样即可通过验证。如果要理解哈希长度扩展攻击，我们要先理解消息摘要算法的实现。以下拿 md5 算法举例。

md5 算法实现

我们要实现对于字符串 abc 的 md5 的值计算。首先我们要把其转化为 16 进制。

补位

消息必须进行补位，即使得其长度在对 512 取模后的值为 448。也就是说，len(message) % 512 == 448 。当消息长度不满 448 bit 时（注意是位，而不是字符串长度），消息长度达到 448 bit 即可。当然，如果消息长度已经达到 448 bit，也要进行补位。补位是必须的。
补位的方式的二进制表示是在消息的后面加上一个，后面跟着无限个，直到len(message) % 512 == 448 。在 16 进制下，我们需要在消息后补，就是 2 进制的。我们把消息 abc 进行补位到 448 bit，也就是 56 byte。

补长度

补位过后，第 57 个字节储存的是补位之前的消息长度。 abc 是 3 个字母，也就是 3 个字节，24 bit。换算成 16 进制为 0x18。其后跟着 7 个字节的 0x00，把消息补满 64 字节。

计算消息摘要

计算消息摘要必须用补位已经补长度完成之后的消息来进行运算，拿出 512 bit的消息（即64字节）。计算消息摘要的时候，有一个初始的链变量，用来参与第一轮的运算。MD5 的初始链变量为：

1	`A=0x67452301` `B=0xefcdab89` `C=0x98badcfe` `D=0x10325476`

我们不需要关系计算细节，我们只需要知道经过一次消息摘要后，上面的链变量将会被新的值覆盖，而最后一轮产生的链变量经过高低位互换（如：aabbccdd -> ddccbbaa）后就是我们计算出来的 md5 值。

哈希长度扩展攻击的实现

问题就出在覆盖上。我们在不知道具体 $SECRET 的情况下，得知了其 hash 值，以及我们有一个可控的消息。而我们得到的 hash 值正是最后一轮摘要后的经过高地位互换的链变量。我们可以想像一下，在常规的摘要之后把我们的控制的信息进行下一轮摘要，只需要知道上一轮消息产生的链变量。
有点难理解，因为我都看的头大。看起来我们把实现放在攻击场景里会更好。
仍然是如上的 PHP。因为其走了一点弯路（strrev、unserialize），所以我们修改一下。

$auth = "I_L0vE_L0li"; if (isset($_COOKIE["auth"])) { $hsh = $_COOKIE["hsh"]; if ($hsh !== md5($SECRET . $_COOKIE["auth"])) { die("F4ck_U!"); }

} else { setcookie("auth", $auth); setcookie("hsh", md5($SECRET . $auth)); die("F4ck_U!");

} die("I_aM_A_L0li_dA_Yo~");

在实际环境中，我不知道 $SECRET 的值（我胡乱打的QAQ），只知道长度为 12。首先我们访问一下看看。不出意外地被 f4ck 了。
Cookie 中的 auth 为 I_L0vE_L0li ，hsh 为7a84f420f8abe642237409f9d4daa851 。我们来进行哈希长度扩展攻击。

长度扩展

我们仍然要进行补位。因为 $SECRET 的长度是 12，我们用 12 个 x 来填补一下，紧跟着就是 auth 的值。然后我们把消息补到 448 bit。接着进行补长度。然后后面跟着要附加的值，随意什么都可以。我这里是 I_aM_L01i 好了=v=。然后去掉前面的假的 $SECRET，得到最终的 $auth。

1	`I_L0vE_L0li\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\xB8\x00\x00\x00\x00\x00\x00\x00I_aM_L01i`

urlencode之后为

1	`I_L0vE_L0li%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%00%00%B8%00%00%00%00%00%00%00I_aM_L01i`

计算哈希

我在网上找了一个 C 语言的 md5 实现。因为 Python 的实现不能改初始的链变量。我修改了初始的链变量为经过高低位逆转的 $hsh。
PS：原来的是 7a84f420f8abe642237409f9d4daa851

1	`A=0x20f4847a` `B=0x42e6abf8` `C=0xf9097423` `D=0x51a8dad4`

然后我们对附加的值进行 md5 加密。附加的值为 I_aM_L01i 。首先我们把前面 64 个字节改为 64 个 A 。这是为了使得除了 hash 本身以外其他的状态完全一样（原文：Then we take the MD5 of 64 'A's. We take the MD5 of a full (64-byte) block of 'A's to ensure that any internal values — other than the state of the hash itself — are set to what we expect）。实际上，前 64 个字节填充什么都无所谓。因为在进行我们的附加值的摘要之前，我们已经把链变量覆盖了。然后我们编译并运行这个加密实现。得到了一串密文，是 1d00eac3f7da072d8365b0a7ae1fec42 。我们用 Firefox 的 firebug 插件进行修改 Cookie。