Cairn

Task description

One step at a time. Do not look back.

TL;DR

The challenge provides a rules document and a challenge.json that together define a deterministic pseudo-random walk on the supersingular isogeny graph over GF(p^2), starting at j0 = 1728. Each of the T = 2^20 steps hashes the current node to pick an isogeny degree and a neighbor; the final node j_T derives the AES key. There is no shortcut — the walk is a one-way hash chain (“do not look back”), so you must execute all 1,048,576 steps. The whole challenge is a correctness-and-performance grind; the AES-GCM authentication tag proves when you’ve walked it right.

The setup

Field. p is the secp256k1 prime

p = 2^256 - 2^32 - 977
  = 115792089237316195423570985008687907853269984665640564039457584007908834671663

Since p ≡ 3 (mod 4), X^2 + 1 is irreducible over GF(p), so we work in

GF(p^2) = GF(p)[i] / (i^2 + 1).

Every element is written z = a + b*i with canonical a, b ∈ [0, p). Serialization is ser(z) = LE32(a) || LE32(b) (two 32-byte little-endian halves, 64 bytes total).

Start point. j0 = 1728. The elliptic curve with j-invariant 1728 is y^2 = x^3 + x, which is supersingular whenever p ≡ 3 (mod 4). So j0 is a supersingular j-invariant, and because supersingular j-invariants are closed under isogenies and all live in GF(p^2), the entire walk stays inside the supersingular isogeny graph — a (roughly p/12 ≈ 2^252-node) Ramanujan-like expander. That graph is far too large to enumerate, which is the point: the walk cannot be shortcut by precomputation.

The deterministic hash-chain walk

Set j := j0. For each step index i = 0, 1, …, T-1 (T = 1048576 = 2^20):

1. Hash. h = SHA256( ser(j) || BE8(i) || salt ), where BE8(i) is the 8-byte big-endian step index and salt is the 32-byte public salt from challenge.json.
2. Degree. l = L[ h[0] mod 4 ] with L = [2, 3, 5, 7].
3. Polynomial. Form f(Y) = Phi_l(j, Y) over GF(p^2) — substitute X = j into the classical modular polynomial Phi_l(X, Y) (its integer coefficients, given in challenge.json, are reduced mod p). Phi_l is symmetric and monic of degree l+1 in each variable, so f is monic of degree l+1.
4. Roots = neighbors. Take the squarefree part and compute all distinct roots of f in GF(p^2). These are exactly the j-invariants l-isogenous to j (the neighbors in the l-isogeny graph). In a supersingular graph f splits completely, so there are l+1 of them (counting the structure correctly, n distinct).
5. Order + step. Sort the roots by (a, b) lexicographically as unsigned 256-bit integers. With n distinct roots, move to j := r_{ h[1] mod n }.

Because step i+1 depends on SHA256 of the exact node reached at step i, the sequence is a one-way chain: you cannot parallelize across steps, skip ahead, or invert it. “One step at a time. Do not look back.” means precisely that the only way forward is to execute every step in order.

After the loop, j_T is the final node.

Key derivation and decryption

key = SHA256( ser(j_T) || "IsogenyLabyrinth" )     # 16-byte ASCII suffix, no newline

The flag is AES-256-GCM(key, nonce) with empty AAD; nonce_b64, ciphertext_b64, tag_b64 are in challenge.json. Using decrypt_and_verify means the GCM tag is a built-in oracle: it only verifies if j_T (hence key) is exactly right, so a successful decrypt is proof of a correct walk — no guessing of the flag.

Results:

j_T.a = 2951744835154356679408485058539998725114852725772335444978399055687248892073
j_T.b = 76297261829986891261504719508868871098352200233656976244600190934732692176052
key   = bf722c55d3a4656cd731699335706f1dab4ba16caf8c2a6bb45b1f949adbc5ca
FLAG  = hiCTF{w41k_th3_sup3rs1n9u14r_l46yr1ntH}

The real work: making 2^20 root-findings feasible

The math is unambiguous; the difficulty is wall-clock time. Each step needs the roots in GF(p^2) of a degree-≤8 polynomial, and there are over a million steps.

This box had no SageMath, no PARI/cypari2, and no C compiler — only Python 3.14 with python-flint 0.9.0 and gmpy2. FLINT’s generic extension-field type (fq, required because p is 256-bit) factors a degree-8 polynomial over GF(p^2) in ~40–55 ms; averaged over the degree distribution that was ~20 ms/step, i.e. ~6 hours for 2^20 steps.

