sm3长度拓展攻击

在打ctf的时候遇到的一道hash_append题，找了很久的脚本但是没一个能用之后非常生气，所以自己写一个

在已知原来的secretInfo的长度和hash之后，如何在补上append_data之后，预测到新的hash

即：

1
2
new_hash = sm3(secretInfo+append_data)
求解 new_hash

也就是说，在不知道secretInfo，只知道len(secretInfo)和sm3(secretInfo)的情况下，如何计算new_hash

那么这里的难点其实在于如何生成append_data

分析：

首先看已知条件，hash其实是由V _i+1 = CF(V_i , B_i )得到的V_i+1

例如：对于secretInfo为’abcd’*16，即官方文档中的61626364 61626364 61626364 61626364 61626364 61626364 61626364 61626364 61626364 61626364 61626364 61626364 61626364 61626364 61626364 61626364

在计算sm3时其实是先补全，再分组进行CF操作

1
2
3
4
5
6
对于上述的例子，补全之后的十六进制字符串为：
61626364 61626364 61626364 61626364 61626364 61626364 61626364 61626364
61626364 61626364 61626364 61626364 61626364 61626364 61626364 61626364
80000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000200
(有一说一啊，官方文档这里好像写错了，有一个0写成8了)

hash = sm3(secretInfo)，那么如果让append_data = ‘80000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000200’，那么补全之后的msg不也是可以预测的吗，那么我们就可以据此计算出new_hash

1
2
3
4
5
6
7
对于secretInfo+append_data，补全之后的十六进制字符串为：
61626364 61626364 61626364 61626364 61626364 61626364 61626364 61626364
61626364 61626364 61626364 61626364 61626364 61626364 61626364 61626364
80000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000200
80000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000400

从官方文档中可以知道，旧的hash实际上是作为新的V_i使用，因此在计算sercetInfo+append_data时，只需根据secretInfo+append_data的长度计算出新的B_i，就可以使用CF(V_i，B_i)计算出new_hash

1
2
3
4
5
对于上例，sm3(secretInfo) = debe9ff9 2275b8a1 38604889 c18e5a4d 6fdb70e5 387e5765 293dcba3 9c0c5732
也就是说V_i = debe9ff9 2275b8a1 38604889 c18e5a4d 6fdb70e5 387e5765 293dcba3 9c0c5732
B_i = 80000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000400
那么new_hash = V_i+1 = CF(V_i,B_i)

虽然只分析了length=64的情况，但是实际上都是差不多的

脚本分析

1
https://github.com/zx2023qj/sm3LengthExtensionAttack
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
#sm3Master.py
from gmssl import sm3


# sm3任意长度拓展攻击脚本(大概，如果没写错的话，当然是不可能超过2^512bit的)

# 把十六进制字符串拆分成8个为一个单位的字符串，用于把旧的hash拆分为新的IV
def split_hex_string(hex_string):
    hex_list = [int(hex_string[i:i + 8], 16) for i in range(0, len(hex_string), 8)]
    return hex_list


def generate_append_data(length):
    # 针对不同长度的secret_Info进行补全，也就是生成append_data
    # mod 为1-55,64
    if length % 64 < 56:
        left_length = 2 * (64 - length % 64) - 10
        append_data = "80" + left_length * "0" + hex(length * 8)[2:].zfill(8)
    # mod 为56-63
    else:
        left_length = 64 - length % 64 - 1
        append_data = '80' + left_length * '0' + 120 * '0' + hex(length * 8)[2:].zfill(8)
    return append_data


# length是字符串的长度，64个Byte
def sm3master(origin_hash, length):
    # 把旧的hash拆分为新的IV
    new_IV = split_hex_string(origin_hash)
    result = ""
    # 根据length的长度生成append_data，其实就是补全操作
    append_data = generate_append_data(length)
    # 长度是算的bit，要乘8；length是字符串，乘8，append_data是hex，乘4
    final_length = length * 8 + len(append_data) * 4
    # 根据新的msg(info+append_data)生成的new_B
    new_B = '80' + 118 * '0' + hex(final_length)[2:].zfill(8)
    new_B = bytes.fromhex(new_B)
    new_B = [i for i in bytes(new_B)]
    y = sm3.sm3_cf(new_IV, new_B)
    for i in y:
        result = '%s%08x' % (result, i)
    return result

Reference

1
https://oscca.gov.cn/sca/xxgk/2010-12/17/1002389/files/302a3ada057c4a73830536d03e683110.pdf