The Forged Signet

Platform: CACTF2026 | Category: Crypto | Type: Challenge | Difficulty: Medium | OS: NA | Author: XESXOR | Date: 2026-07-28 | Status: Solved Techniques: simons_algorithm, hidden_xor_period_recovery, gf2_gaussian_elimination, quantum_oracle_abuse

Summary

Task: HTTP-fronted quantum oracle implementing a 2-to-1 function with a hidden 64-bit XOR period s (f(x)=f(x XOR s)); you choose the middle single-qubit layer. Solution: choose L=H to complete Simon's algorithm, collect samples y satisfying y·s=0 over GF(2), Gaussian-eliminate to a rank-63 system, and extract the unique nonzero null-space vector s.

The Forged Signet — CACTF2026

Description

A long time ago the Brine Signet was the one thing nobody could fake; it was how the Crown proved a seal was real. Then it broke, and everything went bad. Every seal is still checked against a secret called the First Mark, a hidden string s that lives inside the verifier. The verifier has a flaw it was never meant to have: if two inputs differ by exactly the Mark, it cannot tell them apart, so f(x) and f(x XOR s) always look the same to it. The Registry hid the verifier behind a quantum oracle and swore the Mark was safe. It is not.

Target: 154.57.164.65:32671 ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

English summary: A quantum oracle (exposed over an HTTP API) implements a 2-to-1 function f with a hidden non-zero 64-bit period s, i.e. f(x) = f(x XOR s). The goal is to recover the "First Mark" s and submit it to forge a signet, which returns the flag. This is Simon's algorithm dressed up in flavor text.

Analysis

Recon

• The target looked like a raw TCP service but is actually an HTTP server (Python gunicorn). Sending GET / HTTP/1.0 produced a normal HTTP response; raw TCP banter yielded nothing.
• The frontend app.js ("Resonance Oracle") exposed three API endpoints.
• GET /api/oracle returns a datasheet:
  • n = 64 (qubits)
  • promise: f(x) = f(x XOR s) for a secret non-zero First Mark s of n bits
  • circuit: each run: H^n . U_f . measure&discard(output) . L . measure(input) — you choose the single-qubit layer L
  • serial: fd6ab720d8723b7f
• Endpoints:
  • POST /api/run {layer, shots} → returns measured input bitstrings. layer is a single-qubit gate applied to every qubit (or a list of n gates). Gates: I, X, Y, Z, H, S, SDG. shots 1–256.
  • POST /api/forge {s} → submit the recovered 64-bit First Mark; returns {"forged": true, "flag": ...} if correct. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

The vulnerability / key insight

The circuit is:

H^n  .  U_f  .  measure&discard(output)  .  L  .  measure(input)

This is exactly Simon's algorithm — but the middle single-qubit layer L is left up to the attacker. The correct choice is L = H (Hadamard).

Simon's algorithm math:

1. Start in |0>^n |0>^m, apply H^n to the input register → uniform superposition over all x.
2. Apply U_f → sum_x |x>|f(x)>. Because f is 2-to-1 with f(x) = f(x XOR s), each output value z = f(x) is produced by exactly two inputs, x and x XOR s.
3. Measure & discard the output register. The input register collapses to (|x0> + |x0 XOR s>)/sqrt(2) for some random coset representative x0.
4. Apply the second Hadamard layer L = H to the input register. The amplitude of measuring y is proportional to (-1)^{x0·y} + (-1)^{(x0 XOR s)·y} = (-1)^{x0·y}(1 + (-1)^{s·y}). This is non-zero only when s·y ≡ 0 (mod 2). ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

So every measured y satisfies the linear constraint y · s ≡ 0 (mod 2) (dot product over GF(2)). Collecting ~n independent such samples gives a homogeneous linear system whose solution set (null space) is exactly {0, s}. The unique nonzero null-space vector is the hidden period s.

Solution

1. Call POST /api/run with {"layer":"H","shots":256} repeatedly, collecting unique nonzero 64-bit samples y. (256 unique nonzero samples were gathered.)
2. Build a matrix whose rows are the samples and run Gaussian elimination over GF(2). Result: rank = 63, null-space dimension = 1.
3. Extract the unique nonzero null-space vector: set the single free column = 1, back-substitute the pivots. Verify y · s = 0 (mod 2) for every collected row.
4. POST /api/forge {"s": s} → returns forged=true and the flag. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Solver

 python read-only • copy allowed Copy
#!/usr/bin/env python3
import json, urllib.request

HOST = "http://154.57.164.65:32671"
N = 64

def run(layer="H", shots=256):
    req = urllib.request.Request(
        HOST + "/api/run",
        data=json.dumps({"layer": layer, "shots": shots}).encode(),
        headers={"content-type": "application/json"},
        method="POST",
    )
    return json.load(urllib.request.urlopen(req, timeout=30))["samples"]

def forge(s):
    req = urllib.request.Request(
        HOST + "/api/forge",
        data=json.dumps({"s": s}).encode(),
        headers={"content-type": "application/json"},
        method="POST",
    )
    return json.load(urllib.request.urlopen(req, timeout=30))
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

# 1. Collect unique nonzero samples with L = H
rows, seen = [], set()
for _ in range(4):
    for s in run("H", 256):
        v = int(s, 2)
        if v != 0 and v not in seen:
            seen.add(v)
            rows.append(v)
    if len(rows) >= 200:
        break
print(f"collected {len(rows)} unique nonzero samples")

# 2. Gaussian elimination over GF(2) (row = integer, bit i = coeff of var i)
basis, pivot_col = [], []
for r in rows:
    cur = r
    for b, pc in zip(basis, pivot_col):
        if (cur >> pc) & 1:
            cur ^= b
    if cur == 0:
        continue
    pc = cur.bit_length() - 1
    basis = [b ^ cur if (b >> pc) & 1 else b for b in basis] + [cur]
    pivot_col = pivot_col + [pc]
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

rank = len(basis)
print(f"rank = {rank}, nullspace dim = {N - rank}")

pivots = set(pivot_col)
free_cols = [c for c in range(N) if c not in pivots]

# 3. For the single free column (dim 1), set it = 1 and solve pivots
for free in free_cols:
    s_val = 1 << free
    for b, pc in zip(basis, pivot_col):
        rest = b & ~(1 << pc)
        if bin(rest & s_val).count("1") & 1:
            s_val |= (1 << pc)
    sbin = format(s_val, f"0{N}b")
    if s_val != 0 and all(bin(r & s_val).count("1") % 2 == 0 for r in rows):
        # 4. Forge the signet
        print("candidate s =", sbin)
        print("FORGE RESULT:", forge(sbin))
        break

‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Recovered period:

s = 0110010010101010010001100010011111110110010100011001110110100010

Submitting s to /api/forge returned {"forged": true, "flag": ...}. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