Optimization — factor the norm over GF(p) instead of f over GF(p^2). For f with coefficients in GF(p^2), form the norm polynomial

g(Y) = f(Y) · conj(f)(Y),

where conj conjugates each coefficient (a + b*i → a - b*i, which is the Frobenius x → x^p on GF(p^2) since p ≡ 3 mod 4). g has coefficients in GF(p) and degree 2(l+1). Because f splits completely in GF(p^2), g splits over GF(p) into linear and quadratic factors only (each root r ∉ GF(p) pairs with its conjugate into an irreducible quadratic). FLINT’s fmpz_mod_poly factorization over the base field GF(p) is dramatically faster than generic fq (a degree-16 norm factors in ~12 ms vs ~55 ms).

For each factor:

• linear Y - r → candidate root (r, 0) in GF(p);
• quadratic Y^2 + uY + v with discriminant D = u^2 - 4v a non-residue in GF(p) → its two GF(p^2) roots are (-u ± i·s)/2 where s^2 = -D in GF(p). Since p ≡ 3 mod 4, s = (-D)^{(p+1)/4} mod p is a single fast modular exponentiation (no Tonelli-Shanks).

Each candidate is kept iff f(candidate) == 0, which cleanly separates the roots of f from the roots of conj(f). This was verified identical to FLINT’s roots() over 1500 consecutive steps (0 mismatches), with no factor of degree > 2 ever appearing.

Result: ~150 steps/s (~2 hours total) — about a 3x speedup over the naive FLINT path and the difference between “overnight” and “one coffee break”.

Resumability. solver.py checkpoints (i, a, b) to ckpt.json every 5000 steps (atomic write). The checkpoint stores only the current node, so it is algorithm-independent: the run survived a mid-computation machine sleep and was even restarted on the faster root-finder from a checkpoint produced by the slow one, with no loss of correctness.

Solver

The full resumable walker with the fast norm-based root finder, checkpointing, key derivation, and AES-256-GCM decryption:

import sys, json, time, hashlib, os, base64
import flint
from flint import fmpz_mod_poly_ctx, fq_default_ctx, fq_default_poly_ctx

CHAL = sys.argv[1]
CKPT = sys.argv[2] if len(sys.argv) > 2 else os.path.join(
    os.path.dirname(os.path.abspath(__file__)), "ckpt.json")

cj = json.load(open(CHAL, "r"))
p = int(cj["p"])
j0 = [int(cj["j0"][0]) % p, int(cj["j0"][1]) % p]
salt = bytes.fromhex(cj["salt_hex"])
T = int(cj["T"])
L = cj["L"]
phi_raw = cj["phi"]

PHI = {}
MAXX = {}
for l in L:
    d = {}
    mx = 0
    for x_exp, y_exp, coeff in phi_raw[str(l)]:
        d.setdefault(y_exp, []).append((x_exp, coeff % p))
        mx = max(mx, x_exp, y_exp)
    PHI[l] = d
    MAXX[l] = mx

pc = fmpz_mod_poly_ctx(p)
ctx = fq_default_ctx(modulus=pc([1, 0, 1]))   # GF(p^2) = GF(p)[i]/(i^2+1)
Pctx = fq_default_poly_ctx(ctx)
gen = ctx.gen()

def to_ab(z):
    lst = z.to_list()
    a = int(lst[0]) if len(lst) >= 1 else 0
    b = int(lst[1]) if len(lst) >= 2 else 0
    return a, b

def mk(a, b):
    return ctx(a) + ctx(b) * gen

INV2 = pow(2, p - 2, p)
SQE = (p + 1) // 4   # p = 3 mod 4

