[WP] 第二届“熵密杯”全赛题解析

by nebula

第一赛段

初始谜题1

首先,注意到信息有固定的长度为 18 的前缀,一个块的长度为 16,因此我们可以轻松的知道第一个块对应的 plaintext 和 ciphertext,进而还原出第一个 block 的 key。

接下来正常进行秘钥派生(使用题目所给的解密函数)就可以解出结果了

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
from sympy import Mod, Integer
from sympy.core.numbers import mod_inverse
from Crypto.Util.number import *

# 模数
N_HEX = "FFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFF7203DF6B21C6052B53BBF40939D54123"
MODULUS = Integer(int(N_HEX, 16))
MSG_PREFIX = "CryptoCup message:"

# 解密函数
def decrypt_message(encrypted_message, key=-1):
num_blocks = len(encrypted_message) // 32
blocks = [encrypted_message[i * 32:(i + 1) * 32] for i in range(num_blocks)]

decrypted_blocks = []

k = key

# 解密每个分组
for block in blocks:
block_int = int.from_bytes(block, byteorder='big')
if k == -1:
# get key
decrypted_block_int = bytes_to_long(MSG_PREFIX[:16].encode())
k = block_int * mod_inverse(decrypted_block_int, MODULUS) % MODULUS

key_inv = mod_inverse(k, MODULUS)
decrypted_block_int = Mod(block_int * key_inv, MODULUS)
decrypted_blocks.append(decrypted_block_int)
k += 1 # 密钥自增1

# 将解密后的分组连接成最终的明文
decrypted_message = b''.join(
int(block_int).to_bytes(16, byteorder='big') for block_int in decrypted_blocks
)

# 去除前缀
if decrypted_message.startswith(MSG_PREFIX.encode('utf-8')):
decrypted_message = decrypted_message[len(MSG_PREFIX):]

return decrypted_message.rstrip(b'\x00').decode('utf-8')



encrypted_message = bytes.fromhex('9780b05ea8decefb932468a5e95202c055003062d7ced47b2bc83396bf535c9679ffe947e9eea132752f057f2c3efa9b5ddc364907ecd5d5a1c6c92c8e33927612b58f9fbd1a1039fd35c51b65961f551862c2ce7aa5096fb67185cc5a19260948f190a5379f57181883a615fabae29bf4cfa26e0614062a4e5c64501540fc38')
decrypted_message = decrypt_message(encrypted_message)
print("Decrypted Message:", decrypted_message)

初始谜题2

首先直接点开 gmssl 库源码进行阅读学习。

注意到,sm3 将输入划分为 64 字节一个块,然后由块 1~i 的哈希值和块 i+1 的内容计算出块 i+1 的哈希值,因此可以进行 Hash Append Attack。
接下来阅读 padding 逻辑:最后 8 字节为原信息长度,其他填充部分第一个字节为 \x80,其余为 \x00。

思路已经明确:构造足够长的 counter(超出第一个块的长度),使第一个块不变。
此时可以根据已有 token 和第二个块计算出新 token

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import binascii
from gmssl import sm3, func
from Crypto.Util.number import *

counter = 0x7501e6ea
token = 0xf4ce927c79b616e8e8f7223828794eedf9b16591ae572172572d51e135e0d21a

counter_new = bytes.fromhex(hex(counter)[2:])
counter_new += b'\x80' + b'\x00' * 19 # padding
counter_new += b'\x00' * 6 + b'\x01\x20' # len
counter_new += b'\xff' * 4 # counter_append
last_block = b'\xff' * 4
last_block += b'\x80' + b'\x00' * 51 # padding
last_block += b'\x00' * 6 + b'\x02\x20' # len

prefHashValue = bytes.fromhex(hex(token)[2:])
prefHashValue = [bytes_to_long(prefHashValue[i:i+4]) for i in range(0, 32, 4)]
NewHashValue = sm3.sm3_cf(prefHashValue, func.bytes_to_list(last_block))
NewHashValue = ''.join(['%08x'%val for val in NewHashValue])

print('counter:', counter_new.hex())
print('token:', NewHashValue)

初始谜题3

已知: c1, c2, A, b

根据题意可知:

c1=xAc2=xb+e1+mq2c1 = x \cdot A\\ c2 = x \cdot b + e1 + m \cdot \frac{q}{2}

化简得:

x=c1A1e1+mq2=xbx = c1 \cdot A^{-1}\\ e1 + m \cdot \frac{q}{2} = x \cdot b

m 与 e1 都是只含有 0 与 1 的向量, 但是 m 的值乘了 125, 因此大于等于 125 的位置代表 m 的 1, 否则 m 对应位置为 0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import sympy as sp

