浅谈简单Hash算法

hash算法的经典代表md5、sha1。其在进行Hash值运算时，会根据计算对象的数据长度进行分组，之后对分组后的数据一组一组地进行迭代运算。

简单原理

长度分组

将目标对象的数据长度转化为16进制数据或者二进制数据，若按16进制数据计算，则每56Bytes为一组，不足56bytes则对其进行填充——以16进制0x80为首填充字节，后跟0x00，直到该组数据长度被填充到56bytes停下；然后在每一组56字节的数据后再加八个字节——该八个字节为该组数据未填充前的 bit 长度，即len(该组原数据) * 8 bit

迭代运算

分组完成后，就会得到一组组长度为64bytes的数据，以此为基础，hash散列算法会以每组数据为基础进行每一轮的运算。这里因为没有学习hash散列算法的实现，不清楚其运算的过程，故以hash_process(data[i]) 代表每轮的运算过程。data[i] 为分组后的数据，一次用一组。

hash散列函数内置有一个初始数据 seed ，每一轮 hash_process 的运算都会更新该seed——每一轮运算的结果都会覆盖上一个 seed 的值，最后一个 seed 的值进行一次自身的位置置换即为最终的hash值

如此，hash的运算可以用如下代码片段表示：

1
2
3
4
5
6
7
8
9
10

int seed=xxxx;
int data[k]={xxxx};
for(int i=0;i<k;i++)
{
    seed=hash_process(data[i],seed)
}
/*
seed 自身数值位置置换
*/
hash值=seed

实例

比方说我们对xibai这个字符串进行md5的运算:

1
2
3
4
5
6

len('xibai')=5  #所以填充(56-5)=51个字节，填充后为：
'xibai'+'\x80'+'\x00'*50   #然后加上八字节的原数据bit长度记录，len('xibai')*8=40=0x28
#此时该组数据为：
'xibai'+'\x80'+'\x00'*50+'\x00\x00\x00\x00\x00\x00\x00\x28'
#如此是为一组，然后将其与内置的初始seed进行运算，得到新的seed值
seed=hash_process(data[0],seed)

加盐(+salt)

所谓加盐的hash，即在原始数据前面加上一串n字节的数据。

这么一来，加盐的hash计算可以用一下代码来表示其简单流程：

1
2
3
4
5
6
7
8
9
10
11

int seed=xxxx;
int salt=xxxx;
int data[k]={xxxx};  //其中data[0]='salt+原第一组数据'
for(int i=0;i<k;i++)
{
    seed=hash_process(data[i],seed)
}
/*
seed 自身数值位置置换
*/
hash值=seed

一般而言salt是随机生成的一串数据，保存在 其 本地。

Hash长度扩展攻击

由以上分析，我们可以发现，当用户可以获取服务器运算后的hash值时，即便服务器本地有一个我们所不知道的 salt ，我们也有机会控制服务器的hash运算结果。

在本地 计算 服务器的hash运算结果

由以上分析我们可以知道，服务器采用加盐哈希时，如果我们能拿到服务器用 salt 加 我们的输入所计算的hash值时，我们就可以猜测salt的长度来进行hash长度扩展攻击。

而在ctf中，salt的长度往往会给出，此时，我们拥有salt的长度、我们自己的输入、服务器运算出的hash值。

如此一来我们可以控制我们的输入来控制服务器的hash值运算，如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

//服务器
int seed=xxxx;
int salt=xxxx;
int str='输入';  //输入等于'a'*(56-salt.length)
int data[k]= 分组（salt+str）;
//通过hash的分组规则可知，data数据为一组：'salt'+'a'*(56-salt.length)+'\x00'*6+'\x0200'
for(int i=0;i<k;i++)
{
    seed=hash_process(data[i],seed)
}
/*
seed 自身数值位置置换
*/
hash值=seed;

此时我们就获取了第一组数据长度为56字节时的hash值，此刻若我们再多输入一些字符，如 xibai，服务器的计算会变成如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

int seed=xxxx;
int salt=xxxx;
int str='输入';
int data[k]= 分组（salt+str）;
//因为我们是基于上面的输入多输入了五个字符，所以这次分组后的data为两组
//第一组显然和上面是一样的
//第二组则为'xibai'+'\x80'+'\x00'*57+'\x28'
for(int i=0;i<k;i++)
{
    seed=hash_process(data[i],seed)
}
//此时可以发现，第一组数据一样时，其第一轮运算的结果显然也是一样的，而第二轮的计算则是基于第一轮得到的seed进行的
//若我们在本地直接用第一轮的seed来进行后续的计算，如此就可得到服务器本地所计算出来的hash值
//从而以此去通过服务器的hash验证，使其可以对我们的输入执行之后的指令

实例

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
26
27
28
29

$flag = "XXXXXXXXXXXXXXXXXXXXXXX";
$secret = "XXXXXXXXXXXXXXX"; // This secret is 15 characters long for security!
 
$username = $_POST["username"];
$password = $_POST["password"];
 
if (!empty($_COOKIE["getmein"])) {
    if (urldecode($username) === "admin" && urldecode($password) != "admin") {
        if ($COOKIE["getmein"] === md5($secret . urldecode($username . $password))) {
            echo "Congratulations! You are a registered user.\n";
            die ("The flag is ". $flag);
        }
        else {
            die ("Your cookies don't match up! STOP HACKING THIS SITE.");
        }
    } else {
        die ("You are not an admin! LEAVE.");
    }
}
 
setcookie("sample-hash", md5($secret . urldecode("admin" . "admin")), time() + (60 * 60 * 24 * 7));
 
if (empty($_COOKIE["source"])) {
    setcookie("source", 0, time() + (60 * 60 * 24 * 7));
} else {
    if ($_COOKIE["source"] != 0) {
        echo ""; // This source code is outputted here
    }
}

以实验吧的一道web题为例，我们知道了 secret+”adminadmin“ 的md5值，并且我们知道secret的长度为15，

这样我们就可以在本地计算出输出长度大于41后的md5值，通过输入长度扩展，从而控制最终的md5值，达到绕过攻击的目的。

这里推荐一个工具 HashPump

kali里安装hashpump：

1
2
3
4
5

git clone https://github.com/bwall/HashPump
apt-get install g++ libssl-dev #kali
cd HashPump
make
make install

本题中使用HashPump的各个参数解释如下

1
2
3
4

Input Signature 为COOKIES中hsh的值
Input Data 为用户名
Input Key Length 为长度
Input Data to Add 为密码（自定义，除了admin）

预防Hash扩展攻击

解决这个漏洞的办法是使用HMAC算法。该算法大概来说是这样 ：Hash值 =
hash(salt + hash(salt + 输入))，而不是简单的直接对输入进行一次这种加盐hash运算。

具体HMAC的工作原理有些复杂，但你可以有个大概的了解。重点是，由于这种算法进行了双重摘要，密钥不再受本文中的长度扩展攻击影响。HMAC最先是在1996年被发表，之后几乎被添加到每一种编程语言的标准函数库中。

或者也可以使用 hash值=hash（输入+slat） 也可以起到预防的效果，因为这样一来，salt的位置不再固定，就无法进行hash值的准确预测。����