概要

哈希函数将任意长度的输入(又叫做预映射, pre-image),通过散列算法,变换成固定长度的输出,该输出就是散列值,得到hash(散列),下面是一般模型:

由于哈希函数的输出空间是有限的,而输入空间是无限的,因此在理论上存在多个不同的输入可以生成相同的哈希值,这就是所谓的哈希冲突。对于任何一个哈希值,存在着若干消息与之对应,称为碰撞

同样的,这种转换是不可逆的,因为散列值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出,所以不可能从散列值来唯一的确定输入值。

对于一个哈希函数,需要满足:

输入长度可变、输入长度固定、效率高、单向加密(对于哈希值$h$,无法直接得到$H(x)=h$)、抗弱碰撞(对于任意消息$x$,很难通过计算找到另一消息$y$使得$H(x)=H(y)$)、抗强碰撞(找到任意一对$H(x)=H(y)$在计算上不可行)、伪随机性。

常用的哈希函数有MD5、sha1、sha256、sha512。

哈希函数还具有明显的雪崩效应。

雪崩效应:密码学术语,指当输入发生最微小的改变也会导致输出的不可区分改变。

Proof_Of_Work

各大比赛经常会有的工作量证明,常见形式:

1
2
3
4
5
6
7
8
9
10
11
def proof_of_work():
random.seed(os.urandom(8))
proof = ''.join([random.choice(string.ascii_letters+string.digits) for _ in range(20)])
_hexdigest = sha256(proof.encode()).hexdigest()
print(f"sha256(XXXX+{proof[4:]}) == {_hexdigest}")
print('Give me XXXX: ')
x = input()
if len(x) != 4 or sha256(x.encode()+proof[4:].encode()).hexdigest() != _hexdigest:
print('Wrong PoW')
return False
return True

爆破四位,可以使用itertoolsproduct

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import itertools
import hashlib
from pwn import *

r = remote(...)

k = (r.recvuntil(b') == ', drop=1)[-16:]).decode()
res = r.recvline().strip().decode()

for item in itertools.product(string.ascii_letters + string.digits, repeat=4):
str1 = ''.join(item) + k
m = hashlib.sha256(str1.encode()).hexdigest()
if m == res:
break

print(str1)

key1=''.join(item).encode()
print(key1.decode())
r.sendline(key1)

MD5

MD5的输入为任意长的消息,512bit长的分组。输出为128bit的消息摘要(32位hex)。

有时候部分网站提供的MD5哈希值为16位,这16位其实就是从32位转化过来的(去掉前八位和后八位),使用较短的哈希值可能会提高一些性能,但是由于哈希冲突问题,一般建议使用完整的 128 位 MD5 哈希值来确保较高的数据完整性和唯一性。

通常对于某个哈希函数的初始化,如果出现这四个IV:0x67452301,0xEFCDAB89,0x98BADCFE,0x10325476,那么就可以猜测为MD5函数,因为这是MD5的初始IV。

可以根据哈希大概率唯一且不可逆的性质,可以对数据进行唯一性标识。例如通过比较用户登陆传过来的用户名密码的哈希值和后端是否一致,可以判断用户是否合法。

MD5流程

padding

首先先来考虑一下MD5的数据填充逻辑:

之前我们知道,MD5的分组为512bit(64字节)的分组,接下来进行填充;

填充规则是使其对于位长对512求余的结果等于448。

满足的整个分组直接保留,不满足56字节明文数据的分组,后加0x80(10000000),如果还不够56字节长度,继续添加M个0x00字节到达56字节长度,后面的8个字节用字节序表示明文数据的比特数。

当明文长度刚好为$64N+56$字节长度时,直接新加一个分组,第一位为0x80,剩下63位全部为0x00,最后添加这个56字节分组的字节序表示。

多说无益,直接给出一个填充代码:

1
2
3
4
5
6
7
def padding_message(msg: bytes) -> bytes:
orig_len_in_bits = (8 * len(msg)) & 0xffffffffffffffff
msg += bytes([0x80])
while len(msg) % 64 != 56:
msg += bytes([0x00])
msg += orig_len_in_bits.to_bytes(8, byteorder = 'little')
return msg

变换

当我们对消息进行分组padding后,MD5算法会对每组消息64字节一组分别经过64轮数学变换。

关键在于:在运算过程中,每个消息块都会和一个输入向量做一个运算,把结果当成下个消息块的输入向量。听起来和CBC模式有些相似。

在运算开始时,会有一个默认的初始化向量(我们称作默认幻数):

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

好像很眼熟,这就是MD5初始化的那四个向量。

这四个向量组合之后和第一块进行运算,得到新的四个幻数,继续和第二组等不断运算,包括最后一组填充的分组。得到四个最终幻数ABCD,彼此连接之后得到最终的哈希值。

