NCTF 2025 Crypto Writeup

2025-03-23

字数统计: 2.4k字 | 阅读时长≈ 14分

NCTF 2024 三道 crypto 赛题的题解。

周六白天看完三道题，剩下 AES DFA 的三连题不太熟就没看了。

绮云

题目附件：qiyun.zip

题解

提供一个 RSA 的 Encryption Oracle

class RSA:
    def __init__(self,d:int):
        p = getStrongPrime(1024)
        q = getStrongPrime(1024)
        
        assert GCD(d,(p-1)*(q-1)) == 1

        self.N = p * q
        self.d = d
        self.e = pow(d,-1,(p-1)*(q-1))
        open('pubkey','w').write(f'{self.N}\n{self.e}')

    def encrypt(self,m:int,idx:int):
        return pow(m,self.e ^ (1 << idx),self.N)

即

$\mathcal{O}(m, i) = m^{e \oplus 2^i } \mod N$

并且 rsa = RSA(d ** 4) ，d 是一个 232 比特的素数。我们需要恢复私钥 d ，然后伪造 ECDSA 签名。攻击思路如下：

恢复模数 N : 利用 RSA 的乘法同态，固定输入 $i$ ，则密文 $c_1 =\mathcal{O}(m, i), c_2 = \mathcal{O}(m^2, i)$ 满足关系 $c_2 - c_1 = 0 \pmod {N}$ ，然后恢复足够多 N 的倍数求 GCD 即可恢复 N。
恢复公钥 e : 固定输入 $m$ ，取 $i = 2049$ ，已知 $e < 2^{2048}$ ，恢复得到准确的 $m^e$ , 之后逐比特恢复 $e$ 。
恢复私钥 d： $d$ 虽然很小 $< 2^{232}$ ，但是 $d^4 < 2^{928}$ 不满足 Wiener/Boneh 的上界。注意到
$e d^4 = \underbrace{k(1-p-q) + 1}_{< 2^{928 + 1025} \ll 2^{2048}} \pmod N$
这本质就是一个 HNP 方程，我们可以多次复用上述 RSA Encryption Oracle，得到多组 $(N_i, e_i)$ , 构造格求解 SVP 恢复私钥 $d^4$ , 本地测试发现 11 组数据可以稳定恢复私钥。

EXP

from pwn import remote, process, info
from Crypto.Util.number import long_to_bytes, bytes_to_long
from math import gcd
from tqdm import trange, tqdm
from sage.all import matrix, ZZ, Zmod
from task import ECDSA
import os

local = False
if local:
    io = process(['python3', 'task.py'])
else:
    # tcp 39.106.16.204:16943
    io = remote('39.106.16.204', 16943)

def enc_oracle(io: remote, m: int, idx: int) -> int:
    io.sendlineafter(b"Enter 'e' for encryption or other to exit:", b"e")
    io.sendlineafter(b"message:", long_to_bytes(m).hex().encode())
    io.sendlineafter(b"interfere?", str(idx).encode())
    io.recvuntil(b"Result:")
    return int(io.recvline().strip(), 16)

def batch_enc_oracle(io: remote, ms: int, idxs: int, timeout=3) -> int:
    all_requests = b""
    for m, idx in zip(ms, idxs):
        all_requests += b"e\n" + long_to_bytes(m).hex().encode() + b"\n" + str(idx).encode() + b"\n"
    io.send(all_requests)
    lines = io.recvlines(len(ms))
    results = []
    for line in lines:
        line = line.decode()
        if "Result:" in line:
            results.append(int(line.split("Result:")[-1].strip(), 16))
    return results

def recover_rsa_pk(io: remote) -> int:
    io.sendlineafter(b"Your option:", b"1")
    # recover n
    kn = 0
    m = 2
    while True:
        fault_result1 = enc_oracle(io, m, 1)
        fault_result2 = enc_oracle(io, m**2, 1)
        kn = gcd(kn, fault_result2 - fault_result1**2)
        if int(kn).bit_length() <= 2048:
            N = kn
            break
        m += 1
    print(f"{N = }")
    # recover e
    m = 2
    e = 0
    inv =  pow(m, -1 << 2049, N)
    fault_result2 = enc_oracle(io, m, 2049) * inv % N
    # results = batch_enc_oracle(io, [m for _ in range(2048)], [i for i in range(2048)])
    for i in trange(2048):
        fault_result1 = enc_oracle(io, m, i)
        # fault_result1 = results[i]
        if pow(m, 1<<i, N) * fault_result1 % N == fault_result2:
            e |= 1 << i
    # exit oracle
    print(f"{e = } {e.bit_length() = }")
    # io.sendlineafter(b"Enter 'e' for encryption or other to exit:", b"q")
    io.sendline(b"q")
    return N, e

