Just Follow the Recipe — GPN24 CTF (KITCTF)

Description

Cooking is easy they say. Just follow the recipe they say. If you follow the recipe nothing can go wrong. And still, I end up with chemical weapons instead of dinner and they complain. But it's not my fault that my kitchen is shit. But they dont want to hear that excuse.

The binary is there for a reason, LOOK at it.

We connect over TLS (ncat --ssl <host>.gpn24.ctf.kitctf.de 443). Each connection forks a fresh process with alarm(200) and regenerates a random matrix A and a random short secret. At connect the server prints flag_hash = A · secret mod Q. The menu lets us hash arbitrary vectors (an A·v oracle) and submit a guess for secret. Recovering the secret exactly yields the flag — but everything must happen on a single 200-second connection because each new connection regenerates A and secret.

Full source was provided: main.c, mat.c, mat.h, a Dockerfile, and a non-stripped x86-64 ELF challenge.

The Math — SIS / Ajtai-style hash

Constants: N=64, M=164, Q=12289 (prime, NTT-friendly = 2^12·3+1), beta=10.

• A is a random 64×164 matrix over Z_Q, generated per-instance with getrandom then reduced mod Q. It is never printed.
• secret_vec has length M=164, with every entry in {0..9} (generate_random_vector then vec32_mod(secret_vec, beta=10)).
• flag_hash = A · secret mod Q (length 64), printed at connect time, computed with mat_mul_naive (the naive, correct multiply).

Goal: recover secret exactly.

This is the Short Integer Solution (SIS) problem / Ajtai's hash. It is information-theoretically unique: 64 · log2(12289) ≈ 870 bits of equations exceed 164 · log2(10) ≈ 545 bits of secret entropy. The centered secret (secret − 4) has L2 norm ≈ 37.4 — a clean unique-SVP / BDD instance.

Menu / oracle

• 0 Check your work — submit a guess. On exact match: prints Impossible the recipe was a lie. + getenv("FLAG"). On mismatch: prints Wrong guess! Try again. and leaks the true secret, then exit(0) (useless across connections since A/secret are fresh each time).
• 1 Hash a single vector (hash_single, uses the optimized mat_mul).
• 2 Hash multiple vectors (multi_hash, up to 100; uses the optimized mat_mul via a transpose chain).
• 3 Exit.

Both hash options accept arbitrary uint32 vectors and return A·v mod Q, so they look like an oracle to recover the columns of A by querying unit vectors e_i.

The Bug — "compilers are your friend, they would never…"

The hint and the flag text both scream compiler. The Dockerfile compiles with:

gcc -O3 -flto -funroll-loops -mavx2 -fomit-frame-pointer ...

The optimized mat_mul in mat.c has a 4-wide unrolled inner loop:

for (blk = 0; blk < ((int)MM - 4); blk += 4) {
    for (i = 0; i < ...; i++)
        result[blk+0..3] += src[i] * BB[i*MM + blk + 0..3];
}
for (; blk < MM; blk++) { /* cleanup, scalar */ }

This source is mathematically correct. But gcc's AVX2 auto-vectorization miscompiles it: the vectorized code reads BB with the wrong stride — it uses NN (=164, mat->rows) instead of MM (=64) for the row-step. In the disassembly this is visible as

vinserti128 $1, (%r13,%r10,4), ...    ; %r10 = NN, should be MM

The effect: products from different matrix rows/columns get summed/mixed. For example hash_single(e_0) returns A[0][0] + A[1][0] in output row 0, zeros in rows ≡ {2,3 mod 4}, etc. The optimized mat_mul does not compute A·v correctly.

Characterizing the bug empirically (Docker amd64 replica)

The binary is x86-64 and won't run natively on an ARM Mac, so we used Docker --platform linux/amd64 to (a) run the exact provided binary, and (b) build a debug variant — patching main.c to dump A and secret to stderr, plus a variant with a deterministic A = row-index to expose the exact index-mixing. Diffing the optimized path against a debug naive build pinned down:

• flag_hash uses mat_mul_NAIVE → correct (A·secret).
• hash_single (option 1) uses the optimized mat_mul → always buggy/wrong.
• multi_hash (option 2) uses the optimized mat_mul through a transpose chain → correct only when n ≤ 4. For n ≥ 5 the blocked loop blk < n-4 activates and the bug corrupts columns ≡ {1,2 mod 4}. For n ∈ {1,2,3,4} only the scalar cleanup loop runs → correct.

