Nightfall Tempest Trials

---

• 对 Kyber1024 的 keygen 进行了补丁：使用了非标准的向量长度 $K = 12$（因此 PK_BYTES = 12 × 384 + 32 = 4640）。
• ref/ntt.c 会打印每一层 NTT（Number Theoretic Transform）阶段的所有数据，每个多项式泄露 $7 \times 256 = 1792$ 个值（见 attachment/ntt.patch）。
• task.py 仅保留前 $K$ 个泄露块（对应 secret polys），并在每个 stage 加入有界噪声 $\Delta = [240, 430, 600, 75, 70, 88, 99]$；随后对打包后的 NTT 域 secret 做哈希以派生 AES-CBC 密钥，并输出 pk、带噪声的 leaks、ct、iv。
• 目标：在噪声存在的情况下恢复精确的 NTT 域 secret bytes，并解密 attachment/output.txt 中的密文。

泄露模型（Leakage Model）

每个 NTT butterfly 运算为

$t = \zeta \cdot v,\qquad a = u + t,\qquad b = u - t,$

其中运算模数为 q = 3329。补丁后的代码会在每个 stage 泄露 a’, b’，并满足

$|a' - a|,\ |b' - b| \le \Delta_s$

其中 stage 对应的 $\Delta_s$ 就是上面的那组 $\Delta$。第一阶段输入的系数很小（$\eta_1 = 2 \Rightarrow u,v \in {-2,-1,0,1,2}$），这为逆向 NTT 提供了很强的约束。

分阶段重构（Stage-Wise Reconstruction）

• 允许的剩余类集合（Allowed residue sets）：

  对于每个 stage $s$ 的观测值 $o_{s,i}$，构造

  $S_{s,i} = {(o_{s,i} + d) \bmod q \mid d \in [-\Delta_s,\Delta_s]}.$

• 反向 butterfly（Reverse butterflies）：

  从最后一个 stage（len = 2）开始，按长度 $4, 8, 16, 32, 64$ 逐层回退。用

  $u = \tfrac{A+B}{2},\qquad v = \tfrac{(A-B),\zeta^{-1}}{2},$

  计算前一层可能的值，并只保留与 $S_{s-1}$ 相容的解（在 crypto/Nightfall Tempest Trials/solve/solve.py 的 reverse_stage 中实现）。

• 第一阶段的小系数约束（First stage constraint）：

  在 len = 128 时，额外与小系数集合 $\{0, \pm 1, \pm 2\}$ 求交（reverse_final_small）。

• 一致性检查（Consistency check）：

  对于仍存在歧义的索引，枚举小范围笛卡尔积，正向做 NTT（ntt_stages），并只保留在所有 stage 都满足噪声界限的向量。最终，每个多项式都会得到一个很小的候选集合（其打包后的 NTT 输出由 poly_tobytes 得到）。

恢复密钥（Recovering the Key）

1. 对每个多项式枚举一个候选 chunk（共 12 个），拼接得到

   SK_BYTES = 12 × 384。

2. 计算 $k = \mathrm{SHA256}(\texttt{sk\_bytes})$，并使用给定 IV 尝试 AES-CBC 解密。

3. 当填充合法且明文以 0ctf{} 开头时停止。

搜索空间足够小，直接做直积枚举即可很快成功。

PoC

#!/usr/bin/env python3
import re, ast, itertools, hashlib, math
from Crypto.Cipher import AES

# ------------------------
# Kyber constants
# ------------------------
Q = 3329
QINV = 62209
RINV = 169                 # (2^16)^(-1) mod Q
INV2 = pow(2, -1, Q)

K = 12                      # patched
DELTAS = [240, 430, 600, 75, 70, 88, 99]

# η1 = 2 => coefficients in [-2,2]
ALLOWED = {0, 1, 2, Q-1, Q-2}

