Headache — ASIS CTF Quals 2026

Description

=== Non-Linear Hamiltonian Authenticator Oracle (H-PRF) ===
Dimension: 4, Rounds to pass: 7
Max queries per round: 1200, Max sequence length: 20
Commands: 'eval <json_matrix>' or 'challenge'

English summary: a network service hides 60 real parameters per round — coupling tensors A of shape (3,4,4) and observable vectors B of shape (3,4), drawn uniformly from [0.5, 2.0). Given only black-box eval queries returning a scalar tag, we must recover the model precisely enough to predict tags of 6 fresh random sequences (lengths 3–17) with max abs error < 1e-6, for 7 consecutive rounds with fresh secrets each. The flag is released after round 7.

Summary

The oracle is a smooth 3-channel softmax ensemble, so exact per-parameter recovery from chosen queries beats blind 60-dimensional nonlinear fitting:

1. Length-1 probes give exact linear combinations of B.
2. Pair probes reduce every matrix entry A_c[i,j] (jointly with the row of B) to fitting a 3-sigmoid mixture t·Σ_c b_c·σ(t·a_c) on a 1-D curve.
3. Per-pair fits are sometimes degenerate (two nearly equal a's make the split of b unidentifiable), so b is fitted jointly per row — shared across the 4 columns — against all 4 pair curves at once (15 parameters).
4. Row-wise channel permutations (6^4 labelings) are resolved against held-out validation queries; a torch LBFGS global polish fires only on genuine near-misses.
5. The whole 7-round session must fit inside the server's ~125 s connection lifetime: parallel PoW, windowed request pipelining (~5 s/round of querying), 8-way multiprocessing for fitting, and heartbeat keepalives.

All 7 rounds authenticated with max_err between 2.7e-09 and 8.4e-13; total wall time ~90 s, 1512 cumulative queries.

Challenge mechanics

Protocol (server.py):

• PoW: sha256(prefix + nonce) must start with "00000" (20 bits). Then the command loop starts.

• eval <json X> — X is (n,4), 1 ≤ n ≤ 20; 1200 queries per round; each query costs the server a 0.03 s sleep. Per channel c with tail row t = X[-1]:

  s_i    = x_i · (A_c t)                    # per-row score  (einsum 'j,jk,ik->i')
  w_i    = softmax(s)_i                     # Boltzmann weights over rows
  f_c    = Σ_i w_i · (x_i · b_c)            # thermal observable
  tag    = Σ_c f_c                          # 3 channels
  

• challenge — server generates 6 random sequences, lengths [3,5,7,9,13,17], rows uniform in [-1,1], and sends them. The client must answer verify <json_tags>; if any tag is off by ≥ 1e-6 the server closes the connection — a rejected verify loses the whole session. Passing all 7 rounds returns the flag.

Fresh A, B every round ⇒ the recovery pipeline must be reliable, not lucky: budget 1200 queries, and the connection dies ~125 s after connect (activity-independent, measured empirically), so the entire 7-round session — PoW, 7×(probing + fitting + verify) — has to fit in one window.

The math of the pair-probe reduction

Length-1 probes. With X = [e_j] a single row, softmax over one row is identically 1, so

f([e_j]) = Σ_c b_c[j]  =: s_j        (exact, no nonlinearity)

This yields 4 numbers s_0..s_3, the column sums of B.

Pair probes. Take X = [e_j + t·e_i ; e_j], so the tail is e_j and A_c t = A_c[:,j]. Only two rows enter the softmax, so the weight of row 1 is a plain sigmoid of the score difference t·A_c[i,j]:

f = Σ_c [ b_c[j] + t·b_c[i]·σ(t·A_c[i,j]) ]  =  s_j + dy(t)
dy(t) = t · Σ_c b_c[i] · σ(t·a_c),   a_c = A_c[i,j]

So each ordered pair (i,j) produces a 3-sigmoid mixture curve with exactly 6 unknowns: b = B[:,i] (3 values) and a = A[:,i,j] (3 values), plus one linear constraint Σ_c b_c = s_i known from the length-1 probes. 16 ordered pairs × 4 rows cover every entry of A and every entry of B.

Negative-t points are redundant. For T > 0:

dy(−T)/(−T) = Σ_c b_c·σ(−T·a_c) = Σ_c b_c − Σ_c b_c·σ(T·a_c) = s_i − dy(T)/T

Given s_i, every negative-side sample is a deterministic function of the positive side. Symmetric probe sets waste queries; dense sampling of the positive transition region is the right design. The final grid: 11 points t ∈ {0.55, 0.75, 1.0, 1.35, 1.8, 2.4, 3.1, 4.0, 5.2, 6.8, 8.8} (each a_c ∈ [0.5, 2.0] puts its sigmoid knee 1/a_c inside this range) plus 2 negative decay points t ∈ {−9, −13} kept only as seeds for Prony-style exponential fits. Total per round: 4 singles + 16 × 13 pairs + 4 held-out validation queries = 216 of 1200.

Degeneracy analysis and the joint row fit

Per-pair identification. For one (i,j) curve, b is eliminated linearly: with a fixed, dy = M1(a)·b where M1[:,c] = t·σ(t·a_c); the constraint Σb = s_i removes one column, leaving a 2-variable least-squares solve via normal equations. Differential evolution over the 3 bounded a's (a ∈ [0.5,2]) generates seeds; a bounded 6-parameter least_squares polish (residuals + 40·(Σb − s_i)) finishes. Targeted "split" seeds re-separate near-equal a pairs by mid-point perturbations.

The hard case. When two true a_c's are nearly equal, the mixture is practically 2-sigmoid and the split of b between the two close channels becomes unidentifiable from a single curve: the residual stalls around 1e-8 with a wrong b that still fits that one curve perfectly.

The key trick — fit the row, not the pair. b = B[:,i] is shared by all 4 pair curves of row i. So fit (b[3] + a[4][3]) = 15 parameters against all 4 curves at once (52 data points + 1 constraint). Degenerate columns no longer block the row: the shared b is pinned by the well-conditioned columns.

Pipeline per row:

1. Anchor sweep: collect candidate b tuples from all per-pair fits;
2. for each anchor, multistart fixed-b fits of the 4 a triples (inits from per-pair candidates, sorted to the anchor's channel order);
3. one bounded 15-parameter least_squares polish;
4. heavy 15-dim DE fallback only if still inexact.

Exact rows reach residual ~1e-14. Enrichment for stubborn rows: extra t-points are queried only for that row's 4 pairs (e.g. {0.5, 1.7, 3.0, 6.5, −10.5}, then {1.2, 2.0, 3.6, 8.0, −15.0}) and both candidate generation and the joint polish are redone on the augmented data.

Assembly. Per-row fits return channels in arbitrary (sorted-b) order, so 4 independent channel permutations must be resolved: all 6^4 = 1296 labelings are scored against the held-out validation queries (cheap); the correct one gives val_err ~ 1e-12. If val_err > 1e-9, a torch LBFGS global polish over all recorded (X, y) pairs (with sigmoid reparameterization to respect the [0.5, 2.0] bounds) runs as a safety net. The solver refuses to send challenge unless val_err < 1e-8 — a rejected verify kills the session.

Core math (excerpt from the solver; full script in artifacts):

def pair_model(ts, b, a):
    """dy(t) = t * sum_c b_c * sigmoid(t * a_c) for signed t array."""
    ts = np.asarray(ts, dtype=float)
    return ts * np.sum(b / (1.0 + np.exp(-np.outer(ts, a))), axis=1)

def vp_obj(a3):
    # b eliminated linearly; equality constraint sum(b) = s_i via substitution
    Sig = 1.0 / (1.0 + np.exp(-np.outer(ts, a3)))
    M1  = ts[:, None] * Sig
    Mm  = M1[:, :2] - M1[:, 2:3]          # b3 = s_i - b1 - b2
    r   = dy - M1[:, 2] * s_i
    x, *_ = np.linalg.lstsq(Mm, r, rcond=None)
    b   = np.array([x[0], x[1], s_i - x[0] - x[1]])
    return float(np.sum((pair_model(ts, b, a3) - dy) ** 2))

def fit_row(dy_row, s_i, cand_lists, ...):
    # joint 15-param residual: b[3] shared across all 4 columns of the row
    def resid(th):
        b, As = th[:3], th[3:].reshape(D, C)
        r = [pair_model(ts, b, As[j]) - dy_row[j] for j in range(D)]
        return np.concatenate(r + [[40.0 * (b.sum() - s_i)]])

Engineering against the ~125 s clock

Empirically the server kills the TCP connection ~125 s after connect, independent of activity. Three early sessions died to this before the fix. The whole session therefore had to fit in ~118 s:

• PoW in parallel: 20-bit hashcash split across 8 processes (imap_unordered, stride = nproc); found in well under a second (e.g. nonce 5874 in the winning session).
• Pipelined evals: instead of one round trip per query (which would cost 216 × 0.03 s pure server sleep per round plus RTTs serially), ask_batch writes window=32 requests then reads 32 responses — the server sleeps concurrently across the window. Query phase: ~5 s/round.
• Multiprocessing pool (8 workers) for per-pair candidate generation and per-row joint fits — the compute phases dropped to a few seconds per round.
• Heartbeat: a daemon thread writes "\n" every 15 s during silent compute phases; the server's eval loop ignores empty lines (if not line: continue), keeping the socket alive through long fits.
• Per-round cost: 11–19 s; queries 216/round (+enrichment when needed) out of 1200.

Failed approaches

• Naive 60-parameter nonlinear least squares from random starts on mixed random queries: multimodal landscape, stalls ~1e-2 — nowhere near 1e-6. (A local replica did converge once to a functionally equivalent model with ~1e-12 error, but parameter-exact recovery via probes is far more reliable.)
• Derivative/moment expansion of the sigmoid: the 9th moment was not measurable in float64 precision; numerically hopeless.
• Symmetric ± probe sets: negative-t samples add no information given s_i (see the redundancy identity above) — wasted queries.
• Requiring per-pair exactness: near-degenerate columns (two close a's) cannot be resolved per-pair; the joint per-row fit is required.
• Sequential queries / no heartbeat / no pipelining: three remote sessions were killed by the ~125 s limit before round 7 could complete.

Winning session (remote8.log)

Round	fit val_err	wall	cumulative queries	server max_err
1	3.08e-12	13 s	216	2.36e-12
2	1.78e-12	11 s	432	1.10e-12
3	5.73e-09	19 s	648	2.67e-09
4	3.50e-13	12 s	864	1.95e-13
5	9.13e-13	11 s	1080	8.38e-13
6	6.44e-12	13 s	1296	2.30e-12
7	7.14e-12	11 s	1512	2.64e-12 → flag

Round 3 shows the retry loop earning its keep: two attempts stalled at val_err = 1.127e-05 (degenerate row, LBFGS polish could not fix it), the third regeneration of candidate seeds broke through to 5.73e-09 — accepted, since the held-out error bound is what gates the challenge command, and the actual challenge error came out 2.67e-09 < 1e-6.

Artifacts

• Final solver: /Users/sergeyskorobogatov/Projects/Agents/CTF/tasks/asisctf2026/headache/solver5.py
• Official challenge source: /Users/sergeyskorobogatov/Projects/Agents/CTF/tasks/asisctf2026/headache/Headache/server.py
• Investigation log: /Users/sergeyskorobogatov/Projects/Agents/CTF/tasks/asisctf2026/headache/notes.md
• Winning session transcript: /Users/sergeyskorobogatov/Projects/Agents/CTF/tasks/asisctf2026/headache/remote8.log
• Earlier iterations: solver.py … solver4.py, remote.log … remote7.log, ~33 local test logs in the same directory.