This is why naive recovery (via hash_single, or via multi_hash with large batches like n=100) yields a wrong A. Solving A_wrong · s = flag_hash finds a different in-box solution (the server then prints Wrong guess!, and the diffs against the true secret are adjacent-index pair swaps), never the true secret.

Correct recovery: query A's columns via multi_hash with n=4 batches (41 calls for 164 columns), giving the true A consistent with the naive-computed flag_hash.

Solving the bounded SIS (recover the short secret)

Given the true A (64×164 over Z_Q) and t = flag_hash (length 64), find secret ∈ {0..9}^164 with A·secret ≡ t mod Q.

1. Particular solution s0: Gaussian elimination mod Q.
2. q-ary kernel lattice: basis of {x : A·x ≡ 0 mod Q} with det = Q^64, dimension 164.
3. Kannan embedding (dim 165): rows = kernel basis rows + a target row (s0 − mid | tw), with mid=4, tw=1. The embedded vector (secret − mid | tw) (norm ≈ 37.6) is the unique shortest; the kernel λ1 ≈ GH, so the gap ≈ 3.
4. Reduce with BKZ, read the short vector, reconstruct secret = head + mid, verify in-box and A·secret ≡ t.

Tooling lesson (fpylll vs fplll CLI)

The local fpylll was degraded: its bundled fplll strategies JSON was missing (hardcoded CI path), so its BKZ underperformed and plateaued on kernel vectors, never finding the planted short vector even at BKZ-44 (and crashed with infinite loop in babai for some scalings).

Fix: brew install fplll (which ships strategies/default.json) and call the fplll CLI directly:

fplll -a bkz -b <blocksize> -s <path>/strategies/default.json basis.txt

Progressive BKZ (reusing the reduced basis, blocksizes ~40→50→56→60) solves in ~40–90s. Pure LLL is insufficient (Hermite factor ~1.02^165 ≈ 26 > gap 3).

Full exploit flow (~61s on the live server, well within the 200s alarm)

1. Connect (TLS), read flag_hash = t.
2. Recover all 164 columns of A via multi_hash with n=4 batches (option 2, custom vectors = unit vectors e_i). ~44s over SSL.
3. Solve the SIS with the Kannan embedding + progressive fplll-CLI BKZ. ~17–90s.
4. Submit secret to option 0 → Impossible the recipe was a lie. + FLAG.

#!/usr/bin/env python3
# Just Follow the Recipe — GPN24 CTF
# Recover TRUE A via multi_hash n<=4 batches (avoids the AVX2 miscompile),
# then solve bounded SIS with Kannan embedding + fplll-CLI progressive BKZ.
import socket, ssl, subprocess, tempfile, os, re
from sage.all import matrix, vector, ZZ, identity_matrix

HOST = "<host>.gpn24.ctf.kitctf.de"
PORT = 443
N, M, Q, BETA = 64, 164, 12289, 10

def connect():
    raw = socket.create_connection((HOST, PORT))
    ctx = ssl.create_default_context()
    ctx.check_hostname = False
    ctx.verify_mode = ssl.CERT_NONE
    s = ctx.wrap_socket(raw, server_hostname=HOST)
    return s

def recvuntil(s, tok):
    buf = b""
    while tok not in buf:
        buf += s.recv(4096)
    return buf

def parse_vec(text):
    return [int(x) for x in re.findall(r"-?\d+", text)]

# ---- 1) read flag_hash ----
s = connect()
banner = recvuntil(s, b"flag_hash")
banner += recvuntil(s, b"\n")
t = parse_vec(banner.split(b"flag_hash", 1)[1].split(b"\n", 1)[0])[:N]
assert len(t) == N

# ---- 2) recover A column-by-column via multi_hash with n=4 (only cleanup loop -> correct) ----
# multi_hash(option 2): submit batches of up to 4 unit vectors e_i; each returns A*e_i = column i of A.
A_cols = [None] * M
def query_batch(unit_indices):
    # send option 2, count, then each vector (M entries, unit at idx)
    recvuntil(s, b"> ")
    s.sendall(b"2\n")
    recvuntil(s, b":")  # how many
    s.sendall(f"{len(unit_indices)}\n".encode())
    out = []
    for idx in unit_indices:
        recvuntil(s, b":")  # vector prompt
        v = [0] * M
        v[idx] = 1
        s.sendall((" ".join(map(str, v)) + "\n").encode())
    # read len(unit_indices) result rows of length N
    data = recvuntil(s, b"> ")
    nums = parse_vec(data)
    for k in range(len(unit_indices)):
        out.append(nums[k*N:(k+1)*N])
    return out