A = sp.Matrix(此处内容省略)
b = sp.Matrix(此处内容省略)
c1 = sp.Matrix(此处内容省略)
c2 = sp.Matrix(此处内容省略)

q = 251
x = c1 * A.inv_mod(q)

epmq = c2 - x * b

print(epmq)

epmq = [x % 251 for x in list(epmq)]
epmq = [1 if x > 120 else 0 for x in epmq]
epmq = ''.join(str(x) for x in epmq)
epmq = int(epmq, 2)

print(bin(epmq))
print(hex(epmq))

第二赛段

flag1: GITEA 服务器

简单阅读一下 .c 文件, 逻辑比较简单,反过来写个解密, 发现了两个优化点:

  1. 比特逆序过程通过预处理加速
  2. 轮密钥加过程异或操作将按位进行改为直接进行

接下来暴力搜索 key 即可。注意编译时可以开启 -O2 选项,实际大约减少 85% 运行时间

另外可以分段开好几个程序跑(手动多线程)

判断标准:前四位是否是 pwd:。搜索到之后解压 .zip 文件得到 flag1

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
171
172
173
174
175
176
177
178
179
180
181
182
183
// #include <openssl/sha.h>
#include "stdlib.h"
#include <stdio.h>
#include <string.h>

#define ROUND 16

// S-Box 16x16
int sBox[16] = {2, 10, 4, 12, 1, 3, 9, 14, 7, 11, 8, 6, 5, 0, 15, 13};
int rBox[16] = {13, 4, 0, 5, 2, 12, 11, 8, 10, 6, 1, 9, 3, 15, 7, 14};

// 将十六进制字符串转换为 unsigned char 数组
void hex_to_bytes(const char *hex_str, unsigned char *bytes, size_t bytes_len) {
size_t hex_len = strlen(hex_str);
if (hex_len % 2 != 0 || hex_len / 2 > bytes_len) {
fprintf(stderr, "Invalid hex string length.\n");
return;
}

for (size_t i = 0; i < hex_len / 2; i++) {
sscanf(hex_str + 2 * i, "%2hhx", &bytes[i]);
}
}

// 派生轮密钥
void derive_round_key(unsigned int key, unsigned char *round_key, int length) {

unsigned int tmp = key;
for (int i = 0; i < length / 16; i++) {
memcpy(round_key + i * 16, &tmp, 4);
tmp++;
memcpy(round_key + i * 16 + 4, &tmp, 4);
tmp++;
memcpy(round_key + i * 16 + 8, &tmp, 4);
tmp++;
memcpy(round_key + i * 16 + 12, &tmp, 4);
tmp++;
}
}

// 比特逆序
int rb[256];
void reverseBits(unsigned char *state) {
unsigned char temp[16];
for (int i = 0; i < 16; i++) {
temp[15 - i] = rb[state[i]];
}
for (int i = 0; i < 16; i++) {
state[i] = temp[i];
}
}

void sBoxTransform(unsigned char *state) {
for (int i = 0; i < 16; i++) {
int lo = sBox[state[i] & 0xF];
int hi = sBox[state[i] >> 4];
state[i] = (hi << 4) | lo;
}
}
void rBoxTransform(unsigned char *state) {
for (int i = 0; i < 16; i++) {
int lo = rBox[state[i] & 0xF];
int hi = rBox[state[i] >> 4];
state[i] = (hi << 4) | lo;
}
}

void leftShiftBytes(unsigned char *state) {
unsigned char temp[16];
for (int i = 0; i < 16; i += 4) {
temp[i + 0] = state[i + 2] >> 5 | (state[i + 1] << 3);
temp[i + 1] = state[i + 3] >> 5 | (state[i + 2] << 3);
temp[i + 2] = state[i + 0] >> 5 | (state[i + 3] << 3);
temp[i + 3] = state[i + 1] >> 5 | (state[i + 0] << 3);
}
for (int i = 0; i < 16; i++) {
state[i] = temp[i];
}
}

void rightShiftBytes(unsigned char *state) {
unsigned char temp[16];
for (int i = 0; i < 16; i += 4) {
temp[i + 0] = (state[i + 2] << 5) | (state[i + 3] >> 3);
temp[i + 1] = (state[i + 0] >> 3) | (state[i + 3] << 5);
temp[i + 2] = (state[i + 0] << 5) | (state[i + 1] >> 3);
temp[i + 3] = (state[i + 1] << 5) | (state[i + 2] >> 3);
}
for (int i = 0; i < 16; i++) {
state[i] = temp[i];
}
}

// 轮密钥加
void addRoundKey(unsigned char *state, unsigned char *roundKey,
unsigned int round) {
for (int i = 0; i < 16; i++)
state[i] ^= roundKey[i + round * 16];
}

