哈希长度拓展攻击

1.什么是MAC?

MAC就是Message Authentication Codes，即消息验证码

🔐 MAC的核心作用

  • 认证性（Authenticity）：确保消息的发送者是声称的人，即消息确实是由合法的发送者生成。
  • 完整性（Integrity）：验证消息在传输过程中是否被篡改或损坏。

为了实现这些功能，发送者使用一个秘密密钥和MAC算法生成一个认证标签（MAC值），这个标签随消息一起发送。接收者也拥有同样的密钥，可以用相同算法重新生成MAC值。如果重新计算的值和收到的值一致，就可以确认消息没有被改动。

这个标签也叫做tag

MAC系统包含以下三个算法

  • A key generation algorithm selects a key from the key space uniformly at random.
  • A MAC generation algorithm efficiently returns a tag given the key and the message.
  • A verifying algorithm efficiently verifies the authenticity of the message given the same key and the tag. That is, return accepted when the message and tag are not tampered with or forged, and otherwise return rejected.
img

发送者和接受者共享密钥k，然后发送者用k和message计算MAC值，然后将message和MAC一起发送，接受者用k再计算一次message的MAC，比较是否相等

MAC值可以用来验证文件(消息)是否改动，MAC值具有“雪崩效应“，哪怕1bit的变化，就会产生完全不同的MAC值

2.HMAC

In cryptography, an HMAC (sometimes expanded as either keyed-hash message authentication code or hash-based message authentication code) is a specific type of message authentication code (MAC) involving a cryptographic hash function and a secret cryptographic key.

总而言之HMAC就是基于hash的MAC

它的MAC generation algorithm是用HASH函数计算的

具体算法是

3.Merkle–Damgård结构

也称MD结构，耳熟能详的MD5算法

MD结构算法是

🛠️ 具体流程：

1. 消息填充（padding）：

  • 把原始消息 M 填充成多个 固定长度的块（通常是 512 bit）
  • 填充方式会在最后加上原始消息的长度信息

这里值得细说：

先分块，但是通常不会刚好完整分块，总会剩几个

举个例子，“HashInput",它的hex就是0x48617368496e707574

假设我们以64bits为一个block，那就是16个hex位

48 61 73 68 49 6e 70 75, 74 00 00 00 00 00 00 00

第二块只有一个74，假设我们后面全部填充成0

那这样会导致什么后果呢？

这导致0x48617368496e70757400，0x48617368496e7075740000，0x48617368496e707574000000

这一系列的'HashInput'，'HashInput'

得到的hash值都一样了，那不就碰撞了吗？我们还是希望hash函数尽量是一个单射

所以我们要填充一个bit位，也就是填充一个开头为1，后面都是0的，这样看1在哪里，就能区分出前缀一样的message了

也就是填充一个10000000（一个字节，也就是0x80）

48 61 73 68 49 6e 70 75, 74 80 00 00 00 00 00 00

MD结构还把长度信息填充到最后

48 61 73 68 49 6e 70 75, 74 80 00 00 00 00 00 09

img

2. 设置初始值（IV）：

  • 固定的哈希初始值（如 SHA-256 的 IV 是 8 个固定常数）

3. 迭代压缩函数 F：

  • 每个块依次输入 F(prev_hash, block) 得到下一个中间状态
  • 每一步的输出变成下一步的输入

4. 最后一个输出就是 hash 结果：

  • 最后一轮的压缩输出就是最终的摘要值

4.Length-extension attack

In cryptography and computer security, a length extension attack is a type of attack where an attacker can use Hash(message1) and the length of message1 to calculate Hash(message1 ‖ message2) for an attacker-controlled message2, without needing to know the content of message1.

如果我们知道Hash(message1)和message1的长度，我们就可以计算Hash(message1||message2)而不用知道message1的内容

1.MD5拓展长度攻击

img

MD5分块填充后，每个块会分成小块和四个寄存器ABCD运算，每个寄存器里32bits,最后输出寄存器的值就是MD5值

