哈希长度扩展攻击解析
起因
这是 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,也要进行补位。补位是必须的。
补位的方式的二进制表示是在消息的后面加上一个1
,后面跟着无限个0
,直到 len(message) % 512 == 448
。在 16 进制下,我们需要在消息后补80
,就是 2 进制的10000000
。我们把消息abc
进行补位到 448 bit,也就是 56 byte。
补长度
补位过后,第 57 个字节储存的是补位之前的消息长度。abc
是 3 个字母,也就是 3 个字节,24 bit。换算成 16 进制为 0x18。其后跟着 7 个字节的 0x00,把消息补满 64 字节。
计算消息摘要
计算消息摘要必须用补位已经补长度完成之后的消息来进行运算,拿出 512 bit的消息(即64字节)。 计算消息摘要的时候,有一个初始的链变量,用来参与第一轮的运算。MD5 的初始链变量为:
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。
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之后为
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
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。
刷新后发现已经通过验证。
总结
看起来很难理解,我本人也通宵了一晚上才搞定。当然因为我比较笨QAQ。总之,这是个很好玩的东西,大家可以去复现一下。
另外这个问题的解决方案为:hash($SECRET, hash($message))
。这样就可以避免用户可控 message 了。
参考:https://blog.skullsecurity.org/2012/everything-you-need-to-know-about-hash-length-extension-attacks