hash长度扩展攻击研究

0x01前言

其实这个漏洞在好久之前就遇到过,只是当时水平有限,一直没有静下心来研究一下。最近一直在整理ctf的知识点,查缺补漏,下定决心要整明白这玩意。忙活了这两三天,算是初步搞定了吧(大体理解原理,知道如何利用)。。。在这里记录一下,尽最大努力说明白吧。。。

0x02漏洞简介

哈希长度扩展攻击(Hash Length Extension Attacks)是指针对某些允许包含额外信息的加密散列函数的攻击手段。
该攻击适用于在消息与密钥的长度已知的情形下,所有采取了 H(密钥 ∥ 消息) 此类构造的散列函数。MD5和SHA-1等基于Merkle–Damgård构造的算法均对此类攻击显示出脆弱性。

这种定义类的话一看就头大,我们以实验吧上的一个题目(让我进去)为例来说明。
关键代码如下:

$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));

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

  • 我们知道md5($SECRET . urldecode($username . $password))的值
  • 我们知道$SECRET的长度
  • 我们可以算出另外一个 md5 值和另外一个 getmein 的值,使得$COOKIE['getmein'] == md5($SECRET.urldecode($username.$password))

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

0x03hash摘要算法的实现(md5为例)

md5算法的实现如下图

下面详细来说明一下md5的加密过程:

  1. 我们要实现对于字符串abc的 md5 的值计算。首先我们要把其转化为 16 进制。
  2. 补位
    消息必须进行补位,即使得其长度在对 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。
  3. 补长度
    补位过后,倒数第8 个字节储存的是补位之前的消息长度。abc是 3 个字母,也就是 3 个字节,24 bit。换算成 16 进制为 0x18。其后跟着 7 个字节的 0x00,把消息补满 64 字节。
  4. 计算消息摘要
    计算消息摘要必须用补位已经补长度完成之后的消息来进行运算,拿出 512 bit的消息(即64字节)。 计算消息摘要的时候,有一个初始的链变量,用来参与第一轮的运算。MD5 的初始链变量为:
    A=0x67452301 B=0xefcdab89 C=0x98badcfe D=0x10325476 (注意这里这4个值是在md5算法中写死的写死的。。。。)
    我们不需要关心计算细节,我们只需要知道经过一次消息摘要后,上面的链变量将会被新的值覆盖,而最后一轮产生的链变量经过高低位互换(如:aabbccdd -> ddccbbaa)后就是我们计算出来的 md5 值。

0x04长度扩展攻击