然后前一个块计算完之后的ABCD会作为下一个块的初始ABCD

那么这就意味着，我们可以从Message1的md5值中恢复ABCD的值，然后修改MD5算法中ABCD的初始值，用新的参数计算message2的MD5

得到的就是MD5(message1||message2)了

但注意这里的message2的前缀是要有要求的，必须是message1原来的填充pad，不是随便添加message2

举个例子，message1是

message1 = b"this is a test"

填充完是

1
b'this is atest\x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00p\x00\x00\x00\x00\x00\x00\x00'

message2是b"extension"

如果是message1||message2

1
b'this is a testextension\x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\xb8\x00\x00\x00\x00\x00\x00\x00'

如果直接添加message2的话，MD5只会在后面填充，这就不对了，所以我们要手动填充message2,

也就是令

1
pad+message2 = \x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00p\x00\x00\x00\x00\x00\x00\x00extension

看看这样的填充，这样message1+pad +message2填充就是

1
b'this is a test\x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00p\x00\x00\x00\x00\x00\x00\x00extension\x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00H\x02\x00\x00\x00\x00\x00\x00'

可以看到前面一部分一样了，这样当我们计算extension后面的md5的时候，ABCD就是计算完message1的ABCD

也就能计算出整个MD5了

我们可以使用魔改MD5

先提取ABCD

1
2
3
4
5
6
7
8
9
10
11
12
13
def big_endian(hexstring):
    s = []
    for i in range(0,len(hexstring),2):
        s.append(hexstring[i:i+2])
    s = s[::-1]
    return "".join(s)
def get_states(md5_value):
    state = []
    for i in range(0,len(md5_value),8):
        state.append(int(big_endian(md5_value[i:i+8]),16))
    return state

A,B,C,D = get_states(md5_value)

然后用这个ABCD去计算message2的hash值，但要注意，message2填充的长度是总长度，这样才能和message1+pad+message2的长度对上

exp:

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
import struct
import math

class MD5:
    def __init__(self, A=0x67452301, B=0xefcdab89, C=0x98badcfe, D=0x10325476):
        self.A = A
        self.B = B
        self.C = C
        self.D = D

    def _left_rotate(self, x, c):
        return ((x << c) | (x >> (32 - c))) & 0xFFFFFFFF

    def _padding(self, message, total_length=None):
        if total_length is None:
            total_length = len(message)
        bit_len = total_length * 8
        message += b'\x80'
        while len(message) % 64 != 56:
            message += b'\x00'
        message += struct.pack('<Q', bit_len)
        return message

    def _process_chunk(self, chunk):
        M = struct.unpack('<16I', chunk)
        A, B, C, D = self.A, self.B, self.C, self.D

        # 定义四个基本函数
        def F(x, y, z): return (x & y) | (~x & z)
        def G(x, y, z): return (x & z) | (y & ~z)
        def H(x, y, z): return x ^ y ^ z
        def I(x, y, z): return y ^ (x | ~z)

        # 各轮用到的函数和 g 值选择
        functions = [F, G, H, I]
        index_funcs = [
            lambda i: i,
            lambda i: (5 * i + 1) % 16,
            lambda i: (3 * i + 5) % 16,
            lambda i: (7 * i) % 16
        ]

        # 每轮对应的移位值
        shifts = [
            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
        ]

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

        for i in range(64):
            f_index = i // 16
            f = functions[f_index]
            g = index_funcs[f_index](i)
            temp = (A + f(B, C, D) + M[g] + T[i]) & 0xFFFFFFFF
            temp = self._left_rotate(temp, shifts[i])
            A, D, C, B = D, C, B, (B + temp) & 0xFFFFFFFF

        self.A = (self.A + A) & 0xFFFFFFFF
        self.B = (self.B + B) & 0xFFFFFFFF
        self.C = (self.C + C) & 0xFFFFFFFF
        self.D = (self.D + D) & 0xFFFFFFFF

    def hash(self, message: bytes) -> str:
        padded = self._padding(message)
        for i in range(0, len(padded), 64):
            self._process_chunk(padded[i:i + 64])
        return ''.join(f'{x:02x}' for x in struct.pack('<4I', self.A, self.B, self.C, self.D))
    def attack(self,message,total_length):
        padded = self._padding(message,total_length)
        for i in range(0, len(padded), 64):
            self._process_chunk(padded[i:i + 64])
        return ''.join(f'{x:02x}' for x in struct.pack('<4I', self.A, self.B, self.C, self.D))