for base in range(0, M, 4):
    idxs = list(range(base, min(base + 4, M)))
    cols = query_batch(idxs)
    for j, idx in enumerate(idxs):
        A_cols[idx] = [c % Q for c in cols[j]]

A = matrix(ZZ, N, M, lambda r, c: A_cols[c][r])

# ---- 3) solve bounded SIS: A*secret = t mod Q, secret in {0..9} ----
# particular solution mod Q
Aq = A.change_ring(ZZ).augment(vector(ZZ, t)).change_ring(ZZ)
# work in GF(Q)
from sage.all import GF
F = GF(Q)
s0 = (A.change_ring(F).solve_right(vector(F, t))).change_ring(ZZ)

# q-ary kernel lattice basis (dim M, det Q^N)
K = A.change_ring(F).right_kernel_matrix().change_ring(ZZ)
# build full q-ary lattice {x : A x = 0 mod Q}
qary = K.stack(Q * identity_matrix(ZZ, M))
qary = qary.hermite_form(include_zero_rows=False)

MID, TW = 4, 1
target = vector(ZZ, [int(x) - MID for x in s0] + [TW])
emb_rows = []
for row in qary.rows():
    emb_rows.append(list(row) + [0])
emb_rows.append(list(target))
B = matrix(ZZ, emb_rows)

# write basis, run fplll CLI progressive BKZ
def fplll_bkz(mat, bs, strat):
    txt = "[" + "\n".join("[" + " ".join(map(str, r)) + "]" for r in mat.rows()) + "]\n"
    with tempfile.NamedTemporaryFile("w", suffix=".txt", delete=False) as f:
        f.write(txt); path = f.name
    out = subprocess.check_output(
        ["fplll", "-a", "bkz", "-b", str(bs), "-s", strat, path])
    os.unlink(path)
    rows = re.findall(r"\[([^\[\]]+)\]", out.decode())
    return matrix(ZZ, [[int(x) for x in r.split()] for r in rows])

STRAT = "/opt/homebrew/share/fplll/strategies/default.json"  # from brew install fplll
red = B
for bs in (40, 50, 56, 60):
    red = fplll_bkz(red, bs, STRAT)
    for row in red.rows():
        if abs(row[-1]) == TW:
            head = [(-(x)) if row[-1] == -TW else x for x in row[:M]]
            cand = [h + MID for h in head]
            if all(0 <= c < BETA for c in cand) and A * vector(ZZ, cand) % Q == vector(ZZ, t):
                secret = cand
                break
    else:
        continue
    break

# ---- 4) submit ----
recvuntil(s, b"> ")
s.sendall(b"0\n")
recvuntil(s, b":")
s.sendall((" ".join(map(str, secret)) + "\n").encode())
print(s.recv(8192).decode())

Lessons

• Aggressive compiler flags can silently miscompile hand-unrolled SIMD-friendly loops. -O3 -mavx2 -funroll-loops -flto made gcc auto-vectorize with the wrong stride (NN instead of MM). The "naive" reference and the "optimized" path diverge — exactly what the flag jokes about: compilers are your friend, they would never [betray you].
• When two code paths should compute the same linear map but don't, treat each as a black box and characterize it empirically. Unit-vector probing + a Docker linux/amd64 replica + a debug build that dumps ground truth let us pin down that hash_single is always buggy and multi_hash is correct only for n ≤ 4.
• Recover-via-oracle only works if the oracle is consistent with the target computation. flag_hash uses the naive multiply, so the recovered A must match the naive path (achieved via the n ≤ 4 cleanup-only multi_hash), not the buggy optimized one.
• For SIS / uSVP with a short bounded secret: Kannan embedding + BKZ. Mind your lattice tooling — a missing fplll strategies file silently cripples fpylll's BKZ (plateaus, or infinite loop in babai). Use the fplll CLI (or sage / g6k / flatter) with proper strategies and run progressive BKZ.