2024 ZJUCTF WriteUp

 2024-10-24   编程 CTF WriteUp 密码学

2024 ZJUCTF中部分Crypto题目的WriteUp

NSA

构造格

[
    [a[0], 1, 0, 0, 0, 0, 0, 0],
    [a[1], 0, 1, 0, 0, 0, 0, 0],
    [a[2], 0, 0, 1, 0, 0, 0, 0],
    [a[3], 0, 0, 0, 1, 0, 0, 0],
    [a[4], 0, 0, 0, 0, 1, 0, 0],
    [n   , 0, 0, 0, 0, 0, 1, 0],
    [s   , 0, 0, 0, 0, 0, 0, 1]
]

然后LLL得到最短向量

[
    0,
    -230729024844790789556619349600625783344,
    -243907382476137153303325964810673122335944690051,
    -2554279992083296465297024646335705965399770138928743004423,
    -8832885361121131509188923181425003699018344265962112193076074221011,
    -67887266175228062577011710663590854833018502169008849245557931810519788233735,
    1032580361425101070701831457336840876385698805304023083307306198588869332331689,
    1
]

于是得到x的值进而得到flag。 ZJUCTF{64a7b4afeef01bb8ebde50e85e4140cad60483238ac043fcb39a95a456e634c7}

Seed?

使用 mt19937-reversible 的代码，用 MT19937.clone_state_from_output_and_rewind 从624个随机数中得到初始时刻rng的状态。然而，通过阅读cpython源码得知，python的rng实现与这里的MT19937有着略微的不同，要得到刚seed完后的状态还需要额外624次rewind。然后就是再次阅读cpython源码中的seed算法然后反过来即可得到flag。

def rev(to_rev, length):
    to_rev = list(to_rev)
    init = [0] * 624
    init[0] = 19650218 & 0xffffffff
    for i in range(1, 624):
        init[i] = (1812433253 * (init[i - 1] ^ (init[i - 1] >> 30)) + 
            i) & 0xffffffff
    for i in range(623, 2, -1):
        to_rev[i] = ((to_rev[i] + i) ^ ((to_rev[i - 1] ^ 
            (to_rev[i - 1] >> 30)) * 1566083941)) & 0xffffffff
    opt = [0] * length
    for i in range(623, 623 - length, -1):
        opt[(i - 1) % length] = (to_rev[i] - (init[i] ^ 
            ((to_rev[i - 1] ^ (to_rev[i - 1] >> 30)) * 
            1664525)) - ((i - 1) % length)) & 0xffffffff
    return opt
def rev_str_seed(output_for_cloning, length):
    length32 = ((length + 3) // 4) + 16
    mt = MT19937()
    mt.clone_state_from_output_and_rewind(output_for_cloning)
    mt.rewind(rounds=624)
    result = rev(mt.__getstate__()["_state"], length32)
    s = ""
    for i in range(length32 - 1, 15, -1):
        s += (chr((result[i] >> 24) & 0xff) + 
            chr((result[i] >> 16) & 0xff) + 
            chr((result[i] >> 8) & 0xff) + 
            chr(result[i]& 0xff))
    return s
o = []
with open("./leak", "r") as f:
    for i in range(624):
        o.append(int(f.readline(), 16))
print(rev_str_seed(o, 80))

ZJUCTF{hahahaha,D0nt_y0u_think_tH15_is_REV_?I_think_this_can_be_loooooooooonger}

Line

what函数看上去像是一个写错了的 GF(256)GF(256) 乘法

__int64 what(char a1, unsigned __int8 a2)
{
  unsigned __int8 i;
  unsigned __int8 v6;

  v6 = 0;
  for ( i = 0; i <= 7u; ++i )
  {
    if ( (a2 & 1) != 0 )
      v6 ^= a1;
    a1 *= 2;
    if ( a1 < 0 )
      a1 ^= 0x1Bu;
    a2 >>= 1;
  }
  return v6;
}

通过实验发现，what(a, c) ^ what(b, c) == what(a ^ b, c)对任意a,b，以及c=1,2,3均成立。beta函数里的运算只有what和异或，magic_spell_2里的运算只有beta，alpha里的运算只有置换，magic_spell_1里的运算只有alpha，add里的运算只有异或，magic里的运算只有add，magic_spell_1，magic_spell_2。于是得出结论：magic(buf1, key1) ^ magic(buf2, key2) == magic(buf1 ^ buf2, key1 ^ key2)，其中异或是对应字节异或。

进一步得知buf形如ZJUCTF{xxxxxxxx}，将buf的8个未知字节拆成64个bit，将key拆成64个bit，拼在一起得到128个bit，可以看作 GF(2)GF(2) 中的128维向量 v⃗0\vec v_0，将 magic(buf, key)的结果的16个字节拆成128个bit，可以看作 GF(2)GF(2) 中的128维向量 v⃗1\vec v_1。而在 GF(2)GF(2) 中异或等价于加法，于是得出结论，存在 GF(2)GF(2) 中的矩阵 AA 与向量 b⃗\vec b 使得 v⃗1=Av⃗0+b⃗\vec v_1=A\vec v_0+\vec b。让 v⃗0\vec v_0 取全为0，以及只有一位为1，通过magic函数计算相应的 v⃗1\vec v_1，可以算出矩阵 AA 与向量 b⃗\vec b。下面就是通过题目中的 v⃗1\vec v_1 解出 v⃗0\vec v_0 即可，然而 AA 不是可逆的，可能解出很多个 v⃗0\vec v_0，但是用sagemath随便解了个特解交上去试试竟然对了（）于是得到flag。 ZJUCTF{M47rlx!?}

Pseudo

记

k1=(ak0+b)mod⁡c,r0=⌊k0/d⌋,r1=⌊k1/d⌋k_1=(a k_0+b)\operatorname{mod} c,\\r_0=\lfloor k_0/d\rfloor,r_1=\lfloor k_1/d\rfloor

则向量 v⃗=(k0,k1−b)\vec v=(k_0,k_1-b) 在格

L=[1a0c]L= \begin{bmatrix} 1 & a \\ 0 & c \end{bmatrix}

中。而 v⃗′=((r0+12)d,(r1+12)d−b)\vec v^\prime=((r_0+\frac12)d, (r_1+\frac12)d-b) 距离 v⃗\vec v 比较近，事实上有 ∣v⃗−v⃗′∣≈det⁡L\lvert \vec v - \vec v^\prime\rvert \approx \sqrt{\det L}，于是先对 LL 做规约然后枚举在 v⃗′\vec v^\prime 附近的向量比对sha256就能得到正确的 v⃗\vec v 便能预测随机数进而得到flag。 ZJUCTF{Cr4cK_7rUnC4t3d_1c9_w1tH_4_l17tl3_b1t_0f_m4Th}

insane pad

注意到unpad函数是直接移除最后一位对应长度，以及verify里使用了zip，而zip返回的长度是参数的长度的最小值，也就是说可以通过某种方式控制参与验证的字节长度。

AES CBC每块是16个字节。假设AES ECB的解密为 dec(a)，那么AES CBC的解密为 dec(a) 异或前一块的密文，如果 a 是第一块那么异或的就是 iv。flag的密文是80个字节，为5个块，记为 a[0] 至 a[4]。记flag pad后的5个块为 f[0] 至 f[4]。要得到flag pad前的长度，就是要猜 f[4] 的最后一个字节的值。设这个字节为 x，假设 x < 16，那么对任意的 64 <= y <= 79，x ^ y <= 79，所以可以枚举倒数 f[3] 的最后一个字节与 iv 的第一个字节，如果解密成功则说明此时极有可能 x ^ y == 79。枚举后得出 x == 4，于是得到 f[4] 的最后5个字节为 }\x04\x04\x04\x04。