# zetas from Kyber ref ntt.c
ZETAS_RAW = [
-1044,  -758,  -359, -1517,  1493,  1422,   287,   202,
 -171,   622,  1577,   182,   962, -1202, -1474,  1468,
  573, -1325,   264,   383,  -829,  1458, -1602,  -130,
 -681,  1017,   732,   608, -1542,   411,  -205, -1571,
 1223,   652,  -552,  1015, -1293,  1491,  -282, -1544,
  516,    -8,  -320,  -666, -1618, -1162,   126,  1469,
 -853,   -90,  -271,   830,   107, -1421,  -247,  -951,
 -398,   961, -1508,  -725,   448, -1065,   677, -1275,
-1103,   430,   555,   843, -1251,   871,  1550,   105,
  422,   587,   177,  -235,  -291,  -460,  1574,  1653,
 -246,   778,  1159,  -147,  -777,  1483,  -602,  1119,
-1590,   644,  -872,   349,   418,   329,  -156,   -75,
  817,  1097,   603,   610,  1322, -1285, -1465,   384,
-1215,  -136,  1218, -1335,  -874,   220, -1187, -1659,
-1185, -1530, -1278,   794, -1510,  -854,  -870,   478,
 -108,  -308,   996,   991,   958, -1460,  1522,  1628
]

# Convert zetas to normal-domain values (Montgomery factor removed)
ZETAS_EFF = [(z % Q) * RINV % Q for z in ZETAS_RAW]

# ------------------------
# Montgomery reduce (signed int16 behavior)
# ------------------------
def montgomery_reduce(a):
    u = (a * QINV) & 0xFFFF
    if u >= 0x8000:
        u -= 0x10000
    t = a - u * Q
    return t >> 16

def fqmul(a, b):
    return montgomery_reduce(a * b)

def to_signed(x):
    x %= Q
    return x if x <= Q//2 else x - Q

# ------------------------
# Forward NTT stages (signed like C int16)
# ------------------------
def ntt_stages(inp):
    r = [to_signed(x) for x in inp]
    stages = []
    k = 1
    length = 128
    while length >= 2:
        for start in range(0, 256, 2 * length):
            z = ZETAS_RAW[k]
            k += 1
            for j in range(start, start + length):
                t = fqmul(z, r[j + length])
                r[j + length] = r[j] - t
                r[j] = r[j] + t
        stages.append(r[:])
        length //= 2
    return stages

def stage_match(stages, obs):
    for s in range(7):
        delta = DELTAS[s]
        for i in range(256):
            if abs(stages[s][i] - obs[s][i]) > delta:
                return False
    return True

# ------------------------
# Reverse-stage helpers (residue constraints)
# ------------------------
def allowed_residue_sets(obs_stage, delta):
    return [set((x % Q) for x in range(o - delta, o + delta + 1)) for o in obs_stage]

# stage ordering
LENS = [128, 64, 32, 16, 8, 4, 2]
kstart = {}
k = 1
for L in LENS:
    kstart[L] = k
    k += 256 // (2 * L)

invz_by_L = {}
for L in LENS:
    ks = kstart[L]
    nb = 256 // (2 * L)
    invz_by_L[L] = [pow(ZETAS_EFF[ks + b], -1, Q) for b in range(nb)]

def reverse_stage(cand_out, allowed_prev, L):
    cand_in = [set() for _ in range(256)]
    nb = 256 // (2 * L)
    invzs = invz_by_L[L]
    for b in range(nb):
        invz = invzs[b]
        start = b * 2 * L
        for j in range(start, start + L):
            SA = cand_out[j]
            SB = cand_out[j + L]
            allowA = allowed_prev[j]
            allowB = allowed_prev[j + L]

            outA, outB = set(), set()
            for A in SA:
                for B in SB:
                    a = (A + B) * INV2 % Q
                    if a not in allowA:
                        continue
                    t = (A - B) * INV2 % Q
                    bb = t * invz % Q
                    if bb not in allowB:
                        continue
                    outA.add(a)
                    outB.add(bb)

            if not outA or not outB:
                return None

            cand_in[j] = outA
            cand_in[j + L] = outB

    return cand_in