def roots_fast(f):
    """Distinct roots of f in GF(p^2) via factoring the norm f*conj(f) over GF(p)."""
    cf = [c.frobenius() for c in f.coeffs()]
    g = f * Pctx(cf)
    real = []
    for z in g.coeffs():
        za, zb = to_ab(z)
        if zb != 0:
            return None
        real.append(za)
    _, facs = pc(real).factor()
    cands = set()
    for fp, _m in facs:
        d = fp.degree()
        co = [int(x) for x in fp.coeffs()]
        if d == 1:
            cands.add(((-co[0]) % p, 0))
        elif d == 2:
            u = co[1] % p; v = co[0] % p
            disc = (u * u - 4 * v) % p
            s = pow((-disc) % p, SQE, p)
            if (s * s) % p != (-disc) % p:
                return None
            ap = ((-u) * INV2) % p; bp = (s * INV2) % p
            cands.add((ap, bp)); cands.add((ap, (-bp) % p))
        else:
            return None
    out = [(ca, cb) for (ca, cb) in cands if f.evaluate(mk(ca, cb)).is_zero()]
    return sorted(out)

# resume from checkpoint
start_i = 0
a, b = j0[0], j0[1]
if os.path.exists(CKPT):
    try:
        ck = json.load(open(CKPT))
        start_i = int(ck["i"]); a = int(ck["a"]); b = int(ck["b"])
        print(f"[resume] i={start_i} a={a} b={b}", flush=True)
    except Exception as e:
        print("[resume failed]", e, flush=True)

j = mk(a, b)

def save_ckpt(i, a, b):
    tmp = CKPT + ".tmp"
    json.dump({"i": i, "a": a, "b": b}, open(tmp, "w"))
    os.replace(tmp, CKPT)

t0 = time.time()
last = start_i
CK_EVERY = 5000
for i in range(start_i, T):
    a, b = to_ab(j)
    h = hashlib.sha256(
        a.to_bytes(32, "little") + b.to_bytes(32, "little")
        + i.to_bytes(8, "big") + salt).digest()
    l = L[h[0] % 4]
    tbl = PHI[l]; mx = MAXX[l]
    jp = [ctx(1)]
    for k in range(1, mx + 1):
        jp.append(jp[-1] * j)
    deg = l + 1
    coeffs = []
    for k in range(deg + 1):
        terms = tbl.get(k)
        acc = ctx(0)
        if terms:
            for x_exp, c in terms:
                acc = acc + jp[x_exp] * c
        coeffs.append(acc)
    f = Pctx(coeffs)
    distinct = roots_fast(f)
    if not distinct:
        distinct = sorted(to_ab(r) for r, _ in f.roots())
    n = len(distinct)
    na, nb = distinct[h[1] % n]
    j = mk(na, nb)
    if (i + 1) % CK_EVERY == 0:
        save_ckpt(i + 1, na, nb)
        now = time.time()
        rate = (i + 1 - last) / (now - t0) if now > t0 else 0
        done = i + 1 - start_i
        rem = (T - (i + 1)) / rate if rate else 0
        print(f"[i={i+1}/{T}] {rate:.1f} steps/s  ETA={rem/3600:.2f}h",
              flush=True)
        last = i + 1; t0 = now

# j is now j_T — derive key and decrypt
aT, bT = to_ab(j)
save_ckpt(T, aT, bT)
print(f"[done] j_T = ({aT}, {bT})", flush=True)

serT = aT.to_bytes(32, "little") + bT.to_bytes(32, "little")
key = hashlib.sha256(serT + b"IsogenyLabyrinth").digest()
print("key(hex):", key.hex(), flush=True)

from Crypto.Cipher import AES
nonce = base64.b64decode(cj["nonce_b64"])
ciphertext = base64.b64decode(cj["ciphertext_b64"])
tag = base64.b64decode(cj["tag_b64"])
cph = AES.new(key, AES.MODE_GCM, nonce=nonce)
pt = cph.decrypt_and_verify(ciphertext, tag)
print("FLAG:", pt.decode(errors="replace"), flush=True)

Lessons / notes

• Recognize the pieces: p = secp256k1, p ≡ 3 mod 4, j0 = 1728, modular polynomials Phi_l, and "IsogenyLabyrinth" all scream supersingular isogeny walk. There is no cryptanalytic shortcut — it is a verifiable-delay-style grind by design.
• Parse the big integers with arbitrary precision (the RULES explicitly warn that IEEE-754 JSON parsers corrupt the 70-digit coefficients). Python’s json + int is fine.
• When you lack Sage/PARI, you can still get competitive finite-field performance by pushing work down to the base field: the norm trick turns GF(p^2) root-finding into GF(p) factorization plus one square root per conjugate pair.
• Always checkpoint multi-hour sequential computations by their minimal state, so the run is immune to interruptions and to swapping in a faster inner loop.