Challenge Description#

Falcon/NTRU-based challenge with beware.zip. 436 out of 512 coefficients of secret polynomial f were leaked as hints. Flag is encrypted with a SHA-256 stream key: $key = \text{SHA256}(f.\text{tobytes()})$, then XORed with challenge_flag.enc bytes.

From data inspection:

• q = 12289
• n = 512
• A is 512 x 512, b is all-zero
• hints count = 436 unique indices
• unknown secret coefficients = 512 - 436 = 76

Analysis#

The public equation: $b = (f \cdot A + g_{neg}) \bmod q = 0$

This is an LWE-like bounded-noise equation:

• f_known: vector with known hinted coefficients
• x: 76-dimensional vector for unknown coefficients
• M = A[missing,:]^T (shape 512 x 76)
• c = f_known @ A

Equation becomes: $c + Mx \equiv g \pmod q$, where $g$ is small (Falcon noise). This is ideal for a primal lattice CVP attack.

Solution#

Build a primal lattice basis for sampled equations: $L = \{(qz + A_s x, \alpha x)\}$. Reduce basis with LLL then BKZ. Use Babai nearest plane (CVP.babai) with target -c_s. Recover candidate x from the scaled block. Refine with alternating rounded least-squares and coordinate descent.

File used: solve_primal_target.py

#!/usr/bin/env python3
import hashlib
import json
from pathlib import Path

import numpy as np
from fpylll import BKZ, CVP, IntegerMatrix, LLL


def centered(v, q):
    return ((v + q // 2) % q) - q // 2


def decrypt_flag(f_vec, enc_hex):
    key = hashlib.sha256(np.array(f_vec, dtype=np.int64).tobytes()).digest()
    ct = bytes.fromhex(enc_hex)
    return bytes(c ^ key[i % len(key)] for i, c in enumerate(ct))


def build_basis(A_samp, q, alpha):
    # L = {(qz + A x, alpha x)}
    m, n = A_samp.shape
    d = m + n
    rows = []
    for i in range(m):
        r = [0] * d
        r[i] = int(q)
        rows.append(r)
    for j in range(n):
        r = [0] * d
        col = A_samp[:, j]
        for i in range(m):
            r[i] = int(col[i])
        r[m + j] = int(alpha)
        rows.append(r)
    return IntegerMatrix.from_matrix(rows)


def score_x(x, M_all, c_all, q):
    e = centered((c_all + M_all @ x).astype(np.int64), q)
    return int(np.dot(e, e)), int(np.max(np.abs(e))), float(np.std(e)), e


def refine_x(x, M_all, c_all, q, lim=24, rounds=8):
    x = np.clip(x.astype(np.int64), -lim, lim)

    # alternating rounding least squares on quotient vars
    pinv = np.linalg.pinv(M_all.astype(np.float64))
    for _ in range(rounds):
        y = (c_all + M_all @ x).astype(np.float64)
        k = np.rint(y / float(q))
        rhs = (q * k - c_all).astype(np.float64)
        xn = np.rint(pinv @ rhs).astype(np.int64)
        xn = np.clip(xn, -lim, lim)
        if np.array_equal(xn, x):
            break
        x = xn

    # coordinate polish
    sc, _, _, expr = score_x(x, M_all, c_all, q)
    rng = np.random.default_rng(2026)
    for _ in range(10):
        improved = False
        for i in rng.permutation(len(x)):
            old = int(x[i])
            col = M_all[:, i]
            bestv, bests = old, sc
            for nv in (old - 2, old - 1, old + 1, old + 2):
                if nv < -lim or nv > lim:
                    continue
                expr2 = expr + col * (nv - old)
                e2 = centered(expr2, q)
                sc2 = int(np.dot(e2, e2))
                if sc2 < bests:
                    bests = sc2
                    bestv = nv
            if bestv != old:
                expr = expr + col * (bestv - old)
                x[i] = bestv
                sc = bests
                improved = True
        if not improved:
            break
    return x


def main():
    base = Path(__file__).resolve().parent
    data = json.loads((base / "challenge_data.json").read_text())
    enc_hex = (base / "challenge_flag.enc").read_text().strip()

    q = int(data["q"])
    nfull = int(data["n"])
    A = np.array(data["A"], dtype=np.int64)

    f_known = np.zeros(nfull, dtype=np.int64)
    known_mask = np.zeros(nfull, dtype=bool)
    for i, v in data["hints"]:
        i = int(i)
        f_known[i] = int(v)
        known_mask[i] = True

    missing = np.where(~known_mask)[0]
    n = len(missing)
    M_all = A[missing, :].T.astype(np.int64)  # 512 x 76
    c_all = (f_known @ A).astype(np.int64)

    print(f"[+] q={q}, unknown={n}, equations={M_all.shape[0]}")

    rng = np.random.default_rng(1337)
    best_sc = 10**100
    best_x = None

    trial = 0
    for m in [96, 112, 128, 144]:
        for alpha in [1, 2, 3, 4, 5, 6]:
            for beta in [22, 26, 30]:
                for _ in range(12):
                    trial += 1
                    idx = np.sort(rng.choice(M_all.shape[0], size=m, replace=False))
                    As = M_all[idx, :]
                    cs = c_all[idx]

                    B = build_basis(As, q, alpha)
                    LLL.reduction(B, delta=0.997)
                    BKZ.reduction(B, BKZ.Param(block_size=beta, max_loops=2))

                    # target is -c (NOT reduced mod q)
                    target = [int(-v) for v in cs.tolist()] + [0] * n
                    v = np.array(CVP.babai(B, target), dtype=np.int64)

                    x0 = np.rint(v[m:] / float(alpha)).astype(np.int64)
                    x0 = np.clip(x0, -28, 28)

                    for x in (x0, -x0):
                        x = refine_x(x, M_all, c_all, q, lim=24, rounds=8)
                        sc, mx, sd, _ = score_x(x, M_all, c_all, q)

                        if sc < best_sc:
                            best_sc = sc
                            best_x = x.copy()
                            print(
                                f"[+] best t={trial} m={m} a={alpha} bkz={beta} score={sc} max={mx} std={sd:.2f} xr=[{x.min()},{x.max()}]"
                            )

                        f_rec = f_known.copy()
                        for i, pos in enumerate(missing):
                            f_rec[pos] = int(x[i])
                        pt = decrypt_flag(f_rec.tolist(), enc_hex)
                        if b"BITSCTF{" in pt:
                            print("\n[+] FLAG FOUND")
                            print(pt.decode(errors="ignore"))
                            return

                    if trial % 20 == 0:
                        print(f"[*] trial={trial} current_best={best_sc}")

    print(f"[-] no flag. best_score={best_sc}")
    if best_x is not None:
        f_rec = f_known.copy()
        for i, pos in enumerate(missing):
            f_rec[pos] = int(best_x[i])
        pt = decrypt_flag(f_rec.tolist(), enc_hex)
        print(f"[+] best preview: {pt[:120]!r}")


if __name__ == "__main__":
    main()

Install dependencies and run:

python3 -m pip install fpylll cysignals numpy
python3 solve_primal_target.py

Output:

[+] best t=33 m=96 a=1 bkz=30 score=8716 max=14 std=4.11 xr=[-7,9]

[+] FLAG FOUND
BITSCTF{h1nts_4r3_p0w3rfu1_4nd_f4lc0ns_4r3_f4st}