从零学习哈希长度扩展攻击

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


引言

最开始出现好像是在PCTF2014上
最近做题突然看见了
先来看下代码

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
$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>";
}
?>

简单了解hash函数

hash函数补位

当hash函数拿到需要被hash的字符串后,先将其字节长度整除64,取得余数。如果该余数正好等于56,那么就在该字符串最后添加上8个字节的长度描述符(具体用bit表示)。如果不等于56,就先对字符串进行长度填充,填充时第一个字节为hex(80),其他字节均用hex(00)填充,填充至余数为56后,同样增加8个字节的长度描述符(该长度描述符为需要被hash的字符串的长度,不是填充之后整个字符串的长度)。以上过程,称之为补位

hash计算

补位完成后,字符串以64位一组进行分组(因为上面的余数为56,加上8个字节的长度描述符后,正好是64位,凑成一组)。字符串能被分成几组就会进行多少次“复杂的数学变化”。每次进行“复杂的数学变化”都会生成一组新的registers值供下一次“复杂的数学变化”来调用。第一次“复杂的数学变化”会调用程序中的默认值。当后面已经没有分组可以进行数学变化时,该组生成的registers值就是最后的hash值。
在sha1的运算过程中,为确保同一个字符串的sha1值唯一,所以需要保证第一次registers的值也唯一。所以在sha1算法中,registers具有初始值。如上图中的registers值0。
Hash值的随机性完全依赖于进行“复杂的数学变化”时输入的registers值和该次运算中字符串分组的数据。如果进行“复杂数学变化”时输入的registers值和该次运算的字符串分组相同,那么他们各自生成的新的registers值也相同。

如何攻击

了解题意

哈希长度扩展攻击适用于加密情况为: hash($salt . $message) 的情况,其中 hash 最常见的就是 md5、hash1。我们可以在不知道 $salt 的情况下推算出另外一个匹配的值。
如以上代码中我们已知的有:
1.$hsh = $_COOKIE[“hsh”]
2.$role = unserialize($_COOKIE[“role”])
题目要求是我们需要通过构造使得$role === “admin” 时 $hsh === md5($salt.strrev($_COOKIE[“role”]

md5的实现

先将字符串转化为16进制

补位

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

补长度

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

计算消息摘要

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

1
2
3
4
A=0x67452301
B=0xefcdab89
C=0x98badcfe
D=0x10325476

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

Attack

简化代码

为了看起来方便,简化代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
<?php
$auth = "guest";
$salt = "c014hashtest";
if (isset($_COOKIE["auth"])) {
$hsh = $_COOKIE["hsh"];
if ($hsh === md5($salt . $_COOKIE["auth"])) {
die("Welcome, admin!");
}
else{
die("You are not admin!");
}
} else {
setcookie("auth", $auth);
setcookie("hsh", md5($salt . "test"));
die("You are not admin!");
}
?>

扩展攻击

本来准备手动一步步改hex值的,结果发现了python有个HashExtender库..
那就贼简单了

不过文档上的库我没装成功。。
又发现了hashpumpy
假设已知salt长度为12和”test”但是不知道salt的值

把\x改成%直接复制进cookie
刷新

文章目录
  1. 1. 引言
  2. 2. 简单了解hash函数
    1. 2.1. hash函数补位
    2. 2.2. hash计算
  3. 3. 如何攻击
    1. 3.1. 了解题意
    2. 3.2. md5的实现
      1. 3.2.1. 补位
      2. 3.2.2. 补长度
      3. 3.2.3. 计算消息摘要
  4. 4. Attack
    1. 4.1. 简化代码
    2. 4.2. 扩展攻击