Sultan — ASIS CTF Quals 2026

Description

"An encrypted archive from the sultan's laboratory has resurfaced. It is said to contain a message meant for the court alone."

A web service (Flask/gunicorn) hands out an encrypted archive secret.enc per session (GET /download, session cookie sultan_session, up to 500 downloads per session, 20-minute session TTL). Together with the archive, the service publishes 70 transcripts that leak the high bits of an inner product involving the masking polynomial. The goal is to recover the per-session secret string hidden in the archive and POST it to /api/verify (JSON {"guess": ...}) to receive the flag. Flag format: ASIS{...}.

Analysis

Scheme (from the provided crypto_engine.py)

Parameters: q = 8380417 (the Dilithium prime), n = 64, ell = 1, m = 70 transcripts, t = 16 (sparsity of the challenge), b = 65000 (leak quantizer), committee size 63, threshold 32, secret_bound = 3.

Encryption (encrypt_sultan):

1. Secret polynomial s = 64 coefficients uniform in [-3, 3]; w = struct.pack("<64b", s).
2. Key k = shake_256(b"SULTAN/key" + w).digest(32).
3. Fresh nonce (24 bytes); ciphertext e = secret XOR shake_256(b"SULTAN/stream" + k + nonce); tag d = blake2s(b"SULTAN/tag" + nonce + e, key=k, digest_size=32).
4. For each of the m = 70 transcripts:
   • x = 32 random bytes; y = bytes of a sorted random 32-subset of 63 committee members; seed = x + y (fully public).
   • challenge c = _b(seed) — sparse ±1 polynomial (t = 16 nonzero positions), derived deterministically from shake_256(b"SULTAN/challenge" + seed) — public.
   • u — uniform polynomial in [0, q)^64 (secret mask).
   • v = u + c*s in Z_q[x]/(x^64 + 1) (negacyclic) — published as uint32[64].
   • audit polynomial r = _r(seed) — uniform, derived from shake_256(b"SULTAN/audit" + seed) — public.
   • THE LEAK: the transcript stores rho = (<r,u> mod q) // b — the high bits (above b = 65000 ≈ 2^16) of the inner product between the public r and the secret mask u.

File layout: 48-byte header struct "<4sIIIIIIIIIII" (magic d8 06 00 1a, version 4, q, n, ell, m, t, b, secret_bound, committee_size, threshold, secret_len), then nonce(24) + e(secret_len) + d(32) and 70 transcripts of 324 bytes each (x(32) y(32) rho(4) v(256)), all zlib-compressed.

The vulnerability

This is a textbook Hidden Number Problem / leaky-LWE instance in the secret polynomial s. Because r, c are deterministic functions of the public seed, and v = u + c·s is given, each transcript yields one modular equation in s with a small unknown error.

Key equation per transcript j:

<r_j, v_j> ≡ <r_j, u_j> + <r_j, c_j*s>   (mod q)
<r_j, u_j> mod q = rho_j * b + rem_j,   rem_j ∈ [0, b)
⇒  <r_j, c_j*s> + rem_j ≡ B_j := (<r_j, v_j> − rho_j * b) mod q

Here M_j(s) := <r_j, c_j*s> is linear in s: with negacyclic reduction,

m[j] = Σ_k ±c[k]·r[(k+j) mod 64]   (sign +1 if k+j < 64, −1 if k+j ≥ 64)

so each equation is Σ_i m[i]·s[i] + rem ≡ B (mod q) with 64 unknowns |s_i| ≤ 3 and error rem < 65000. With 70 equations (one file) for 64 unknowns, the system is over-determined enough for a Kannan-embedding lattice attack.

Solution

1. Parse the archive

Decompress, validate the header, and split out nonce, e, d and the 70 (seed, rho, v) triples.

2. Build the leak equations

For each transcript, recompute r = _r(seed), c = _b(seed) from the public seed, compute B = (<r, v> − rho·b) mod q, and the linear coefficient vector m for <r, c*s>.

3. Kannan embedding lattice (dimension 64 + 70 + 1 = 135)

Target short vector: (KS·s | rem − b/2 | 1) with all coordinates ≲ 32500 — short compared to q ≈ 2^23.