def verify_oracle(io: remote, r: int, s: int) -> bool:
    io.sendlineafter(b"Your option:", b"2")
    io.sendlineafter(b"signature:", f"{r} {s}".encode())
    return io.recvline().decode().strip()

n_samples = 11
Ns = []
es = []
dbit = 232
for i in range(n_samples):
    N, e = recover_rsa_pk(io)
    Ns.append(N)
    es.append(e)
    
mat = matrix(ZZ, n_samples + 1, n_samples + 1)
T = 2**(4 * dbit + 1025)
D = 2 ** (4 * dbit)
for i in range(n_samples):
    mat[i, i] = Ns[i]
    mat[n_samples, i] = es[i]
    
mat[n_samples, n_samples] = 2 ** (1024)

L = mat.LLL()
for row in L:
    rowbits = [ZZ(num).nbits() for num in row]
    if all(num < T for num in row):
        rd4 = abs(row[-1] // 2**1024)
        d = ZZ(rd4).nth_root(4)
        print(f"Found {d = }")
        break

ecdsa = ECDSA()
ecdsa.d = d
ecdsa.Q = ecdsa.mul(ecdsa.d, ecdsa.G)
my_msg = f'nctf2024-{os.urandom(1).hex()}'.encode()
r, s = ecdsa.sign(my_msg)
while True:
    response = verify_oracle(io, r, s)
    if "Congratulations" in response:
        print(response)
        break

Arcahv

题目附件：arcahv.zip

题解

套娃题，LCG + RSA Byte Oracle，攻击思路如下：

LCG Oracle ：给出了连续 5 个 LCG 的输出，我们可以通过多次访问这个 Oracle ，拼凑重合的 LCG 输出，得到连续 $n > 5$ 个 LCG 的输出。但是 5 个连续的输出已经足够恢复出 LCG 的所有状态，回溯若干轮直到 state 小于 $2^{128}$ ，即可恢复 key。
RSA Byte Oracle： crystal_trick 函数并不会混淆首字节，因此返回明文的首字节是准确的，加上是小端序，因此该 Oracle 每次泄露了低 8 位。我们需要解密 $c = p_1 ^ e \mod N_2$ 的密文， $p_1$ 只有 1024 比特，75 次 Oracle 最多泄露 600 比特，因此未知比特数只有 424 比特，利用 Coppersmith 即可分解 $N_1 = p_1 q_1$ 。

EXP

from pwn import remote, process
from functools import reduce
from math import gcd
from Crypto.Util.number import getPrime, isPrime
from Crypto.Cipher import AES
import decimal
from sage.all import PolynomialRing, Zmod, ZZ

def getting_map(N, leak_range):
    map = [None]*leak_range
    for i in range(leak_range):
        k = -i*N % leak_range
        map[k] = i
    return map


def rsa_lsb_oracle_solver(c: int, e: int, n: int, leak_length: int, times: int, oracle_func: callable):
    decimal.getcontext().prec = n.bit_length()
    lb = decimal.Decimal(0)
    ub = decimal.Decimal(n)
    leak_range = 2**leak_length
    map = getting_map(n, leak_range)
    oracle_times = 0
    # skip half of the oracles since p is 1024-bit
    for i in range(127):
        c = (c * pow(leak_range, e, n)) % n
        k = 0
        interval = (ub-lb) / leak_range
        lb = lb + interval * k
        ub = lb + interval
    cnt = 0
    while lb <= ub - 2:
        c = (c * pow(leak_range, e, n)) % n
        msg = oracle_func(c)
        k = map[msg]
        oracle_times += 1
        interval = (ub-lb) / leak_range
        lb = lb + interval * k
        ub = lb + interval
        cnt += 1
        if cnt == times:
            break
    gap = int(ub - lb)
    if gap <= 2**20:
        for m in range(int(lb), int(ub) + 1):
            if pow(m, e, n) == c:
                return [m, m]
    return [int(lb), int(ub)]

class LCG:
    def __init__(self,seed:int) -> None:
        self.p = getPrime(1024)
        self.a = getPrime(1023)
        self.b = getPrime(1023)
        self.status = seed

    def next(self) -> int:
        ret = self.status
        self.status = (self.status * self.a + self.b) % self.p
        return ret
    
def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, x, y = egcd(b % a, a)
        return g, y - (b // a) * x, x

def modinv(b, n):
    g, x, _ = egcd(b, n)
    if g == 1:
        return x % n

def crack_unknown_increment(states, modulus, multiplier):
    increment = (states[1] - states[0] * multiplier) % modulus
    return increment


def crack_unknown_multiplier(states, modulus):
    multiplier = (states[2] - states[1]) * modinv(states[1] - states[0], modulus) % modulus
    return multiplier

def crack_unknown_modulus(states):
    diffs = [s1 - s0 for s0, s1 in zip(states, states[1:])]
    zeroes = [t2 * t0 - t1 * t1 for t0, t1, t2 in zip(diffs, diffs[1:], diffs[2:])]
    modulus = abs(reduce(gcd, zeroes))
    return modulus


local = False
if local:
    io = process(["python3", "arcahv.py"])
else:
    io = remote("39.106.16.204", 14900)
    

def get_flaghints(io: remote):
    io.sendlineafter(b"Option > ", b"1")
    io.recvuntil(b"Encrypted flag: ")
    encflag = bytes.fromhex(io.recvline().strip().decode())
    io.recvuntil(b"Hint1: ")
    hint1 = bytes.fromhex(io.recvline().strip().decode())
    io.recvuntil(b"Hint2: ")
    hint2 = bytes.fromhex(io.recvline().strip().decode())
    return encflag, hint1, hint2

def lcg_oracle(io: remote):
    io.sendlineafter(b"Your Option > ", b"3")
    outs = ""
    for i in range(16 * 5):
        io.sendlineafter(b"(y/[n])?", b"y")
        num = int(io.recvline().strip().decode())
        outs += hex(num)[2:].zfill(16)
    io.sendlineafter(b"(y/[n])?", b"n")
    return outs

def enter_rsa_oracle(io: remote):
    io.sendlineafter(b"Your Option > ", b"2")
    io.recvuntil(b"Your pubkey:(")
    N_hex, e_hex = io.recvline().strip().decode().strip("()").split(",")
    N = int(N_hex, 16)
    e = int(e_hex, 16)
    return N, e

def rsa_oracle(io: remote, c: int):
    io.sendlineafter(b'Do you still want to try decryption(y/[n])?', b"y")
    io.sendlineafter(b'Your ciphertext(in hex):', int(c).to_bytes(256, "big").hex().encode())
    io.recvuntil(b"Result: ")
    m = bytes.fromhex(io.recvline().strip().decode())
    return m[0]

encflag, hint1, hint2 = get_flaghints(io)

for i in range(10):
    outhex = lcg_oracle(io)
    if outhex[0] != "0":
        break

outs = [int(outhex[i:i+256], 16) for i in range(0, len(outhex), 256)]    
kp = crack_unknown_modulus(outs)
for i in range(2, 2**10):
    if kp % i == 0:
        kp //= i
    if kp.bit_length() <= 1024:
        p = kp
        break
print(f"{p = } {p.bit_length()}")
assert isPrime(p), "Modulus is not prime"
a = crack_unknown_multiplier(outs, p)
b = crack_unknown_increment(outs, p, a)
assert isPrime(a) and isPrime(b)
assert a.bit_length() <= 1023 and b.bit_length() <= 1023
state = outs[0]
a_inv = modinv(a, p)
# back trace
while state >= 2**128:
    state = (state - b) * a_inv % p

key = state.to_bytes(16, "big")
N1 = int.from_bytes(AES.new(key,AES.MODE_ECB).decrypt(hint2), "big")
N2, e2 = enter_rsa_oracle(io)
lsb_oracle = lambda c: rsa_oracle(io, c) & 0xff
cp = int.from_bytes(hint1, "little")
lb, ub = rsa_lsb_oracle_solver(cp, e2, N2, 8, 75, lsb_oracle)
unknown_bits = int(ub - lb).bit_length()
print(f"{unknown_bits = } of p")
polyring = PolynomialRing(Zmod(N1), 'x')
print(f"{N1 = }")
print(f"{lb = }")
x = polyring.gen()
poly = lb + x
x_root = poly.small_roots(X=2**unknown_bits, beta=0.498)
print(f"{x_root = }")
p = int(x_root[0]) + lb
assert isPrime(p) 
assert N1 % p == 0
q = N1 // p
encflag = int.from_bytes(encflag, "big")
flag = pow(encflag, modinv(65537, (p-1)*(q-1)), N1)
flag_bytes = int(flag).to_bytes(256, "big").strip(b"\x00")
print(flag_bytes)

Sign

题目附件：sign.zip

题解

套娃题：AGCD + MT19937 ，AGCD 思路如下，加密部分

$c = p \cdot (r_{1} x) + (r_2 y) \cdot 2^{8} + m$

其中 $r_1 < 2^{177}, r_2 < 2^{17}, x, y \le 2^{4}, m< 2^{8}$ , 恢复私钥 $p$ 后解密 $m = c\pmod p \pmod {2^{8}}$ ，上式即 AGCD 问题的等式，详情参考博客正交格攻击。

EXP

untwister 源码参考 mersenne_twister.py。

from pwn import remote
from Crypto.Util.number import getRandomNBitInteger, getPrime
from sage.all import matrix, ZZ, gcd
from util import FHE
from Crypto.Util.number import long_to_bytes
from random import Random
from untwister import MT19937
from Crypto.Cipher import AES
from hashlib import md5

def ol_attack(x, rho):
    assert len(x) >= 2, "At least two x values are required."
    R = 2 ** rho
    alpha = 2**(ZZ(max(x)).nbits())
    B = matrix(ZZ, len(x), len(x) + 1)
    for i, xi in enumerate(x):
        B[i, 0] = xi * alpha
        B[i, i + 1] = 1
    B = B.LLL()
    assert B[:-1,0] == 0, "not orthogonal"
    
    K =  B[:-2, 1:].right_kernel().basis_matrix()
    L = K.LLL()
    for row in L:
        if all( -R < num < R for num in row):
            r = [abs(num) for num in row]
            p = ZZ(gcd([xi - ri for ri, xi in zip(r,x)]))
            return p, r
    return None, None

def decrypt(p, ciphertext:list[int]):
    result = []
    for c in ciphertext:
        m = (c % p) & 0xff
        result.append(m)
    return result


# tcp 39.106.16.204:19496
io = remote("39.106.16.204", 19496)
io.recvuntil(b"Your ciphertext: ")
encflag = bytes.fromhex(io.recvline().strip().decode())
io.recvuntil(b"The keys to retrieve the global internet connection are as follows:")
Keys = []
io.sendline(b"")
all_data = io.recvall(timeout=2)
lines = all_data.split(b"\n")
for line in lines:
    if not line:
        continue
    Keys.append(int(line.decode().strip('[+] ').strip()))

secret_string = b""
for i in range(0, 30000, 2500): 
    subkeys = Keys[i:i+2500]   
    xs = subkeys[:128]
    mp, mrs = ol_attack(xs, 36)
    ms = decrypt(mp, subkeys)
    mtouts = bytes(ms[:-4])
    m32_outs = []
    for i in range(0, len(mtouts), 4):
        m32_outs.append(int.from_bytes(mtouts[i:i+4], "big"))
    mt = MT19937()
    mt.clone_state_from_output(m32_outs[:624][::-1])
    first_32 = mt.get_next_random()
    real_s = long_to_bytes(first_32, 4) + mtouts
    mchar = 0
    for i in range(4):
        bit2 = pow(real_s[i], -1, 0x101) * ms[-4 + i] % 0x101 
        assert bit2 <= 3
        mchar |= bit2 << (2*i)
    secret_string += bytes([mchar])
    print(f"{secret_string = }")

flag = AES.new(md5(secret_string).digest(),AES.MODE_ECB).decrypt(encflag)
print(f"[+] Flag: {flag}")