# 原始消息
message1 = b"this is a test"
pad = MD5()._padding(message1)[len(message1):]
message2 = b'extension'
md5 = MD5()
md5_value = md5.hash(message1)
print(f"[+]拓展完如下：{md5._padding(message1+pad+message2)}")
# 提取中间状态
def big_endian(hexstring):
    s = []
    for i in range(0,len(hexstring),2):
        s.append(hexstring[i:i+2])
    s = s[::-1]
    return "".join(s)
def get_states(md5_value):
    state = []
    for i in range(0,len(md5_value),8):
        state.append(int(big_endian(md5_value[i:i+8]),16))
    return state

A,B,C,D = get_states(md5_value)
# 构造伪造的消息（攻击者伪造的完整消息）
forged_message = message1 + pad + message2

# 使用伪造状态进行 length extension
md5_forged = MD5(A,B,C,D)

forged_hash = md5_forged.attack(message2,len(pad)+len(message1)+len(message2))

print(f"[+] 原始 hash:     {md5_value}")
print(f"[+]拓展完的hash: {MD5().hash(forged_message)}")
print(f"[+] 伪造的消息:    {forged_message}")
print(f"[+] 伪造后的 hash: {forged_hash}")
print(f"[+] 验证 hash(伪造消息) 是否一致：")
print(MD5().hash(forged_message) == forged_hash)

2.SM3拓展长度攻击

SM3算法也是基于MD结构的，和MD5的填充基本一致，只有一处不同

那就是SM3算法填充长度是大端序，MD5是小端序

SM3 填充过程

对于消息 "abc" (长度3字节 = 24位)：

  1. 原始消息: 0x61 0x62 0x63
  2. 添加 0x80: 0x61 0x62 0x63 0x80
  3. 填充0x00直到长度56字节: [0x61 0x62 0x63 0x80] + [0x00]*52
  4. 添加64位长度(大端序): 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x18

MD5 填充过程

对于同样的消息 "abc"：

  1. 原始消息: 0x61 0x62 0x63
  2. 添加 0x80: 0x61 0x62 0x63 0x80
  3. 填充0x00直到长度56字节: [0x61 0x62 0x63 0x80] + [0x00]*52
  4. 添加64位长度(小端序): 0x18 0x00 0x00 0x00 0x00 0x00 0x00 0x00

SM3的压缩算法更加复杂，有8个寄存器，不过由于是大端序，倒是少了转换的步骤

我们大体了解一下就行，压缩函数是CF(IV,block)

IV是上一个block算出来的SM3值，然后初值IV是给定的，这都和MD5类似，那么照搬MD5的长度拓展攻击就行了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def SM3_len_ex_ak(num_block,IV,plaintext):
    Vtemp=IV
    a=(len(plaintext)*4+1 ) % 512
    #print(a)
    k=0
    B=[]
    if a<=448:
        k=448-a
    elif a>448:
        k=512-a+448
    #print(k)
    m=plaintext+"8"+"0"*int((k+1)/4-1)+zero_fill(str(hex(len(plaintext)*4+num_block*512))[2:],16) #填充
    #print(m)
    block_len=int((len(plaintext)*4 + k + 65) / 512)
    #print(block_len)
    for i in range(0,block_len):
        B.append(m[128*i:128*i+128])     #分组
    #print("B:",B)
    for i in range(0,block_len):
        Vtemp=CF(Vtemp,B[i])

    return Vtemp

以熵密杯2024为例

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
import binascii
from gmssl import sm3