问题就出在覆盖上。我们在不知道具体 $SECRET 的情况下,得知了其 hash 值,以及我们有一个可控的消息。 而我们得到的 hash 值正是`最后一轮摘要后的经过高地位互换的链变量`。 我们可以想像一下,在常规的摘要之后把我们的控制的信息进行下一轮摘要,只需要知道上一轮消息产生的链变量(也就是上题中的`md5($secret."adminadmin"))`。
上题符合:

  1. 消息可控已知
  2. 密钥长度已知
  3. 使用MD5加密(基于Merkle–Damgård构造的算法)

可以使用hash长度扩展攻击 求出$x $y满足md5($secret.'admin$x')=$y 首先将`md5($secret."adminadmin")`也就是571580b26c65f306376d4f64e53cb5c7 高低位逆转作为初始链变量(此处具体过程是:将32位的md5平均分成4份,然后将这4个string转化为16进制,得到的就是初始链变量即上文提到的A,B,C,D。结合下面的代码会更容易理解)然后对附加值(随便一个长度不为0的字符串)以修改后的初始链变量进行MD5加密得到新的md5值。
下面是我从github上找的实现代码,做了简单的修改

# -*- coding: UTF-8 -*-

# 引入math模块,因为要用到sin函数
import math

# 定义每轮中用到的函数。L为循环左移,注意左移之后可能会超过32位,所以要和0xffffffff做与运算,确保结果为32位。
F = lambda x, y, z: ((x & y) | ((~x) & z))
G = lambda x, y, z: ((x & z) | (y & (~z)))
H = lambda x, y, z: (x ^ y ^ z)
I = lambda x, y, z: (y ^ (x | (~z)))
L = lambda x, n: (((x << n) | (x >> (32 - n))) & (0xffffffff))

# 定义每轮中循环左移的位数,这里用4个元组表示,用元组是因为速度比列表快。
shi_1 = (7, 12, 17, 22) * 4
shi_2 = (5, 9, 14, 20) * 4
shi_3 = (4, 11, 16, 23) * 4
shi_4 = (6, 10, 15, 21) * 4

# 定义每轮中用到的M[i]次序。
m_1 = (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15)
m_2 = (1, 6, 11, 0, 5, 10, 15, 4, 9, 14, 3, 8, 13, 2, 7, 12)
m_3 = (5, 8, 11, 14, 1, 4, 7, 10, 13, 0, 3, 6, 9, 12, 15, 2)
m_4 = (0, 7, 14, 5, 12, 3, 10, 1, 8, 15, 6, 13, 4, 11, 2, 9)

abcd_list = ['0x67452301', '0xefcdab89', '0x98badcfe', '0x10325476']

# 定义函数,用来产生常数T[i],常数有可能超过32位,同样需要&0xffffffff操作。注意返回的是十进制的数。
def T(i):
    result = (int(4294967296 * abs(math.sin(i)))) & 0xffffffff
    return result

# 定义函数,用来将列表中的元素循环右移。原因是在每轮操作中,先运算A的值,然后是D,C,B,16轮之后右恢复原来顺序,所以只要每次操作第一个元素即可。
def shift(shift_list):
    shift_list = [shift_list[3], shift_list[0], shift_list[1], shift_list[2]]
    return shift_list

# 定义主要的函数,参数为当做种子的列表,每轮用到的F,G,H,I,生成的M[],以及循环左移的位数。该函数完成一轮运算。
def fun(fun_list, f, m, shi):
    count = 0
    global Ti_count
    # 引入全局变量,T(i)是从1到64循环的。
    while count < 16:
        xx = int(fun_list[0], 16) + f(int(fun_list[1], 16), int(fun_list[2], 16), int(fun_list[3], 16)) + int(m[count], 16) + T(Ti_count)
        xx &= 0xffffffff
        ll = L(xx, shi[count])
        fun_list[0] = hex((int(fun_list[1], 16) + ll) & 0xffffffff)[:-1]
        # 最后的[:-1]是为了去除类似'0x12345678L'最后的'L'
        fun_list = shift(fun_list)
        count += 1
        Ti_count += 1
        # print fun_list
    return fun_list

# 该函数生成每轮需要的M[],最后的参数是为了当有很多分组时,进行偏移。
def genM16(order, ascii_list, f_offset):
    ii = 0
    m16 = [0] * 16
    f_offset *= 64
    for i in order:
        i *= 4
        m16[ii] = '0x' + ''.join((ascii_list[i + f_offset] + ascii_list[i + 1 + f_offset] + ascii_list[
            i + 2 + f_offset] + ascii_list[i + 3 + f_offset]).split('0x'))
        ii += 1
    for ind in range(len(m16)):
        m16[ind] = reverse_hex(m16[ind])
    return m16

# 翻转十六进制数的顺序:'0x01234567' => '0x67452301'
def reverse_hex(hex_str):
    hex_str = hex_str[2:]
    if len(hex_str) < 8:
        hex_str = '0' * (8 - len(hex_str)) + hex_str
    hex_str_list = []
    for i in range(0, len(hex_str), 2):
        hex_str_list.append(hex_str[i:i + 2])
    hex_str_list.reverse()
    hex_str_result = '0x' + ''.join(hex_str_list)
    return hex_str_result

# 显示结果函数,将最后运算的结果列表进行翻转,合并成字符串的操作。
def show_result(f_list):
    result = ''
    f_list1 = [0] * 4
    for i in f_list:
        f_list1[f_list.index(i)] = reverse_hex(i)[2:]
        result += f_list1[f_list.index(i)]
    return result

def padding(input_m, msg_lenth = 0):
    # 对每一个输入先添加一个'0x80',即'10000000'
    ascii_list = map(hex, map(ord, list(input_m)))
    msg_lenth += len(ascii_list) * 8
    ascii_list.append('0x80')
    for i in range(len(ascii_list)):
        if len(ascii_list[i]) < 4:
            ascii_list[i] = '0x' + '0' + ascii_list[i][2:]
    # 补充0
    while (len(ascii_list) * 8 + 64) % 512 != 0:
        ascii_list.append('0x00')

    # 最后64为存放消息长度,注意长度存放顺序低位在前。例如,消息为'a',则长度为'0x0800000000000000'
    msg_lenth_0x = hex(msg_lenth)[2:]
    msg_lenth_0x = '0x' + msg_lenth_0x.rjust(16, '0')
    msg_lenth_0x_big_order = reverse_hex(msg_lenth_0x)[2:]
    msg_lenth_0x_list = []
    for i in range(0, len(msg_lenth_0x_big_order), 2):
        msg_lenth_0x_list.append('0x' + msg_lenth_0x_big_order[i:i + 2])
    ascii_list.extend(msg_lenth_0x_list)
    #print ascii_list
    return ascii_list

def md5(ascii_list):
    global Ti_count
    global abcd_list
    Ti_count = 1
    #abcd_list = ['0x67452301', '0xefcdab89', '0x98badcfe', '0x10325476']
    #ascii_list = padding(input_m)

    # 对每个分组进行4轮运算
    for i in range(0, len(ascii_list) / 64):
        # 将最初128位种子存放在变量中,
        aa, bb, cc, dd = abcd_list

        # 根据顺序产生每轮M[]列表
        order_1 = genM16(m_1, ascii_list, i)
        order_2 = genM16(m_2, ascii_list, i)
        order_3 = genM16(m_3, ascii_list, i)
        order_4 = genM16(m_4, ascii_list, i)

        # 主要四轮运算,注意打印结果列表已经被进行过右移操作!
        abcd_list = fun(abcd_list, F, order_1, shi_1)
        abcd_list = fun(abcd_list, G, order_2, shi_2)
        abcd_list = fun(abcd_list, H, order_3, shi_3)
        abcd_list = fun(abcd_list, I, order_4, shi_4)

        # 将最后输出与最初128位种子相加,注意,最初种子不能直接使用abcd_list[0]等,因为abcd_list已经被改变
        output_a = hex((int(abcd_list[0], 16) + int(aa, 16)) & 0xffffffff)[:-1]
        output_b = hex((int(abcd_list[1], 16) + int(bb, 16)) & 0xffffffff)[:-1]
        output_c = hex((int(abcd_list[2], 16) + int(cc, 16)) & 0xffffffff)[:-1]
        output_d = hex((int(abcd_list[3], 16) + int(dd, 16)) & 0xffffffff)[:-1]

        # 将输出放到列表中,作为下一次128位种子
        abcd_list = [output_a, output_b, output_c, output_d]

        # 将全局变量Ti_count恢复,一遍开始下一个分组的操作。
        Ti_count = 1
        # print show_result(abcd_list)

    return show_result(abcd_list)

def update_abcd_list(secret):
    global abcd_list
    abcd_list = []
    for i in range(0, 32, 8):
        abcd_list.append(reverse_hex('0x' + secret[i: i + 8]))
    return abcd_list

def md5_attack(secret, msg_length, suffix):
    global Ti_count
    update_abcd_list(secret)
    ascii_list = padding(suffix, (msg_length + 64) / 64 * 64 * 8)
    print ascii_list
    return md5(ascii_list)
    #print abcd_list

if __name__ == '__main__':
    msg = '123456'
    print msg
    secret = md5(padding(msg))
    print secret
    print md5_attack(secret, len(msg), 'seaii')
    print md5()

其实我们并不需要关心md5的加密算法是如何实现,重点看这个函数,真正实现攻击的就这个函数。

def md5_attack(secret, msg_length, suffix):
    global Ti_count
    update_abcd_list(secret)   #获取初始链变量
    #保证附加值前面有至少512bit的数据
    ascii_list = padding(suffix, (msg_length + 64) / 64 * 64 * 8)
    print ascii_list
    return md5(ascii_list)    #进行加密
    #print abcd_list

回到上面的题目,只要我们将数据填充到512(512的倍数)bit,再加上我们的附加值,就可以算出一个新的hash值,更换cookie,就可以拿到flag
长度扩展前,一个例子如下:
密文为$secret
数据为adminadmin
md5为571580b26c65f306376d4f64e53cb5c7
扩展后
密文为$secret
数据为adminadmin%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%c8%00%00%00%00%00%00%00pcat
md5为3e67e8f0c05e1ad68020df30bbc505f5

0x05利用工具HashPump

  1. 安装

    git clone https://github.com/bwall/HashPump 
    apt-get install g++ libssl-dev 
    cd HashPump 
    make 
    make install
    #想在python里实现hashpump,可以使用hashpumpy插件:
    pip install hashpumpy
    python >>> import hashpumpy >>> help(hashpumpy.hashpump)
  2. 使用
    # hashpump
    Input Signature: 加密值  md5(secret.xxx)
    Input Data: 附加值       xxx
    Input Key Length: 明文长度 len(secret)
    Input Data to Add: 想要添加的值  suffix

0x06漏洞实战

这种攻击一般出现在ctf中,在实战中利用较少,找来找去就只有p牛博客上的这个例子:
phpwind 利用哈希长度扩展攻击进行getshell
具体的分析过程文章写的很详细了,就不班门弄斧了。。。

0x07总结+参考资料

写了这么久,总是感觉有好多东西还没说清楚。。。很多都是直接复制人家的,专业性强的话还是写不出来。。。好在自己理解了。。。

标签: web, 密码学
添加新评论