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

by nebula

第一赛段

初始谜题1

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

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

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

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 = x \cdot A\\ c2 = x \cdot b + e1 + m \cdot \frac{q}{2}$$

化简得:

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

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

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

// #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 = d2 \cdot k3 \bmod n\\ s3 = d2 \cdot (r+k2) \bmod n\\ \Downarrow\\ d2=\frac{s3-s2}{r} \bmod n$$

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 的循环

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 的逆元)

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 对应的式子进行求解

$$\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}$$

# 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 中得到的相关公式就可以得到伪造后的签名啦

# 求出 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