void dump(unsigned char *d) {
for (int i = 0; i < 16; i++) {
printf("%02X", d[i]);
}
printf("\n");
}

// 加密函数
void encrypt(unsigned char *password, unsigned int key,
unsigned char *ciphertext) {
unsigned char roundKeys[16 * ROUND] = {}; //

// 生成轮密钥
derive_round_key(key, roundKeys, 16 * ROUND);

// 初始状态为16字节的口令
unsigned char state[16]; // 初始状态为16字节的密码
memcpy(state, password, 16); // 初始状态为密码的初始值

// 迭代加密过程
for (int round = 0; round < ROUND; round++) {
reverseBits(state);
sBoxTransform(state);
leftShiftBytes(state);
addRoundKey(state, roundKeys, round);
}

memcpy(ciphertext, state, 16);
}

void decrypt(unsigned char *ciphertext, unsigned int key,
unsigned char *password) {
unsigned char roundKeys[16 * ROUND] = {};
derive_round_key(key, roundKeys, 16 * ROUND);
unsigned char state[16];
memcpy(state, ciphertext, 16);
for (int round = 15; round >= 0; round--) {
addRoundKey(state, roundKeys, round);
rightShiftBytes(state);
rBoxTransform(state);
reverseBits(state);
}
memcpy(password, state, 16);
}

int main() {
for (int i = 0; i <= 255; i++) {
for (int u = 0; u < 8; u++)
rb[i] |= ((i >> u) & 1) << (7 - u);
}
unsigned char password[] =
"pwd:1234xxxxabcd"; // 口令明文固定以pwd:开头,16字节的口令
unsigned int key = 0xF0FFFFFF; // 4字节的密钥
unsigned char ciphertext[16]; // 16字节的状态
unsigned char passback[17] = {0};
printf("Password: \n");
printf("%s\n", password);

encrypt(password, key, ciphertext);
decrypt(ciphertext, key, passback);
printf("%s\n", passback); // 检验解密函数正确性


memcpy(ciphertext,
"\x99\xF2\x98\x0A\xAB\x4B\xE8\x64\x0D\x8F\x32\x21\x47\xCB\xA4\x09",
16);
unsigned int s = 0xf0000000;
unsigned int e = 0x00000000;
for (unsigned int key = s; key != e; key++) {
if ((key & ((1 << 14) - 1)) == 0) {
printf("key = %x (%.2lf%%)\n", key, (key - s) * 100. / (e - s));
}
decrypt(ciphertext, key, passback);
if (passback[0] == 'p' && passback[1] == 'w' && passback[2] == 'd' &&
passback[3] == ':') {
printf("%x\n", key);
printf("%16s\n", passback);
break;
// 94b05686
// fab7c49d
}
}
}

flag2: 协同签名源码文件

代码内容很繁杂,但是只看两个文件注释部分就能知道大致逻辑 (变量关系)
注意几个关键变量(为什么关键?名字带 k 代表 key)的来源: k1, k2, k3

其中 k1 为前端密钥
查找 k2, k3 的来源的时候发现, k2 = k3(即漏洞所在)
因此联立 s2, s3 的公式就可以推出 d2

s2=d2k3modns3=d2(r+k2)modnd2=s3s2rmodns2 = d2 \cdot k3 \bmod n\\ s3 = d2 \cdot (r+k2) \bmod n\\ \Downarrow\\ d2=\frac{s3-s2}{r} \bmod n

1
2
3
4
5
6
7
8
9
10
11
from Crypto.Util.number import *


n = 0xFFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFF7203DF6B21C6052B53BBF40939D54123
r = 0xC2B7B217894974EC9B9F89C3047A1D4FDC598C8E6618990544AE9294BEEA21F7
s2 = 0x091F61678088CEF35F6D550E69B794ADBBC83ACDC03B11AE71EE4BB386F3C37D
s3 = 0xBEEBE5AF8877372971DCA1D7D1F5EE064AA48B59DCA838F8A6E24A76970A34B0

dif = s3 - s2
d2 = inverse(r, n) * dif % n
print(f'flag2{{{hex(d2)[2:]}}}')

flag3: 数据库管理系统 [登录]

简单读一下 login.go 的逻辑, 发现核验证书的时候并没有核验证书是否为本人持有。因此考虑构造一组 PrivateKey - PublicKey(Cert),关键点在于如何找到一组对应的裸公钥 & 裸私钥

考虑寻找本地资源。所有 python 包发布时均携带 README,以 METADATA 形式存在。在 python 的 site-packages 目录下打开 gmssl-3.2.2.dist-info,找到 METADATA

成功找到 METADATA 中的例子对应的裸公私钥

此处 private_key 有前缀 ‘00’ 需去除, public_key 少前缀 ‘04’ 需加上

然后即可用公钥注册用户,用私钥和生成的证书进行登录,即可获得 flag