加盐哈希

哈希函数的唯一性输出会带来一个显著问题:确定性明文带来的确定性哈希问题。根据常见的明文,构造对应的哈希表进行暴力破解成为可能。

如果我们在创建密码时增加额外的随机内容(加盐),使得密码的盐都不一样,这样我们在验证时和盐加在一起做哈希,就几乎不可能进行暴力攻击了:

那么这种思路真的可靠吗?后续会继续探讨。

哈希函数拓展攻击

以下内容参考:MD5哈希碰撞之哈希长度拓展攻击 - 知乎 (zhihu.com)

基于哈希加盐

攻击条件:

1.攻击者有某个特定的明文;

2.攻击者获得了这个特定的明文的加盐哈希值;

3.攻击者知道了盐的长度,不知道具体内容。

现在模拟一个场景,一个服务端在做校验,用户输入明文信息和待验证的哈希值,服务端根据后台存储的盐,计算出加盐的哈希,比较加盐哈希与存储的哈希是否一致。

例如,这个服务器有一个长度为10字节的盐,某明文为hello,world

1
2
3
4
5
6
7
8
9
import hashlib

key = b"1234567890"
data = b"hello,world"
h = hashlib.md5(key + data)
md5_value = h.hexdigest()
print(md5_value, len(key),data)

# 95f96bd63ad51a2472b8304d4a9ffdac 10 hello,world

我们能得到加盐哈希值和密钥长度以及明文。

我们希望构造出一种添加了特定数据的明文,提前计算出对应的验证哈希值,提交服务端能验证通过。

攻击实现:

首先根据哈希还原下一次我们计算所需的幻数,然后计算出我们添加攻击数据后的哈希值。

这里的攻击数据需要满足:

添加攻击数据后,之前的正常加盐哈希能计算出来;

添加攻击数据后,服务端计算出的加盐哈希值和攻击者期望一致。

提供代码(题目取自VNCTF2024):

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
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
# 参考:https://github.com/bkfish/Script-DES-Crypto/blob/master/MD5/python3/md5.py

import hashlib
import math
from typing import Any, Dict, List
from Crypto.Util.number import *
from pwn import *

rotate_amounts = [7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22,
5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20,
4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23,
6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21]

constants = [int(abs(math.sin(i + 1)) * 2 ** 32) & 0xFFFFFFFF for i in range(64)]

functions = 16 * [lambda b, c, d: (b & c) | (~b & d)] + \
16 * [lambda b, c, d: (d & b) | (~d & c)] + \
16 * [lambda b, c, d: b ^ c ^ d] + \
16 * [lambda b, c, d: c ^ (b | ~d)]

index_functions = 16 * [lambda i: i] + \
16 * [lambda i: (5 * i + 1) % 16] + \
16 * [lambda i: (3 * i + 5) % 16] + \
16 * [lambda i: (7 * i) % 16]


def get_init_values(A: int = 0x67452301, B: int = 0xefcdab89, C: int = 0x98badcfe, D: int = 0x10325476) -> List[int]:
return [A, B, C, D]


def left_rotate(x, amount):
x &= 0xFFFFFFFF
return ((x << amount) | (x >> (32 - amount))) & 0xFFFFFFFF


def padding_message(msg: bytes) -> bytes:
"""
在MD5算法中,首先需要对输入信息进行填充,使其位长对512求余的结果等于448,并且填充必须进行,即使其位长对512求余的结果等于448。
因此,信息的位长(Bits Length)将被扩展至N*512+448,N为一个非负整数,N可以是零。
填充的方法如下:
1) 在信息的后面填充一个1和无数个0,直到满足上面的条件时才停止用0对信息的填充。
2) 在这个结果后面附加一个以64位二进制表示的填充前信息长度(单位为Bit),如果二进制表示的填充前信息长度超过64位,则取低64位。
经过这两步的处理,信息的位长=N*512+448+64=(N+1)*512,即长度恰好是512的整数倍。这样做的原因是为满足后面处理中对信息长度的要求。
"""
orig_len_in_bits = (8 * len(msg)) & 0xffffffffffffffff
msg += bytes([0x80])
while len(msg) % 64 != 56:
msg += bytes([0x00])
msg += orig_len_in_bits.to_bytes(8, byteorder = 'little')
return msg


def md5(message: bytes, A: int = 0x67452301, B: int = 0xefcdab89, C: int = 0x98badcfe, D: int = 0x10325476) -> int:
message = padding_message(message)
hash_pieces = get_init_values(A, B, C, D)[:]
for chunk_ofst in range(0, len(message), 64):
a, b, c, d = hash_pieces
chunk = message[chunk_ofst:chunk_ofst + 64]
for i in range(64):
f = functions[i](b, c, d)
g = index_functions[i](i)
to_rotate = a + f + constants[i] + int.from_bytes(chunk[4 * g:4 * g + 4], byteorder = 'little')
new_b = (b + left_rotate(to_rotate, rotate_amounts[i])) & 0xFFFFFFFF
a, b, c, d = d, new_b, b, c
for i, val in enumerate([a, b, c, d]):
hash_pieces[i] += val
hash_pieces[i] &= 0xFFFFFFFF