• Rows i = 0..63: [KS·δ_i | m_0[i], ..., m_69[i] | 0] with scaling KS = b//3 = 10833 (so KS·3 ≈ b/2 — the secret block has the same magnitude as the centered error block).
• Rows 64+j: q·δ_j in the error block (reduce equations mod q).
• Last row: [0...0 | −(B_j − b//2) mod q ... | 1] (centering rem at b/2 and embedding).

4. Reduce: LLL, then progressive BKZ

fpylll LLL first, then BKZ with increasing block sizes 20 → 30 → 40. The secret was recovered at BKZ-30/40 in roughly 3–4 minutes. Detect the answer row by: last coordinate ±1, first 64 coordinates divisible by KS with quotient |s_i| ≤ 3 (also try the row negated).

Operational note: use one file (70 transcripts, dim 135). A 140-transcript variant (dim 205) needed BKZ > 50, blew the shell timeout, and burned the 20-minute session TTL.

5. Decrypt and self-verify

w = struct.pack("<64b", s) → k = shake_256(b"SULTAN/key" + w).digest(32) → secret = e XOR shake_256(b"SULTAN/stream" + k + nonce). Correctness is confirmed by recomputing the blake2s tag d — no server round-trip needed to check a candidate.

6. Get the flag

The plaintext is a 28–32 char alphanumeric ASCII string. POST /api/verify with JSON {"guess": <recovered secret>} using the same session cookie used for the download (the session secret is shared across /download calls and regenerates after the 20-minute TTL). The server responds with the flag.

Full solver

#!/usr/bin/env python3
"""Sultan solver: HNP lattice attack on leaked high bits of <r,u>.

Per transcript (seed, rho, v):
  c = _b(seed) (public sparse +-1), r = _r(seed) (public), v = u + c*s mod q (given)
  <r,v> = <r,u> + <r,c*s> (mod q),  <r,u> mod q = rho*b + rem, rem in [0,b)
=> <r,c*s> + rem = (<r,v> - rho*b) mod q  : one equation per transcript.
Lattice: Kannan embedding, unknowns s (|s_i|<=3), errors f=rem-b/2 (|f|<=b/2).
"""
import hashlib
import struct
import sys
import zlib

from fpylll import BKZ, IntegerMatrix, LLL

q, n, ell, m, t, b = 8380417, 64, 1, 70, 16, 65000
secret_bound = 3
HEADER = "<4sIIIIIIIIIII"
KS = b // 3 // 1  # scaling for s-part: KS*3 ~ b/2  (10833)


def _b(x):
    h = hashlib.shake_256(b"SULTAN/challenge" + x).digest(4096)
    z, seen, i = [0] * n, set(), 0
    while len(seen) < t:
        u = int.from_bytes(h[i:i + 2], "little") % n
        i += 2
        if u not in seen:
            seen.add(u)
            z[u] = 1 if h[i] & 1 else -1
            i += 1
    return z


def _r(x):
    h = hashlib.shake_256(b"SULTAN/audit" + x).digest(4 * n * ell)
    return [
        [int.from_bytes(h[4 * (j * n + i):4 * (j * n + i + 1)], "little") % q for i in range(n)]
        for j in range(ell)
    ]


def parse(blob):
    raw = zlib.decompress(blob)
    (magic, version, Q, N, E_, M, T, B, sb, cs, th, slen) = struct.unpack(HEADER, raw[:48])
    assert magic == b"\xd8\x06\x00\x1a" and version == 4, (magic, version)
    assert (Q, N, E_, M, T, B) == (q, n, ell, m, t, b), (Q, N, E_, M, T, B)
    off = 48
    nonce = raw[off:off + 24]; off += 24
    e = raw[off:off + slen]; off += slen
    d = raw[off:off + 32]; off += 32
    transcripts = []
    for _ in range(M):
        x = raw[off:off + 32]
        y = raw[off + 32:off + 64]
        (rho,) = struct.unpack("<I", raw[off + 64:off + 68])
        v = list(struct.unpack("<%dI" % (ell * n), raw[off + 68:off + 68 + 4 * ell * n]))
        transcripts.append((x + y, rho, v))
        off += 32 + 32 + 4 + 4 * ell * n
    assert off == len(raw), (off, len(raw))
    return nonce, e, d, transcripts


def build_eqs(transcripts):
    """Return list of (mvec, B) with: sum_i mvec[i]*s[i] + rem == B (mod q)."""
    eqs = []
    for seed, rho, v in transcripts:
        r = _r(seed)[0]
        c = _b(seed)
        rv = sum(ri * vi for ri, vi in zip(r, v)) % q
        B = (rv - rho * b) % q
        mvec = [0] * n
        for k in range(n):
            ck = c[k]
            if ck:
                for j in range(n):
                    s = k + j
                    if s < n:
                        mvec[j] += ck * r[s]
                    else:
                        mvec[j] -= ck * r[s - n]
        eqs.append(([x % q for x in mvec], B))
    return eqs


def try_decrypt(s, nonce, e, d):
    w = struct.pack("<" + "b" * (ell * n), *s)
    k = hashlib.shake_256(b"SULTAN/key" + w).digest(32)
    p = hashlib.shake_256(b"SULTAN/stream" + k + nonce).digest(len(e))
    secret = bytes(u ^ v for u, v in zip(e, p))
    tag = hashlib.blake2s(b"SULTAN/tag" + nonce + e, key=k, digest_size=32).digest()
    if tag == d:
        return secret
    return None


def solve(eqs, tests, blocks=(20, 30, 40, 50, 60, 80)):
    """Kannan embedding + progressive BKZ. tests: list of (nonce,e,d) to check candidates."""
    M = len(eqs)
    dim = n + M + 1
    A = IntegerMatrix(dim, dim)
    for i in range(n):
        A[i, i] = KS
        for j, (mv, _) in enumerate(eqs):
            A[i, n + j] = mv[i]
    for j in range(M):
        A[n + j, n + j] = q
    last = n + M
    for j, (mv, Bv) in enumerate(eqs):
        # center rem: rem = b/2 + f  =>  subtract b/2 from RHS
        A[last, n + j] = -((Bv - b // 2) % q)
    A[last, last] = 1

    def check_rows():
        for rr in range(dim):
            lc = A[rr, last]
            if abs(lc) != 1:
                continue
            sgn = 1 if lc > 0 else -1
            s = []
            ok = True
            for i in range(n):
                val = A[rr, i]
                if val % KS:
                    ok = False
                    break
                si = (val // KS) * sgn
                if abs(si) > secret_bound:
                    ok = False
                    break
                s.append(si)
            if not ok:
                continue
            for (nonce, e, d) in tests:
                for cand in (s, [-x for x in s]):
                    sec = try_decrypt(cand, nonce, e, d)
                    if sec is not None:
                        return cand, sec
        return None, None

    print("[*] LLL (dim=%d) ..." % dim, flush=True)
    LLL.reduction(A)
    s, sec = check_rows()
    if s is not None:
        return s, sec

    for bs in blocks:
        print("[*] BKZ-%d ..." % bs, flush=True)
        par = BKZ.Param(
            block_size=bs,
            max_loops=8,
            flags=BKZ.AUTO_ABORT | BKZ.MAX_LOOPS,
        )
        BKZ.reduction(A, par)
        s, sec = check_rows()
        if s is not None:
            return s, sec
    return None, None


def main():
    files = sys.argv[1:]
    assert files, "usage: solve.py a.enc b.enc ..."
    nonce = e = d = None
    transcripts = []
    tests = []
    for fp in files:
        with open(fp, "rb") as fh:
            nonce_j, e_j, d_j, tr = parse(fh.read())
        nonce, e, d = nonce_j, e_j, d_j
        tests.append((nonce, e, d))
        transcripts.extend(tr)
    print("[*] total transcripts: %d" % len(transcripts))
    eqs = build_eqs(transcripts)
    s, sec = solve(eqs, tests)
    if s is None:
        print("[-] lattice solve failed")
        sys.exit(1)
    print("[+] s =", s)
    print("[+] secret =", sec.decode())


if __name__ == "__main__":
    main()