flag4: 数据库管理系统 [流量包解密]

注意到 iv, key 的生成逻辑均为伪随机数, 考虑根据 iv 求解出伪随机数 seed 首先, 伪随机数是一个线性同余生成器的模型, 因此可以简化 genRandom 的循环

1
2
3
4
5
mult = 1
add = 0
for _ in range(ITERATIONS):
mult = (mult * MULTIPLIER) & MASK
add = (add * MULTIPLIER + ADDEND) & MASK

接下来, 注意到 global_seed 的高 32 位即为输出, 考虑暴力枚举低 32 位
有假 seed, 要结合 iv 进行核验 (假 seed 原因: mult 不存在模 2^32 的逆元)

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
from Crypto.Util.number import *
from tqdm import tqdm, trange
import sys

MULTIPLIER = 6364136223846793005
ADDEND = 1
MASK = 0xffffffffffffffff
ITERATIONS = 1000

iv_bytes = bytes.fromhex('90fc5cf2e2f47488a257fd51e0ae615b')
iv0 = bytes_to_long(iv_bytes[:4])
iv1 = bytes_to_long(iv_bytes[4:8])
print(f'[+] {hex(iv0) = }')
print(f'[+] {hex(iv1) = }')

mult = 1
add = 0
for _ in range(ITERATIONS):
mult = (mult * MULTIPLIER) & MASK
add = (add * MULTIPLIER + ADDEND) & MASK

print(f'[+] {mult = }')
print(f'[+] {add = }')

a = sys.argv[1] # 通过参数手动八线程
a = int(a)
s = (1 << 32) // 8 * a
e = (1 << 32) // 8 * (a + 1)

print(f'[+] range: [{s}, {e})')

for low_bit in trange(s, e):
cur_seed = iv0 << 32 | low_bit
cur_seed = (cur_seed * mult + add) & MASK
cur_seed = (cur_seed >> 32) & 0xffffffff
if cur_seed == iv1:
print(f'[+] low_bit found: {hex(low_bit)}')
# 0xea3632d2
# 0xb8bcf1e5

Final Challenge: 伪造总经理签名

非常有意思的一道题目,结合了 flag2 和 flag4 中得到的信息。

  • flag2 给出了多端签名的具体流程(公式)
  • flag4 流量包里包含了一次签名的全过程(及数据)

那么伪造签名其实就很简单了。flag4 流量包中大部分的数值其实可以复用(没有抗重放攻击),只有跟 e(message 的 hash)相关的要重新计算,即不需要考虑椭圆曲线相关部分

注意到唯二的未知量: k1, d1,可以联立 s, s1 对应的式子进行求解

{s1=k11(e+d11r1)modns=d1k1s2+d1s3rmodn\begin{cases} s1 = k1^{-1} \cdot (e + d1^{-1} \cdot r1) \bmod n\\ s = d1\cdot k1\cdot s2 + d1\cdot s3 -r \bmod n \end{cases}

1
2
3
4
5
6
# sage 联立求解 k1, d1
Zp = Zmod(n)
Ring.<d1> = PolynomialRing(Zp)
f = d1 * (e + r1 / d1) / s1 * s2 + d1 * s3 - r - s
print(f.small_roots())
# 70876251652018951816204531333898961264581396631311308791889131135075769962727*d1 + 28389347226065243237592735608129939252293860285881733191501012145796335719821

然后简单带入 flag2 中得到的相关公式就可以得到伪造后的签名啦

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 求出 k1, d1
k = 70876251652018951816204531333898961264581396631311308791889131135075769962727
b = 28389347226065243237592735608129939252293860285881733191501012145796335719821
d1 = -b * inverse(k, n) % n
k1 = (e + r1 * inverse(d1, n)) * inverse(s1, n) % n
print(f'{d1 = }')
print(f'{k1 = }')

# python 进行签名伪造
x1 = (r - e) % n

e_new = 0x9e810778a6b177c6aa1799365977adfbeef605c19b5ea917527d1541c1339019
d2 = 0xa61bdbacbad62b141284a6955b14a27df01c09984e23785ec75b5e5c79e18f62
s1 = inverse(k1, n) * (e_new + inverse(d1, n) * q1x) % n
k2 = k3 = s2 * inverse(d2, n) % n
r = (e_new + x1) % n
s2 = (d2 * k3) % n
s3 = (d2 * (r+k2)) % n
s = (d1 * k1 * s2 + d1 * s3 - r) % n
print(hex(r)[2:] + hex(s)[2:])
# 3dfc09bda8a41dd4d6818bb09687c223f3be57998de0bc8434585bde9671c6e7a4372c7f5d440454f0d0617c58e538667a63733d95b232812859630081592816

联系方式

See About