# 读取HMAC key文件
def read_hmac_key(file_path):
    with open(file_path, 'rb') as f:
        hmac_key = f.read().strip()
    return hmac_key


# 生成token
def generate_token(hmac_key, counter):
    # 如果HMAC_KEY长度不足32字节，则在末尾补0，超过64字节则截断
    if len(hmac_key) < 32:
        hmac_key = hmac_key.ljust(32, b'\x00')
    elif len(hmac_key) > 32:
        hmac_key = hmac_key[:32]

    # 将计数器转换为字节表示
    counter_bytes = counter.to_bytes((counter.bit_length() + 7) // 8, 'big')
    # print("counter_bytes:", binascii.hexlify(counter_bytes))

    tobe_hashed = bytearray(hmac_key + counter_bytes)

    # print("tobe_hashed:", binascii.hexlify(tobe_hashed))

    # 使用SM3算法计算哈希值
    sm3_hash = sm3.sm3_hash(tobe_hashed)

    # 将SM3的哈希值转换为十六进制字符串作为token
    token = sm3_hash

    return token


current_counter = 0


def verify_token(hmac_key, counter, token):
    # 生成token
    generated_token = generate_token(hmac_key, counter)
    global current_counter
    # 比较生成的token和输入的token是否相同
    if generated_token == token:
        if counter & 0xFFFFFFFF > current_counter:
            current_counter = counter & 0xFFFFFFFF
            print("current_counter: ", hex(current_counter))
            return "Success"
        else:
            return "Error: counter must be increasing"
    else:
        return "Error: token not match"


# 假设HMAC key文件路径
hmac_key_file = 'hmac_key.txt'
# 假设计数器值
counter = 0x12345678

# 读取HMAC key
hmac_key = read_hmac_key(hmac_key_file)

# 生成token
token = generate_token(hmac_key, counter)
print("Generated token:", token)
print(verify_token(hmac_key, counter, token))

虽然说是HMAC吧，但是他这里实现的其实就是MAC

题目要求给定一个counter+hash

然后输出一个更大的counter+hash

我们只要在后面加上一个，这样一定是最大的

exp:

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
def zero_fill(a,n):
    if len(a)<n:
        a="0"*(n-len(a))+a
    return a
def cycle_shift_left( B, n):
    n=n%32
    return ((B << n) ^ (B >> (32 - n)))%(2**32)

def T(j):
    if j>=0 and j<=15:
        return int("79cc4519",16)
    elif j>=16 and j<=63:
        return int("7a879d8a",16)

def FF(X,Y,Z,j):
    if j>=0 and j<=15:
        return X^Y^Z
    elif j>=16 and j<=63:
        return (X&Y)|(X&Z)|(Y&Z)
def GG(X,Y,Z,j):
    if j >= 0 and j <= 15:
        return X ^ Y ^ Z
    elif j >= 16 and j <= 63:
        return (X & Y) | (~X & Z)

def P0(x):
    return x^(cycle_shift_left(x,9))^cycle_shift_left(x,17)
def P1(x):
    return x^(cycle_shift_left(x,15))^cycle_shift_left(x,23)

def Message_extension(a):  #a的数一定要满足512bit,不够要补零!!  ,承接的是字符串
    W1 = []            #  W0-15
    W2=[]             #  W' 0-63
    #print("a消息扩展的a:",a)
    for i in range(int(len(a) / 8)):
        W1.append(int(a[8 * i:8 * i + 8],16))
        #print("W1的前16个",a[8 * i:8 * i + 8])
    for j in range(16,68):
        temp=P1(W1[j-16] ^ W1[j-9] ^ cycle_shift_left(W1[j-3],15)) ^cycle_shift_left(W1[j-13],7)^W1[j-6]
        #print("消息扩展：",hex(temp))
        W1.append(temp)

    for j in range(0,64):
        W2.append(W1[j]^W1[j+4])

    W1.append(W2)
    return W1

def CF(V,Bi):  #V是字符串
    Bi=zero_fill(Bi,128)
    W=[]
    W=Message_extension(Bi)   #消息扩展完的消息字
    #print("W:",W)
    A=int(V[0:8],16)
    #print("A:", hex(A))
    B = int(V[8:16], 16)
    C = int(V[16:24], 16)
    D = int(V[24:32], 16)
    E = int(V[32:40], 16)
    F = int(V[40:48], 16)
    G = int(V[48:56], 16)
    H = int(V[56:64], 16)
    for j in range(0,64):
        temp=(cycle_shift_left(A,12) + E +cycle_shift_left(T(j),j)) %(2**32)
        SS1=cycle_shift_left(temp,7)
        SS2=SS1 ^ cycle_shift_left(A,12)
        TT1=(FF(A,B,C,j) +D +SS2 +W[-1][j] ) %(2**32)
        TT2=(GG(E,F,G,j)+H+SS1+W[j])%(2**32)
        D=C
        C=cycle_shift_left(B,9)
        B=A
        A=TT1
        H=G
        G=cycle_shift_left(F,19)
        F=E
        E=P0(TT2)
        #print("B:", hex(B))
    t1=zero_fill(hex(A^int(V[0:8],16))[2:],8)
    t2 = zero_fill(hex(B ^ int(V[8:16], 16))[2:], 8)
    t3 = zero_fill(hex(C ^ int(V[16:24], 16))[2:], 8)
    t4 = zero_fill(hex(D ^ int(V[24:32], 16))[2:], 8)
    t5 = zero_fill(hex(E ^ int(V[32:40], 16))[2:], 8)
    t6 = zero_fill(hex(F ^ int(V[40:48], 16))[2:], 8)
    t7 = zero_fill(hex(G ^ int(V[48:56], 16))[2:], 8)
    t8 = zero_fill(hex(H ^ int(V[56:64], 16))[2:], 8)
    t=t1+t2+t3+t4+t5+t6+t7+t8
    return t

def SM3(plaintext):
    Vtemp=IV
    a=(len(plaintext)*4+1 ) % 512
    #print(a)
    k=0
    B=[]
    if a<=448:
        k=448-a
    elif a>448:
        k=512-a+448
    #print(k)
    m=plaintext+"8"+"0"*int((k+1)/4-1)+zero_fill(str(hex(len(plaintext)*4))[2:],16)
    #print(m)
    block_len=int((len(plaintext)*4 + k + 65) / 512)
    #print(block_len)
    for i in range(0,block_len):
        B.append(m[128*i:128*i+128])     #分组
    #print("B:",B)
    for i in range(0,block_len):
        Vtemp=CF(Vtemp,B[i])

    return Vtemp

def SM3_len_ex_ak(num_block,IV,plaintext):
    Vtemp=IV
    a=(len(plaintext)*4+1 ) % 512
    #print(a)
    k=0
    B=[]
    if a<=448:
        k=448-a
    elif a>448:
        k=512-a+448
    #print(k)
    m=plaintext+"8"+"0"*int((k+1)/4-1)+zero_fill(str(hex(len(plaintext)*4+num_block*512))[2:],16)
    #print(m)
    block_len=int((len(plaintext)*4 + k + 65) / 512)
    #print(block_len)
    for i in range(0,block_len):
        B.append(m[128*i:128*i+128])     #分组
    #print("B:",B)
    for i in range(0,block_len):
        Vtemp=CF(Vtemp,B[i])

    return Vtemp

IV="7380166f4914b2b9172442d7da8a0600a96f30bc163138aae38dee4db0fb0e4e"


#############################################################################
IV2="f81b58b75c469707402e44054d4d45dcacb0294daba39501f5353e20b6fcfe2a"
num_block=1
counter = "fde43312"
New_Counter = hex(int((bin(int(counter,16))[2:].zfill(32) + "1") + "0"*(448 - 32*8 - 1 - 4*8) + bin(36*8)[2:].zfill(64) , 2))[2:] + "ffffffff"

print(New_Counter)
print(SM3_len_ex_ak(1,IV2,"FFFFFFFF"))