return sum(x << (32 * i) for i, x in enumerate(hash_pieces))


def md5_to_hex(digest: int) -> str:
raw = digest.to_bytes(16, byteorder = 'little')
return '{:032x}'.format(int.from_bytes(raw, byteorder = 'big'))


def get_md5(message: bytes, A: int = 0x67452301, B: int = 0xefcdab89, C: int = 0x98badcfe, D: int = 0x10325476) -> str:
return md5_to_hex(md5(message, A, B, C, D))


def md5_attack(message: bytes, A: int = 0x67452301, B: int = 0xefcdab89, C: int = 0x98badcfe,
D: int = 0x10325476) -> int:
hash_pieces = get_init_values(A, B, C, D)[:]
for chunk_ofst in range(0, len(message), 64):
a, b, c, d = hash_pieces
chunk = message[chunk_ofst:chunk_ofst + 64]
for i in range(64):
f = functions[i](b, c, d)
g = index_functions[i](i)
to_rotate = a + f + constants[i] + int.from_bytes(chunk[4 * g:4 * g + 4], byteorder = 'little')
new_b = (b + left_rotate(to_rotate, rotate_amounts[i])) & 0xFFFFFFFF
a, b, c, d = d, new_b, b, c
for i, val in enumerate([a, b, c, d]):
hash_pieces[i] += val
hash_pieces[i] &= 0xFFFFFFFF

return sum(x << (32 * i) for i, x in enumerate(hash_pieces))


def get_init_values_from_hash_str(real_hash: str) -> List[int]:
"""

Args:
real_hash: 真实的hash结算结果

Returns: 哈希初始化值[A, B, C, D]

"""
str_list: List[str] = [real_hash[i * 8:(i + 1) * 8] for i in range(4)]
# 先按照小端字节序将十六进制字符串转换成整数,然后按照大端字节序重新读取这个数字
return [int.from_bytes(int('0x' + s, 16).to_bytes(4, byteorder = 'little'), byteorder = 'big') for s in str_list]


def get_md5_attack_materials(origin_msg: bytes, key_len: int, real_hash: str, append_data: bytes) -> Dict[str, Any]:
"""

Args:
origin_msg: 原始的消息字节流
key_len: 原始密钥(盐)的长度
real_hash: 计算出的真实的hash值
append_data: 需要添加的攻击数据

Returns: 发起攻击需要的物料信息
{
'attack_fake_msg': bytes([...]),
'attack_hash_value': str(a1b2c3d4...)
}

"""
init_values = get_init_values_from_hash_str(real_hash)
# print(['{:08x}'.format(x) for x in init_values])
# 只知道key的长度,不知道key的具体内容时,任意填充key的内容
fake_key: bytes = bytes([0xff for _ in range(key_len)])
# 计算出加了append_data后的真实填充数据
finally_padded_attack_data = padding_message(padding_message(fake_key + origin_msg) + append_data)
# 攻击者提前计算添加了攻击数据的哈希
attack_hash_value = md5_to_hex(md5_attack(finally_padded_attack_data[len(padding_message(fake_key + origin_msg)):],
A = init_values[0],
B = init_values[1],
C = init_values[2],
D = init_values[3]))
fake_padding_data = padding_message(fake_key + origin_msg)[len(fake_key + origin_msg):]
attack_fake_msg = origin_msg + fake_padding_data + append_data
return {'attack_fake_msg': attack_fake_msg, 'attack_hash_value': attack_hash_value}


if __name__ == '__main__':
sh = remote(...)
for Rounds in range(100):
print(Rounds)

sh.recvuntil(b"Round")
sh.recvuntil(b"msg:")
# 服务端根据正常的数据预先计算出来的哈希值
msg = long_to_bytes(int(sh.recvline().strip().decode(),16))
attack_data: bytes = b"SPARKLE"
sh.recvuntil(b"sign:")
h = sh.recvline().strip().decode()
md5_value = h

# 预备发起攻击,先计算构造碰撞相关的参数
attack_materials = get_md5_attack_materials(msg, 32, md5_value, attack_data)
newmsg = attack_materials['attack_fake_msg']
h = attack_materials['attack_hash_value']
sh.sendline(newmsg.hex().encode())
sh.sendline(h.encode())

sh.recvline()
sh.recvline()
print(sh.recvline())

这里添加的attack_data不确定,可以多试几个,有的会成功有的会失败。