def reverse_final_small(cand_out):
    cand_in = [set() for _ in range(256)]
    invz = invz_by_L[128][0]
    for j in range(128):
        SA = cand_out[j]
        SB = cand_out[j + 128]
        outA, outB = set(), set()
        for A in SA:
            for B in SB:
                a = (A + B) * INV2 % Q
                t = (A - B) * INV2 % Q
                bb = t * invz % Q
                if a in ALLOWED and bb in ALLOWED:
                    outA.add(a)
                    outB.add(bb)
        if not outA or not outB:
            return None
        cand_in[j] = outA
        cand_in[j + 128] = outB
    return cand_in

# ------------------------
# Packing poly_tobytes (Kyber format)
# ------------------------
def poly_tobytes(coeffs):
    out = bytearray(384)
    for i in range(0, 256, 2):
        t0 = coeffs[i] % Q
        t1 = coeffs[i + 1] % Q
        j = 3 * (i // 2)
        out[j] = t0 & 0xFF
        out[j + 1] = ((t0 >> 8) | ((t1 & 0x0F) << 4)) & 0xFF
        out[j + 2] = (t1 >> 4) & 0xFF
    return bytes(out)

def unpad_pkcs7(x):
    pad = x[-1]
    if pad < 1 or pad > 16:
        return None
    if x[-pad:] != bytes([pad]) * pad:
        return None
    return x[:-pad]

# ------------------------
# Main solve
# ------------------------
def main(fn):
    txt = open(fn, "r").read()

    pk_hex = re.search(r"pk = ([0-9a-f]+)", txt).group(1)
    ct_hex = re.search(r"ct = ([0-9a-f]+)", txt).group(1)
    iv_hex = re.search(r"iv = ([0-9a-f]+)", txt).group(1)

    leaks = ast.literal_eval(re.search(r"leaks = (\[\[.*\]\])\nct", txt, re.S).group(1))
    ct = bytes.fromhex(ct_hex)
    iv = bytes.fromhex(iv_hex)

    # enumerate candidate chunks for each poly
    poly_chunks = []
    for leak in leaks:
        obs = [leak[i*256:(i+1)*256] for i in range(7)]
        allowed_sets = [allowed_residue_sets(obs[s], DELTAS[s]) for s in range(7)]

        cand = [[(obs[6][i] + d) % Q for d in range(-DELTAS[6], DELTAS[6] + 1)] for i in range(256)]

        # reverse from stage 7 -> stage 1
        for (L, prev_stage) in [(2,5),(4,4),(8,3),(16,2),(32,1),(64,0)]:
            cand = reverse_stage(cand, allowed_sets[prev_stage], L)
            if cand is None:
                raise RuntimeError("reverse failed")

        # reverse final stage to small coeff input
        cand0 = reverse_final_small(cand)
        if cand0 is None:
            raise RuntimeError("final reverse failed")

        amb = [i for i,s in enumerate(cand0) if len(s) > 1]
        base = [next(iter(s)) if len(s)==1 else 0 for s in cand0]

        sols = []
        for values in itertools.product(*[sorted(cand0[i]) for i in amb]):
            arr = base[:]
            for idx,val in zip(amb, values):
                arr[idx] = val
            st = ntt_stages(arr)
            if stage_match(st, obs):
                ntt_out = [x % Q for x in st[-1]]
                sols.append(poly_tobytes(ntt_out))

        poly_chunks.append(sols)

    # brute across all polys
    sizes = [len(x) for x in poly_chunks]
    for idxs in itertools.product(*[range(s) for s in sizes]):
        sk = b''.join(poly_chunks[i][idxs[i]] for i in range(K))
        key = hashlib.sha256(sk).digest()
        pt = AES.new(key, AES.MODE_CBC, iv).decrypt(ct)
        msg = unpad_pkcs7(pt)
        if msg and msg.startswith(b"0ctf{"):
            print(msg.decode())
            return

    print("not found")

if __name__ == "__main__":
    import sys
    main(sys.argv[1] if len(sys.argv)>1 else "output.txt")

该方法会重构 secret 并输出：

0ctf{7n_the_Twilight_0f_br0k3n_ReAlm5_mY_deSt1ny_rise5_froM_7he_v0id.}

---