Hash长度扩展攻击

HASH原理

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

补位完成后,字符串以64位一组进行分组(因为上面的余数为56,加上8个字节的长度描述符后,正好是64位,凑成一组)。字符串能被分成几组就会进行多少次“复杂的数学变化”。每次进行“复杂的数学变化”都会生成一组新的registers值供下一次“复杂的数学变化”来调用。第一次“复杂的数学变化”会调用程序中的默认值。当后面已经没有分组可以进行数学变化时,该组生成的registers值就是最后的hash值。

为确保同一个字符串的hash值唯一,所以需要保证第一次registers的值也唯一。所以在hash算法中,registers具有初始值。如上图中的registers值0。

MD5算法实现

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

补位

(1byte=8bit)消息必须进行补位,即使得其长度在对 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。图片.png

补长度

补位过后,第 57 个字节储存的是补位之前的消息长度。abc是 3 个字母,也就是 3 个字节,24 bit。换算成 16 进制为 0x18。其后跟着 7 个字节的 0x00,把消息补满 64 字节。
MD5中存储的都是小端方式!
MD5中存储的都是小端方式!
MD5中存储的都是小端方式!
重要的事情说三遍,举个例子:假如我们这一块值为0x12345678
那么在MD5运算时候存储的顺序是 0x78563412
这也是之所以后8字节为长度,而第1字节先有数据的原因

图片.png

计算消息摘要

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

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

上面的链变量将会被新的值覆盖。之后有四个非线性函数,将字符串和那四个链接变量经过一系列的复杂运算,算出一组新的A,B,C,D的值,如果消息小于512,也就是只需要计算一次,这时候将新的ABCD的值按ABCD的顺序级联,然后输出,就是MD5的值,如果消息大于512的话,就需要计算多次,先计算出前512位的ABCD值然后用再用这个ABCD去计算后面512位的ABCD值以此类推,最后计算出来的ABCD经过拼接就是这串字符串的MD5值。

哈希长度扩展攻击的实现

ISCC2018一道题目

<?php
include "secret.php";
@$username=(string)$_POST['username'];
function enc($text){
    global $key;
    return md5($key.$text);
}
if(enc($username) === $_COOKIE['verify']){
    if(is_numeric(strpos($username, "admin"))){
        die($flag);
    }
    else{
        die("you are not admin");
    }
}
else{
    setcookie("verify", enc("guest"), time()+60*60*24*7);
    setcookie("len", strlen($key), time()+60*60*24*7);
}
show_source(__FILE__);

我们在不知道具体$key的值但是知道他长度的情况下,知道了md5($key+guest)的值。而我们得到的 hash 值正是最后一轮摘要后的经过高地位互换的链变量。在常规的摘要之后把我们控制的信息进行下一轮摘要,只需要知道上一轮消息产生的链变量。图片.png
COOKIE中,MD5($key+guest)=78cfc57d983b4a17e55828c001a3e781,以及$key的长度为46。我们来进行哈希长度扩展攻击。

长度扩展

补位,因为$key的长度是46,我们用46个x来填补,然后跟着的是guest。接着把消息补到448bit。也就是补充够56byte。然后补长度,51字节*8bit=408bit转换为16进制就是198。MD5中小端方式存储
图片.png
然后后面跟着要附加的值admin。
图片.png
然后去掉前面的假的 $key,得到最终的 $username。
guest\x80\x00\x00\x00\x00\x98\x01\x00\x00\x00\x00\x00\x00admin
urlencode之后为
guest%80%00%00%00%00%98%01%00%00%00%00%00%00admin
带入enc函数返回的就是md5($key+guest+admin)的值。
然后把md5($key+guest)值作为加密admin的初始链变量

A=0x7d57cf78
B=0x174a3b98
c=0xc02858e5
d=0x81e7a301

图片.png
用hashpump脚本跑一下求出其md5值5f585093a7fe86971766c3d25c43d0eb,抓包放入cookie中。图片.png
大体就是,原本的md5($key+$username)小于512bit,直接用初始的链变量计算一次就计算出了md5值。题目要求enc($username)===enc("guest"),而且$username中要包含admin。我们可以通过填充把username扩展超过512bit,让他进行两次计算,第二次计算使用到的链变量是第一次计算得到的md5($key+guest)覆盖掉原来的链变量让他作为加密admin的链变量,最后把cookie改为这个经过覆盖的链表量+admin的md5加密值。就可以满足条件