在这之后，通过控制倒数第二块密文的最后一个字节，可以控制参与比对的长度。依次控制长度从1到16并枚举iv的第1到16个字节，可以得到满足 dec(a) ^ iv == f[0] 的 iv，也就是说可以求出 dec(a) ^ f[0]。从 dec(a[4]) ^ a[3] == f[4] 最后五个字节已知可以得到 dec(a[4]) 的最后五个字节，再求出 dec(a[4]) ^ f[0]，于是 f[0] 的后五个字节已知。又有 f[i] ^ f[0] == dec(a[i]) ^ a[i - 1] ^ f[0]，于是可以求出所有的 f[i] ^ f[0]。此时枚举 f[0] 中间未知的4个字节，计算得到的原文的sha256，即可得到正确的原文。这题手动交互次数更加不可接受，写了个程序交互了一万次得到flag。

import socket
def netcat_client(host, port):
    with socket.socket(socket.AF_INET, socket.SOCK_STREAM) as sock:
        sock.connect((host, port))
        while True:
            response = sock.recv(1024)
            msg = yield response.decode()
            sock.sendall(msg.encode())
gen = netcat_client("127.0.0.1", 12345)
next(gen)
a = gen.send("G\n").split(">")[0].strip()
hash1 = gen.send("H\n").split(">")[0].strip()
def dec(msg, iv):
    gen.send("V\n")
    gen.send(msg + "\n")
    res = gen.send(iv + "\n")
    return "Invaild" not in res
a = list(bytes.fromhex(a))
cip_0 = a[: 16]
cip_1 = a[16: 32]
cip_2 = a[32: -32]
cip_3 = a[-32: -16]
cip_4 = a[-16: ]
def lstxor(u, v):
    return [x ^ y for x, y in zip(u, v)]
# solves dec(cip) ^ f[0] 
def solve1(cip):
    test_iv = [0] * 16
    for i in range(16):
        pad = 48 - (i + 1)
        test_mid = [pad ^ 0x04 ^ cip_3[-1]] * 16
        for j in range(256):
            test_iv[i] = j
            if dec(bytes(cip + test_mid + cip_4).hex(), bytes(test_iv).hex()):
                break
    return test_iv
iv = solve1(cip_0)
flag_0_head = list(b"ZJUCTF{")
flag_4_tail = list(b"}\x04\x04\x04\x04")
flag_0_tail = lstxor(lstxor(solve1(cip_4)[-5:], cip_3[-5:]), flag_4_tail)
flag_0_temp = flag_0_head + ([0] * 4) + flag_0_tail
flag_1_temp = lstxor(lstxor(solve1(cip_1), cip_0), flag_0_temp)
flag_2_temp = lstxor(lstxor(solve1(cip_2), cip_1), flag_0_temp)
flag_3_temp = lstxor(lstxor(solve1(cip_3), cip_2), flag_0_temp)
flag_4_temp = lstxor(lstxor(solve1(cip_4), cip_3), flag_0_temp)
LEGAL=b"0123456789abcdef"
from hashlib import sha256
for i in range(0xffff):
    enum = [LEGAL[i >> 12], LEGAL[(i >> 8) & 0xf], LEGAL[(i >> 4) & 0xf], LEGAL[i & 0xf]]
    temp_flag = flag_0_temp + flag_1_temp + flag_2_temp + flag_3_temp + flag_4_temp
    temp_flag = lstxor(temp_flag, (([0] * 7) + enum + ([0] * 5)) * 5)
    temp_flag = bytes(temp_flag[:-4])
    if sha256(temp_flag).hexdigest() == hash1:
        print(temp_flag)
        break

ZJUCTF{8e2adfdad177098ec814184e96c0b231b7736293773ce07f9daa380b0f66f922f2ca}