name: ctf-crypto
description: Cryptography CTF attacks: RSA, AES, ECC, PRNG, hash length-extension, padding oracles, lattice/LWE/CVP, HNP, Coppersmith, Pollard, Wiener, ZKP/Circom/halo2, post-quantum KEM. Dispatch on prime shape, oracle type, or scheme artefact.
license: MIT
compatibility: Requires filesystem-based agent (Claude Code or similar) with bash, Python 3, and internet access for tool installation.
allowed-tools: Bash Read Write Edit Glob Grep Task WebFetch WebSearch
metadata:
user-invocable: "false"
CTF Cryptography
Quick reference for crypto CTF challenges. Each technique has a one-liner here; see supporting files for full details with code.
Additional Resources
- classic-ciphers.md — Vigenere/Kasiski, XOR variants, OTP reuse, homophonic
- modern-ciphers.md — AES/CBC/GCM, padding oracle, Bleichenbacher, LFSR, length extension
- modern-ciphers-2.md — 2024-26: S-box collision, AES-GCM derived, Ascon diff, linear MAC, FFT Shamir
- rsa-attacks.md — small e/d, common mod, Wiener, Hastad, Fermat, Coppersmith, polynomial-prime
- rsa-attacks-2.md — 2025-26: TLS blinder-squaring + Coppersmith partial-
d
- rsa-attacks-oracle.md — Manger's OAEP, padding/timing/blinding oracles
- ecc-attacks.md — invalid curve, Smart's, Pohlig-Hellman, ECDSA nonce, genus-1 variety
- zkp-and-advanced.md — Groth16/PLONK/halo2/Noir ZK, Z3, SSS, LogUp/ProtoStar
- prng.md — MT19937, LCG, V8 XorShift128+, time-seed, ChaCha20 key recovery
- prng-2.md — 2024-26: GF(2) matrix, middle-square, logistic, Legendre bit oracle
- historical.md — Lorenz SZ40, book cipher
- advanced-math.md — CVP/Babai, LLL, Coppersmith, HNP, Pohlig-Hellman, Quaternion RSA
- advanced-math-2.md — 2024-26: LWE, clock group, CSIDH trace, Joux, GEA LFSR, Hill off-by-one
- exotic-crypto.md — braid-group DH, tropical, ePrint scheme killers, CSIDH sign-leak, PQ (Kyber/UOV)
Pattern Recognition Index
Map observable signals (not challenge names) to the right technique. Scan this first.
| Signal in challenge | Technique → file |
|---|
pow(m, e, n) == m for some m ∉ {0,1,n-1}; timing outlier on one input | RSA fixed-point factoring → rsa-attacks.md |
| Close primes (` | p - q |
Small d (Wiener bound), or small e + small m | Wiener / cube-root → rsa-attacks.md |
Same m under same e to several n_i | Hastad broadcast / CRT → rsa-attacks.md |
| PKCS#1 v1.5 error side-channel on an RSA decrypt endpoint | Bleichenbacher / Manger → rsa-attacks-oracle.md, modern-ciphers.md |
| Two faulted RSA signatures, TLS renegotiation between them | Blinder A → A² bit recovery → rsa-attacks-oracle.md |
| Many linear eqs mod q with bounded error (ECDSA partial nonce, truncated LCG, HNP) | CVP/Babai (rkm0959 template) → advanced-math.md |
| Power/EM traces with uniform length but shape clustering | Waveform-morphology analysis (sliding min/max/mean) → advanced-math-2.md |
| CSIDH / isogeny + small secret vector + AES oracle | Brute force 419-element shared-secret space → advanced-math-2.md |
| Padding-oracle endpoint on CBC | Byte-by-byte CBC padding oracle → modern-ciphers.md |
| ECDSA with partial-nonce leak / same nonce reused | Pohlig-Hellman / nonce lattice → ecc-attacks.md, advanced-math.md |
| MT19937 outputs visible (624 words) | State recovery via Python randcrack or GF(2) matrix → prng.md |
| Boolean predicate + "find x such that f(x)=1" + N small | Qiskit Grover k = π/4√(N/M) → ctf-misc/ai-ml.md |
| Model weights file + accuracy-gate grader | Federated label-flip poisoning → ctf-misc/ai-ml.md |
| Two parsers for same URL/path/HTML (different libs in deps) | Parser differential → ctf-web/auth-and-access.md |
halo2 circuit: advice_values[…] fill without RNG, ≥ N proofs same secret | Blinding-omission Lagrange recovery → zkp-and-advanced.md |
LogUp/ProtoStar-style lookup over F_p with p ≤ 2^32 | Characteristic-repetition bypass → zkp-and-advanced.md |
Noir/Circom sha256_var(buf, len) with trailing buf unconstrained | Trailing-byte under-constraint → zkp-and-advanced.md |
| Obfuscated projective embedding, degree-2 coord relations, group order = small·large | Genus-1 variety → Weierstrass + BSGS/MOV/NFS → ecc-attacks.md |
Jacobian Point class without is_on_curve check | Invalid-curve small-order pts → ecc-attacks.md |
| Scheme quoting ePrint, "homomorphism learning" / "entropic operator" | Linear-algebra scheme-killer → exotic-crypto.md |
CSIDH/group-action KEM exposing group_action(e, ±1) | Sign-leak oracle → exotic-crypto.md |
| Distinguishable "invalid padding" vs "invalid message" on OAEP endpoint | Manger's attack → rsa-attacks-oracle.md |
| Modulus hex shows repeated-block structure (u·2^k + u·v + w) | Polynomial factorisation of n → rsa-attacks.md |
| Shamir t-of-n with x_i^t = 1 (roots of unity) | FFT collapse recovery → modern-ciphers-2.md |
AES with Nr=1 literal or one-round helper | Linear inversion from one PT/CT pair → modern-ciphers-2.md |
| Hill/classical cipher mod = printable-ASCII range (94) | Try N-1 and N-2 → advanced-math-2.md |
| Dual hash suffix constraint MD5 + SHA1 (3-byte) | Joux multicollision cascade → advanced-math-2.md |
| GEA-1/GEA-2 LFSR with known keystream prefix | Rank-deficient key MITM → advanced-math-2.md |
Bit oracle on (s_i / p) Legendre symbol | Z3/lattice over GF(p) state → prng-2.md |
Falcon-512/1024 ref-impl signing with double-based FPU math + many signature samples | FP subnormal / rounding leakage → exotic-crypto.md#falcon |
ML-DSA / Dilithium signatures with hints h (ω-bounded) or filtered z | Hint-leak lattice primal attack → exotic-crypto.md#ml-dsa |
| SPHINCS+ / SLH-DSA signing where FORS idx can repeat (non-atomic counter) | Tree-reuse forgery → exotic-crypto.md#slh-dsa |
CSIDH / CTIDH KEM accepts attacker-supplied Montgomery A with no twist check | Invalid-curve Pohlig-Hellman → exotic-crypto.md#invalid-curve-pq |
| Custom KDF iterated N times before encrypt, entropy-shrinking op inside; PCAP has hundreds of packets | Null-key fixed-point: try key=0 first → modern-ciphers-2.md |
AES ref-impl in Python with m[-8]/m[-4] negative indices + accepts len > 16 | Extended-block linear byte relation → modern-ciphers-2.md |
Merkle tree leaves = bcrypt(fixed_salt, user_payload) with variable-length payload | 72-byte truncation collision → modern-ciphers-2.md |
TLS server with RSA signing + OOB-byte primitive corrupting d; two renegotiations per session | Blinder squaring + Coppersmith partial-d → rsa-attacks-2.md |
For each row the point is: if you see the signal, go to the file — you never need to know the challenge's name.
For inline code/cheatsheet quick references (grep patterns, one-liners, common payloads), see quickref.md. The Pattern Recognition Index above is the dispatch table — always consult it first; load quickref.md only if you need a concrete snippet after dispatch.
CTF Crypto - Advanced Math (2024-2026)
Modern lattice / Coppersmith / algebraic attacks from 2024-2026. For the classical toolbox (isogenies, Pohlig-Hellman, LLL, Quaternion RSA, CVP/HNP template), see advanced-math.md.
Table of Contents
Coppersmith's Method (Structured Primes, LACTF 2026)
Pattern (six-seven-again): p = base + 10^k · x where base is fully known, x is small.
Condition: x < N^{1/e} for degree-e polynomial (≈ N^0.25 for linear).
Attack:
R.<x> = PolynomialRing(Zmod(N))
inv_10k = inverse_mod(10^k, N)
f = x + (base * inv_10k) % N
roots = f.small_roots(X=2^70, beta=0.5)
if roots:
x_val = int(roots[0])
p = base + 10^k * x_val
q = N // p
Key details:
- Polynomial MUST be monic (leading coefficient 1)
beta=0.5 means we're looking for a factor ≥ N^0.5X parameter is upper bound on root size- Works for any "partially known prime" pattern
Clock Group (x^2+y^2=1 mod p) DLP (LACTF 2026)
Pattern (the-clock): Diffie-Hellman on the unit circle group.
Group structure:
def clock_mul(P, Q, p):
x1, y1 = P
x2, y2 = Q
return ((x1*y2 + y1*x2) % p, (y1*y2 - x1*x2) % p)
def clock_pow(P, n, p):
result = (0, 1)
base = P
while n > 0:
if n & 1:
result = clock_mul(result, base, p)
base = clock_mul(base, base, p)
n >>= 1
return result
Recovering hidden prime p:
from math import gcd
vals = [x**2 + y**2 - 1 for x, y in known_points]
p = reduce(gcd, vals)
Pohlig-Hellman when p+1 is smooth:
order = p + 1
factors = factor(order)
CRITICAL: The order is p+1, isomorphic to norm-1 elements of GF(p²)*. This is different from multiplicative group (order p-1) and elliptic curves (order ≈ p).
Non-Permutation S-box Collision Attack (Nullcon 2026)
Detection: Check if S-box is a permutation:
sbox = [...]
if len(set(sbox)) < 256:
from collections import Counter
counts = Counter(sbox)
for val, cnt in counts.items():
if cnt > 1:
colliders = [i for i in range(256) if sbox[i] == val]
delta = colliders[0] ^ colliders[1]
print(f"S[{hex(colliders[0])}] = S[{hex(colliders[1])}] = {hex(val)}, delta = {hex(delta)}")
Attack: For each key byte position k (0-15):
- Try all 256 values v: encrypt two plaintexts differing by
delta at position k
- When
ct1 == ct2: S-box input at position k was in the collision set {c0, c1}
- Deduce:
key[k] = v ^ round_const OR key[k] = v ^ round_const ^ delta
- 2-way ambiguity per byte -> 2^16 = 65,536 candidates, brute-force locally
Total oracle queries: 16 x 256 + 1 = 4,097 (reference ciphertext + probes).
Key lessons:
- SAT/SMT solvers time out on 15+ rounds of symbolic AES even with simplified S-box
- Integral/square attacks fail because non-permutation S-box breaks balance property
- Always check S-box for non-permutation FIRST before attempting complex cryptanalysis
Polynomial CRT in GF(2)[x] (Nullcon 2026)
Pattern: Server gives r = flag mod f where f is a random polynomial over GF(2).
Attack: Chinese Remainder Theorem in polynomial ring GF(2)[x]:
- Collect ~20 pairs
(r_i, f_i) from server (each f_i is ~32-bit random polynomial)
- Filter for coprime pairs using polynomial GCD
- Apply CRT to combine:
flag = r_i (mod f_i) for all i
- With ~13-20 coprime 32-bit moduli (>= 400 bits combined), flag is unique
def poly_crt(remainders, moduli):
"""CRT in GF(2)[x]: combine (r_i, f_i) pairs."""
result, mod = remainders[0], moduli[0]
for i in range(1, len(remainders)):
g, s, t = poly_xgcd(mod, moduli[i])
combined_mod = poly_mul(mod, moduli[i])
result = poly_add(poly_mul(poly_mul(remainders[i], s), mod),
poly_mul(poly_mul(result, t), moduli[i]))
result = poly_mod(result, combined_mod)
mod = combined_mod
return result, mod
Manger's RSA Padding Oracle Attack (Nullcon 2026)
Setup:
- Key
k < 2^64 (small), RSA modulus n is large (1337+ bits)
- Oracle: "invalid padding" =
decrypt < threshold, "error" = decrypt >= threshold
- No modular wrap-around because
k << n
Attack (simplified Manger's):
f1 = 1
while oracle(encrypt(f1)) == "below":
f1 *= 2
lo, hi = 0, threshold
while lo < hi:
mid = (lo + hi) // 2
f_test = ceil(threshold, mid + 1)
if oracle(encrypt(f_test)) == "above":
hi = mid
else:
lo = mid + 1
key = lo
Total queries: ~128 (64 for phase 1 + 64 for phase 2).
LWE Lattice Attack via CVP (EHAX 2026)
Pattern (Dream Labyrinth): Multi-layer challenge ending with Learning With Errors (LWE) recovery. Secret vector s in {-1, 0, 1}^n, public matrix A, ciphertext b = A*s + e (mod q).
LWE solving with fpylll (CVP/Babai):
from fpylll import IntegerMatrix, LLL, CVP
import numpy as np
q = 3329
n = 256
m = 512
def solve_lwe_cvp(A, b, q, n, m):
dim = m + n
B = IntegerMatrix(dim, dim)
for i in range(m):
B[i, i] = q
for j in range(n):
for i in range(m):
B[m + j, i] = int(A[i][j])
B[m + j, m + j] = 1
LLL.reduction(B)
target = [int(b[i]) for i in range(m)] + [0] * n
closest = CVP.babai(B, target)
s_candidate = [closest[m + j] for j in range(n)]
s = []
for val in s_candidate:
val_mod = val % q
if val_mod == 0:
s.append(0)
elif val_mod == 1:
s.append(1)
elif val_mod == q - 1:
s.append(-1)
else:
s.append(min([-1, 0, 1], key=lambda t: abs((val_mod - t) % q)))
return s
s = solve_lwe_cvp(A, b, q, n, m)
CRITICAL: Endianness gotcha. Server may describe data as "big-endian" but actually use little-endian (or vice versa). If CVP produces garbage, try swapping byte order of the secret interpretation:
s_bytes_le = bytes([(v % 256) for v in s])
s_bytes_be = s_bytes_le[::-1]
Key derivation after LWE recovery (common pattern):
import hashlib
from Cryptodome.Cipher import AES
s_bytes = bytes([(v % 256) for v in s])
session_nonce = bytes(a ^ b for a, b in
zip(wrapped_nonce, hashlib.sha256(s_bytes).digest()[:16]))
aes_key = hashlib.sha256(s_bytes + session_nonce).digest()
cipher = AES.new(aes_key, AES.MODE_GCM, nonce=aes_nonce)
plaintext = cipher.decrypt_and_verify(ciphertext, tag)
Layer patterns in multi-stage crypto challenges:
- Layer 1 (Geometry): Reconstruct point positions from noisy distance measurements. Use least-squares or trilateration with multiple models. Compute convex hull of recovered points.
- Layer 2 (Subspace): Find hidden low-dimensional subspace in high-dimensional data. Self-dot products of candidate vectors identify correct answers (smallest self-dot products = closest to subspace).
- Layer 3 (LWE): Recover secret vector from lattice problem. Use CVP with fpylll, project result to expected domain (ternary, binary, etc.).
References: EHAX CTF 2026 "Dream Labyrinth". Related: Kyber/CRYSTALS lattice cryptography.
Affine Cipher over Non-Prime Modulus (Nullcon 2026)
Pattern: c = A @ p + b (mod m) where A is nxn matrix, m may not be prime (e.g., 65).
Chosen-plaintext attack:
- Send n+1 crafted inputs to get n+1 ciphertext blocks
- Difference attack:
c_i - c_0 = A @ (p_i - p_0) (mod m)
- Build difference matrices D (plaintext) and E (ciphertext)
- Solve:
A = E @ D^{-1} (mod m) using Gauss-Jordan with GCD invertibility checks
- Recover:
b = c_0 - A @ p_0 (mod m)
CRT approach for composite modulus (preferred):
def crt2(r1, m1, r2, m2):
"""CRT: x = r1 (mod m1) and x = r2 (mod m2)"""
m1_inv = pow(m1, m2 - 2, m2)
t = ((r2 - r1) * m1_inv) % m2
return (r1 + m1 * t) % (m1 * m2)
def gauss_elim(A, b, mod):
"""Gaussian elimination over Z/modZ. A=matrix, b=vector, returns solution x."""
n = len(b)
M = [list(A[i]) + [b[i]] for i in range(n)]
for col in range(n):
pivot = next((r for r in range(col, n) if M[r][col] % mod), None)
if pivot is None: continue
M[col], M[pivot] = M[pivot], M[col]
inv = pow(M[col][col], -1, mod)
M[col] = [x * inv % mod for x in M[col]]
for r in range(n):
if r != col and M[r][col] % mod:
f = M[r][col]
M[r] = [(M[r][j] - f * M[col][j]) % mod for j in range(n + 1)]
return [M[i][n] % mod for i in range(n)]
A5, b5 = A % 5, rhs % 5
A13, b13 = A % 13, rhs % 13
x5 = gauss_elim(A5, b5, mod=5)
x13 = gauss_elim(A13, b13, mod=13)
x = [crt2(x5[i], 5, x13[i], 13) for i in range(len(x5))]
CSIDH Isogeny Power-Trace Side-Channel (404CTF 2024 "Sea Side Channel")
Target: CSIDH (Commutative Supersingular Isogeny Diffie-Hellman) — post-quantum key exchange where secret is a small integer vector e = (e_1, ..., e_n) with each e_i in a small range (e.g. [-5, 5]).
Practical trick 1 — brute force the shared secret space:
CSIDH's shared-secret keyspace is frequently tiny (≤ 419 distinct values for the 404CTF instance). Iterate all candidates, validate each against a known-plaintext AES oracle (if the shared secret feeds KDF → AES-GCM, ≤ 419 trial decryptions suffice). No isogeny computation needed.
Practical trick 2 — Velu isogeny degree leaks via loop count:
For each prime l_i, the Velu formula applies l_i point operations. Degree-3/5/7 isogenies produce distinctly sized power traces:
- degree 3 (
l=3) → ~1940 frames
- degree 5 → ~3700 frames
- degree 7 → ~5440 frames
Count frames per isogeny step → directly read off |e_i| (sign decided later).
Practical trick 3 — bypass constant-time padding via waveform shape:
A "constant time" implementation pads each step to 7 operations so the duration no longer leaks l_i. Bypass it by looking at the morphology of the trace (shape of P+1/4 pattern), not its length. Groups the 7-op step into A/B/C signatures:
import numpy as np
def shape_features(trace, w=100):
k = np.lib.stride_tricks.sliding_window_view(trace, w)
return np.stack([k.min(-1), k.max(-1), k.mean(-1)], axis=-1)
Then pattern-match each step against reference A/B/C waveforms.
Key lesson for CTFs: when a crypto chall gives you power/EM/timing traces, first try duration analysis (loop counts). If that's padded, escalate to waveform shape — padding doesn't fix shape.
Source: mathishammel.com/blog/writeup-404ctf-seaside.
Hill-Cipher / Classical Modulus Off-by-One (source: Midnightflag 2025)
Trigger: Hill cipher (or any classical encoding) where the alphabet is printable-ASCII range 33–126 (94 chars) but the code uses modulus 94 — while the actual keyspace requires 93 (or vice versa).
Signals: challenge script with mod = 94 on printable ASCII; small key-permutation space (≤ 6 orderings).
Mechanic: brute-force the key-permutation space AND sweep modulus ∈ {N−2, N−1, N}. Correct modulus gives readable plaintext; off-by-one gives garbled output. Pattern: any classical cipher using a printable-ASCII-sized modulus → try N−1 and N−2.
MD5 + SHA1 Dual-Suffix Joux Multicollision Cascade (source: FCSC 2025 Fun With Hash)
Trigger: server requires md5(p) and sha1(p) to both end with a fixed 3-byte suffix (e.g. FC 5C 25); payload must also embed a time-limited sha256(ts).
Signals: dual-hash suffix constraint, Merkle-Damgård hashes only (no BLAKE/KangarooTwelve), short handshake time.
Mechanic: Joux multicollision on MD5 — find k = 24 pairs of colliding blocks → 2^24 MD5-equivalent payloads at cost 24·2^64 / 2^32 = 2^56 work (trivial with dedicated differential tool). Constrain blocks so the 3-byte MD5 suffix already holds, then enumerate the 2^24 free payloads until one also matches the SHA1 3-byte suffix. P ≈ 2^24 · 2^−24 ≈ 63 % success. Tool: hashclash (Marc Stevens) with custom target bytes.
GEA-1 / GEA-2 LFSR Rank-Deficient Key Recovery (source: FCSC 2025 Make GEA Great Again)
Trigger: GPRS cipher GEA-1 or GEA-2; three/four LFSRs with weak key-setup (intentional rank deficiency in init reducing effective keyspace to ~40 bits); known plaintext prefix.
Signals: keystream length multiple of 8 bits; challenge explicitly references GEA/GPRS; short session key (64 bits).
Mechanic: use Beierle et al. (2021) — recover GEA-1 session key via 40-bit meet-in-the-middle on the rank-deficient register initialization. For GEA-2, use the algebraic attack (linearisation over F_2). Generic takeaway: any LFSR-based telephony cipher (GEA, A5/1, A5/2) → check for register-init "coincidence".
dream_multiply Digit-Concatenation Diophantine (source: SekaiCTF 2025 I Dream of Genni)
Trigger: custom binary op f(x,y) = int(str(x) + str(y)) or digit-shifting variant; service asks for (x, y) satisfying both f(x, y) == T and x * y == T'.
Signals: user-provided constraint involving str(x) + str(y), str(x).lstrip('0'), or base-10 digit concatenation.
Mechanic: branch-and-prune over digit positions. f(x, y) = x · 10^len(y) + y, so the constraint becomes x · 10^k + y = T with y < 10^k. For each candidate k ∈ [1, 10], solve y = T − x · 10^k, check x · y == T' → small search space. Z3 or plain backtracking in a few seconds.
CTF Crypto - Advanced Mathematical Attacks
Table of Contents
For 2024-2026 era techniques (LACTF / Nullcon / EHAX / 404CTF / FCSC / SekaiCTF / Midnightflag), see advanced-math-2.md.
Elliptic Curve Isogenies
Isogeny-based crypto challenges are often graph traversal problems in disguise:
Key concepts:
- j-invariant uniquely identifies curve isomorphism class
- Curves connected by isogenies form a graph (often tree-like)
- Degree-2 isogenies: each node has ~3 neighbors (2 children + 1 parent)
Modular polynomial approach:
- Connected j-invariants j₁, j₂ satisfy Φ₂(j₁, j₂) = 0
- Find neighbors by computing roots of Φ₂(j, Y) in the finite field
- Much faster than computing actual isogenies
Pathfinding in isogeny graphs:
def estimate_height(j, neighbors_func, trials=100):
min_depth = float('inf')
for _ in range(trials):
depth, curr = 0, j
while True:
nbrs = neighbors_func(curr)
if len(nbrs) <= 1:
break
curr = random.choice(nbrs)
depth += 1
min_depth = min(min_depth, depth)
return min_depth
def find_path(start, end):
Complex multiplication (CM) curves:
- Discriminant D = f² · D_K where D_K is fundamental discriminant
- Conductor f determines tree depth
- Look for special discriminants: -163, -67, -43, etc. (class number 1)
Pohlig-Hellman Attack (Weak ECC)
For elliptic curves with smooth order (many small prime factors):
from sage.all import *
E = EllipticCurve(GF(p), [a, b])
n = E.order()
factors = factor(n)
partial_logs = []
for (prime, exp) in factors:
cofactor = n // (prime ** exp)
G_sub = cofactor * G
P_sub = cofactor * P
d_sub = discrete_log(P_sub, G_sub, ord=prime**exp)
partial_logs.append((d_sub, prime**exp))
from sympy.ntheory.modular import crt
moduli = [m for (_, m) in partial_logs]
residues = [r for (r, _) in partial_logs]
private_key, _ = crt(moduli, residues)
LLL Algorithm for Approximate GCD
Pattern (Grinch's Cryptological Defense): Server gives hints h_i = f * p_i + n_i where f is the flag, p_i are small primes, n_i is small noise.
Lattice construction:
from sage.all import *
M = matrix(ZZ, [
[1, 0, 0, h1],
[0, 1, 0, h2],
[0, 0, 1, h3],
[0, 0, 0, -1]
])
reduced = M.LLL()
Coppersmith's Method (Close Private Keys)
Pattern (Duality of Key): Two RSA key pairs with d1 ≈ d2 (small difference).
Attack:
R.<x> = PolynomialRing(Zmod(N))
r = inverse_mod(e1*e2, N) * (e1 - e2) % N
f = r - x
roots = f.small_roots(X=2^128, beta=0.5)
Quaternion RSA
Pattern: RSA encryption using Hamilton quaternion algebra over Z/nZ. The plaintext is embedded into quaternion components that are linear combinations of m, p, q, then the quaternion matrix is raised to power e mod n.
Key structure:
a0 = m
a1 = m + α1*p + β1*q
a2 = m + α2*p + β2*q
a3 = m + α3*p + β3*q
Critical property: For quaternion q = s + v (scalar + vector), q^k = s_k + t_k*v — the vector part stays proportional under exponentiation. This means the ratios of imaginary components are preserved:
c1 : c2 : c3 = a1 : a2 : a3 (mod n)
Factoring n (the attack):
import math
c0, c1, c2, c3 = ct[0], (-ct[1]) % n, (-ct[2]) % n, (-ct[3]) % n
A = (-(α1*c1 - α2*c2)*(c1-c3) + (α1*c1 - α3*c3)*(c1-c2)) % n
B = (-(β1*c1 - β2*c2)*(c1-c3) + (β1*c1 - β3*c3)*(c1-c2)) % n
A = (-(11*c1-3*c2)*(c1-c3) + (17*c1-3*c3)*(c1-c2)) % n
B = (-(13*c1-7*c2)*(c1-c3) + (19*c1-7*c3)*(c1-c2)) % n
q_factor = math.gcd(A, n)
p_factor = math.gcd(B, n)
Decryption after factoring:
Over F_p, the quaternion algebra H_p ≅ M_2(F_p) (Wedderburn theorem), so the quaternion's multiplicative order divides p²-1. Decrypt using:
d_p = pow(e, -1, p**2 - 1)
d_q = pow(e, -1, q**2 - 1)
enc_mod_p = [[x % p for x in row] for row in enc_matrix]
enc_mod_q = [[x % q for x in row] for row in enc_matrix]
dec_p = matrix_pow(enc_mod_p, d_p, p)
dec_q = matrix_pow(enc_mod_q, d_q, q)
m = CRT(dec_p[0][0], dec_q[0][0], p, q)
flag = long_to_bytes(m)
Why it works: The "reduced dimension" is that 4D quaternion exponentiation reduces to a 2D recurrence (scalar + magnitude of vector), and the direction of the vector part is invariant. This leaks the ratio a1:a2:a3 directly from the ciphertext, enabling factorization.
References: SECCON CTF 2023 "RSA 4.0", 0xL4ugh CTF "Reduced Dimension"
Polynomial Arithmetic in GF(2)[x]
Key operations for CTF crypto:
def poly_add(a, b):
"""Addition in GF(2)[x] = XOR of coefficient integers."""
return a ^ b
def poly_mul(a, b):
"""Carry-less multiplication in GF(2)[x]."""
result = 0
while b:
if b & 1:
result ^= a
a <<= 1
b >>= 1
return result
def poly_divmod(a, b):
"""Division with remainder in GF(2)[x]."""
if b == 0:
raise ZeroDivisionError
deg_a, deg_b = a.bit_length() - 1, b.bit_length() - 1
q = 0
while deg_a >= deg_b and a:
shift = deg_a - deg_b
q ^= (1 << shift)
a ^= (b << shift)
deg_a = a.bit_length() - 1
return q, a
Applications: CRT in GF(2)[x] for recovering secrets from polynomial remainders, Reed-Solomon-like error correction.
RSA Signing Bug
Vulnerability: Using wrong exponent for signing
- Correct:
sign = m^d mod n (private exponent)
- Bug:
sign = m^e mod n (public exponent)
Exploitation:
from sympy import integer_nthroot
forged_sig, exact = integer_nthroot(message, e)
if exact:
print(f"Forged signature: {forged_sig}")
CVP for Biased-Nonce ECDSA / Truncated LCG / HNP
Pattern (Hidden Number Problem): You have many equations of the form k_i ≡ a_i * x + b_i (mod q) where k_i is an unknown nonce with some high or low bits known or biased. Goal: recover the secret x.
Applies to:
- ECDSA with partial-nonce leak (top/bottom bits known from side-channel)
- Truncated LCG (seen low/mid bits of state, each state relates linearly to seed)
- DSA with constant nonce prefix
Lattice construction (Babai's nearest plane via fpylll):
from fpylll import IntegerMatrix, CVP, LLL
n = len(a_list)
B = IntegerMatrix(n + 2, n + 2)
for i in range(n):
B[i, i] = q
B[n, n] = 1
B[n + 1, n + 1] = K
for i in range(n):
B[n, i] = a_list[i]
B[n + 1, i] = b_list[i]
B = LLL.reduction(B)
target = tuple([0] * n + [0, K])
closest = CVP.babai(B, target)
Canonical reference: rkm0959/Inequality_Solving_with_CVP — this repo is the go-to template; it reframes biased-nonce ECDSA, truncated LCG, and bounded HNP into a single inequality-solving CVP problem.
Spot the pattern: any challenge with many linear equations mod q + bounded error → CVP via lattice. Don't try to Gaussian-eliminate; the "error" is what makes LLL/Babai necessary.
CTF Crypto - Classic Ciphers
Table of Contents
Vigenere Cipher
Known Plaintext Attack (most common in CTFs):
def vigenere_decrypt(ciphertext, key):
result = []
key_index = 0
for c in ciphertext:
if c.isalpha():
shift = ord(key[key_index % len(key)].upper()) - ord('A')
base = ord('A') if c.isupper() else ord('a')
result.append(chr((ord(c) - base - shift) % 26 + base))
key_index += 1
else:
result.append(c)
return ''.join(result)
def derive_key(ciphertext, plaintext):
"""Derive key from known plaintext (e.g., flag format CCOI26{)"""
key = []
for c, p in zip(ciphertext, plaintext):
if c.isalpha() and p.isalpha():
c_val = ord(c.upper()) - ord('A')
p_val = ord(p.upper()) - ord('A')
key.append(chr((c_val - p_val) % 26 + ord('A')))
return ''.join(key)
Kasiski Examination for Key Length
When no known plaintext is available, determine the Vigenere key length using Kasiski examination: find repeated sequences in the ciphertext and compute the GCD of their distances.
from math import gcd
from functools import reduce
from collections import Counter
def kasiski_examination(ciphertext, min_seq=3):
"""Find repeating sequences and compute likely key lengths."""
ct = ''.join(c.upper() for c in ciphertext if c.isalpha())
distances = []
for seq_len in range(min_seq, 6):
seen = {}
for i in range(len(ct) - seq_len):
seq = ct[i:i+seq_len]
if seq in seen:
for prev_pos in seen[seq]:
distances.append(i - prev_pos)
seen[seq].append(i)
else:
seen[seq] = [i]
if distances:
key_len = reduce(gcd, distances)
print(f"Likely key length: {key_len}")
print(f"All distances: {sorted(set(distances))}")
return key_len
return None
def frequency_attack(ciphertext, key_length):
"""Break Vigenere by frequency analysis on each key-position group."""
ct = [c.upper() for c in ciphertext if c.isalpha()]
english_freq = [0.082,0.015,0.028,0.043,0.127,0.022,0.020,0.061,0.070,
0.002,0.008,0.040,0.024,0.067,0.075,0.019,0.001,0.060,
0.063,0.091,0.028,0.010,0.023,0.002,0.020,0.001]
key = []
for i in range(key_length):
group = [ct[j] for j in range(i, len(ct), key_length)]
best_shift, best_score = 0, -1
for shift in range(26):
decrypted = [chr((ord(c) - ord('A') - shift) % 26 + ord('A')) for c in group]
freq = Counter(decrypted)
score = sum(freq.get(chr(j+65), 0) / len(group) * english_freq[j]
for j in range(26))
if score > best_score:
best_score = score
best_shift = shift
key.append(chr(best_shift + ord('A')))
return ''.join(key)
Key insight: Repeated sequences in Vigenere ciphertext occur at distances that are multiples of the key length. The GCD of all such distances reveals the key length, after which each position becomes a simple Caesar cipher solvable by frequency analysis.
When standard keys don't work:
- Key may not repeat - could be as long as message
- Key derived from challenge theme (character names, phrases)
- Key may have "padding" - repeated letters (IICCHHAA instead of ICHA)
- Try guessing plaintext words from theme, derive full key
Atbash Cipher
Simple substitution: A<->Z, B<->Y, C<->X, etc.
def atbash(text):
return ''.join(
chr(ord('Z') - (ord(c.upper()) - ord('A'))) if c.isalpha() else c
for c in text
)
Identification: Challenge name hints ("Abashed" = Atbash), preserves spaces/punctuation, 1-to-1 substitution.
Substitution Cipher with Rotating Wheel
Pattern (Wheel of Mystery): Physical cipher wheel with inner/outer alphabets.
Automated solver: Use quipqiup.com for general substitution ciphers — it uses word pattern matching and language entropy to solve without knowing the key.
Brute force all rotations:
outer = "ABCDEFGHIJKLMNOPQRSTUVWXYZ{}"
inner = "QNFUVWLEZYXPTKMR}ABJICOSDHG{"
for rotation in range(len(outer)):
rotated = inner[rotation:] + inner[:rotation]
mapping = {outer[i]: rotated[i] for i in range(len(outer))}
decrypted = ''.join(mapping.get(c, c) for c in ciphertext)
if decrypted.startswith("METACTF{"):
print(decrypted)
XOR Variants
Multi-Byte XOR Key Recovery via Frequency Analysis
Pattern: Ciphertext XOR'd with a repeating multi-byte key. Key length unknown.
Step 1 — Determine key length: Try each candidate length, split ciphertext into groups by position modulo key length, score each group's byte frequency against English text (space = 0x20 is the most common byte).
Step 2 — Recover each key byte: For each position, brute-force all 256 byte values and select the one producing the most English-like decrypted text.
from collections import Counter
def score_english(data):
"""Score how English-like a byte sequence is."""
freq = Counter(data)
return freq.get(ord(' '), 0) + sum(freq.get(c, 0) for c in range(ord('a'), ord('z')+1))
def find_key_length(ciphertext, max_len=40):
"""Test key lengths by scoring single-byte XOR on each column."""
best_len, best_score = 1, 0
for kl in range(1, max_len + 1):
total = 0
for col in range(kl):
group = ciphertext[col::kl]
best_col_score = max(
score_english(bytes(b ^ k for b in group))
for k in range(256)
)
total += best_col_score
if total > best_score:
best_score = total
best_len = kl
return best_len
def recover_key(ciphertext, key_length):
"""Recover each key byte via frequency analysis."""
key = []
for col in range(key_length):
group = ciphertext[col::key_length]
best_k = max(range(256), key=lambda k: score_english(bytes(b ^ k for b in group)))
key.append(best_k)
return bytes(key)
ct = open('encrypted.bin', 'rb').read()
kl = find_key_length(ct)
key = recover_key(ct, kl)
print(f"Key ({kl} bytes): {key}")
print(bytes(c ^ key[i % len(key)] for i, c in enumerate(ct)))
Key insight: Multi-byte repeating XOR splits into key_length independent single-byte XOR problems. English text frequency (especially space = 0x20) reliably identifies correct key bytes. Works best with ciphertext longer than ~100 bytes.
Cascade XOR (First-Byte Brute Force)
Pattern (Shifty XOR): Each byte XORed with previous ciphertext byte.
for first_byte in range(256):
flag = [first_byte]
for i in range(1, len(ct)):
flag.append(ct[i] ^ flag[i-1])
if all(32 <= b < 127 for b in flag):
print(bytes(flag))
XOR with Rotation: Power-of-2 Bit Isolation (Pragyan 2026)
Pattern (R0tnoT13): Given S XOR ROTR(S, k) for multiple rotation offsets k, recover S.
Key insight: When ALL rotation offsets are powers of 2 (2, 4, 8, 16, 32, 64), even-indexed and odd-indexed bits NEVER mix across any frame. This reduces N-bit recovery to just 2 bits of brute force.
Algorithm:
- Express every bit of S in terms of two unknowns (s_0 for even bits, s_1 for odd bits) using the k=2 frame
- Only 4 candidate states -> try all, verify against all frames
- XOR valid state with ciphertext -> plaintext
Weak XOR Verification Brute Force (Pragyan 2026)
Pattern (Dor4_Null5): Verification XORs all comparison bytes into a single byte instead of checking each individually.
Vulnerability: Any fixed response has 1/256 probability of passing. With enough interaction budget (e.g., 4919 attempts), brute-force succeeds with ~256 expected attempts.
for attempt in range(3000):
r.sendlineafter(b"prompt: ", b"00" * 8)
result = r.recvline()
if b"successful" in result:
break
Deterministic OTP with Load-Balanced Backends (Pragyan 2026)
Pattern (DumCows): Service encrypts data with deterministic keystream that resets per connection. Multiple backends with different keystreams behind a load balancer.
Attack:
- Send known plaintext (e.g., 18 bytes of 'A'), XOR with ciphertext -> recover keystream
- XOR keystream with target ciphertext -> decrypt secret
- Backend matching: Must connect to same backend for keystream to match. Retry connections until patterns align.
def recover_keystream(known, ciphertext):
return bytes(k ^ c for k, c in zip(known, ciphertext))
def decrypt(keystream, target_ct):
return bytes(k ^ c for k, c in zip(keystream, target_ct))
Key insight: When encryption is deterministic per connection with no nonce/IV, known-plaintext attack is trivial. The challenge is matching backends.
OTP Key Reuse / Many-Time Pad XOR (BYPASS CTF 2025)
Pattern (Once More Unto the Same Wind): Two ciphertexts encrypted with the same OTP key. Known plaintext for one message enables recovery of the other.
XOR property: C1 XOR C2 = P1 XOR P2 (key cancels). When one plaintext (P1) is known, recover the other: P2 = C1 XOR C2 XOR P1.
from pwn import xor
c1 = bytes.fromhex("7713283f5e9979...")
c2 = bytes.fromhex("740b393f4c8b67...")
known_plaintext = b"A" * len(c1)
flag = xor(xor(c1, c2), known_plaintext)
print(flag)
When plaintext is unknown — crib dragging:
def crib_drag(c1, c2, crib, max_pos=None):
"""Slide known word across XOR of two ciphertexts."""
xored = xor(c1[:min(len(c1), len(c2))], c2[:min(len(c1), len(c2))])
for pos in range(len(xored) - len(crib)):
candidate = xor(xored[pos:pos+len(crib)], crib)
if all(32 <= b < 127 for b in candidate):
print(f"pos {pos}: {candidate}")
Key insight: OTP (One-Time Pad) XOR encryption is only secure when the key is truly one-time. Reusing the key on two messages leaks P1 XOR P2 — exploit with known plaintext or crib dragging.
Book Cipher
Pattern (Booking Key, Nullcon 2026): Book cipher with "steps forward" encoding. Brute-force starting position with charset filtering reduces ~56k candidates to 3-4.
See historical.md for full implementation.
Variable-Length Homophonic Substitution (ASIS CTF Finals 2013)
Pattern (Rookie Agent): Ciphertext uses alphanumeric characters grouped in blocks of 5. Single-character frequency analysis shows non-uniform distribution. N-gram analysis reveals repeated multi-character groups mapping to single plaintext characters, with different plaintext characters encoded by groups of different lengths (1-4 characters).
Analysis workflow:
- Collapse whitespace and compute n-gram frequencies (1 through 6):
from collections import Counter
ct = "6di16ovhtmnzslsxqcjo8fkdmtyrbn..."
for n in range(1, 7):
ngrams = [ct[i:i+n] for i in range(len(ct)-n+1)]
freq = Counter(ngrams).most_common(20)
print(f"{n}-grams: {freq[:10]}")
- Identify constant-frequency groups — if
8f, fk, and kd each appear exactly 36 times, check whether 8fkd also appears 36 times. If so, it is a single substitution unit:
substitutions = {
'8fkd': 'E', '4bg9': 'I', 'lsxq': 'A', 'fmrk': 'B',
'9gle': 'C', 'mtyr': 'D', 'cjo': 'F', 'htm': 'G',
}
reduced = ct
for pattern, symbol in sorted(substitutions.items(), key=lambda x: -len(x[0])):
reduced = reduced.replace(pattern, symbol)
-
The reduced text is now a monoalphabetic substitution — solve with quipqiup.com or statistical analysis on English.
-
When some characters remain ambiguous after decryption, brute-force permutations against a known hash of the flag:
from itertools import permutations
from hashlib import sha256
partial_flag = '3c6a1c371b381c943065864b95ae5546'
ambiguous_chars = '12456789x'
known_hash = '9f2a579716af14400c9ba1de8682ca52c17b3ed4235ea17ac12ae78ca24876ef'
for p in permutations(ambiguous_chars):
mapping = dict(zip(ambiguous_chars, p))
candidate = ''.join(mapping.get(c, c) for c in partial_flag)
if sha256(('ASIS_' + candidate).encode()).hexdigest() == known_hash:
print(f"Flag: ASIS_{candidate}")
break
Key insight: Variable-length homophonic substitution hides letter frequencies by mapping common plaintext letters to longer codegroups. The attack reverses this: find n-grams that always appear as a unit (identical frequency for all sub-n-grams), replace them with single symbols, then solve the resulting monoalphabetic substitution. When the flag format provides a hash for verification, brute-force remaining ambiguous character permutations offline.
CTF Crypto - Elliptic Curve Attacks
Table of Contents
Small Subgroup Attacks
- Check curve order for small factors
- Pohlig-Hellman: solve DLP in small subgroups, combine with CRT
E = EllipticCurve(GF(p), [a, b])
G = E.gens()[0]
order = E.order()
Invalid Curve Attacks
If point validation is missing, send points on weaker curves. Craft points with small-order subgroups to leak secret key bits.
Singular Curves
If discriminant delta = 0, curve is singular. DLP becomes easy (maps to additive/multiplicative group).
Smart's Attack (Anomalous Curves)
When to use: Curve order equals field characteristic p (anomalous curve). Solves ECDLP in O(1) via p-adic lifting.
Detection: E.order() == p — always check this first!
SageMath (automatic):
E = EllipticCurve(GF(p), [a, b])
G = E(Gx, Gy)
Q = E(Qx, Qy)
secret = G.discrete_log(Q)
Manual p-adic lift (when Sage's auto method fails):
def smart_attack(p, a, b, G, Q):
E = EllipticCurve(GF(p), [a, b])
Qp = pAdicField(p, 2)
Ep = EllipticCurve(Qp, [a, b])
Gp = Ep.lift_x(ZZ(G[0]), all=True)
Qp_point = Ep.lift_x(ZZ(Q[0]), all=True)
for gp in Gp:
for qp in Qp_point:
try:
pG = p * gp
pQ = p * qp
x_G = ZZ(pG[0] / pG[1]) / p
x_Q = ZZ(pQ[0] / pQ[1]) / p
secret = ZZ(x_Q / x_G) % p
if E(G) * secret == E(Q):
return secret
except (ZeroDivisionError, ValueError):
continue
return None
Multi-layer decryption after key recovery: Challenge may wrap flag in AES-CBC + DES-CBC or similar — just busywork once the ECC key is recovered. Derive keys with SHA-256 of shared secret.
ECC Fault Injection
Pattern (Faulty Curves): Bit flip during ECC computation reveals private key bits.
Attack: Compare correct vs faulty ciphertext, recover key bit-by-bit:
Clock Group DLP via Pohlig-Hellman (LACTF 2026)
Pattern (the-clock): Diffie-Hellman on unit circle group: x^2 + y^2 = 1 (mod p).
Key facts:
- Group law: (x1,y1) * (x2,y2) = (x1y2 + y1x2, y1y2 - x1x2)
- Group order = p + 1 (not p - 1!)
- Isomorphic to GF(p^2)* elements of norm 1
Group operations:
def clock_mul(P, Q, p):
x1, y1 = P
x2, y2 = Q
return ((x1*y2 + y1*x2) % p, (y1*y2 - x1*x2) % p)
def clock_pow(P, n, p):
result = (0, 1)
base = P
while n > 0:
if n & 1:
result = clock_mul(result, base, p)
base = clock_mul(base, base, p)
n >>= 1
return result
Recovering hidden prime p:
from math import gcd
vals = [x**2 + y**2 - 1 for x, y in known_points]
p = reduce(gcd, vals)
Attack when p+1 is smooth:
Identification: Challenge mentions "clock", "circle", or gives points satisfying x^2+y^2=1. Always check if p+1 (not p-1) is smooth.
Ed25519 Torsion Side Channel (BearCatCTF 2026)
Pattern (Curvy Wurvy): Ed25519 signing oracle derives per-user keys as user_key = MASTER_KEY * uid mod l (where l is the Ed25519 subgroup order). Goal: recover MASTER_KEY from oracle queries.
The attack exploits Ed25519's cofactor h=8:
- Full curve order =
8*l, but scalars are reduced mod l
- When
MASTER_KEY * 2^t wraps around l, multiplication produces a torsion component visible as y-coordinate change
Key extraction via binary decomposition:
bits = []
for t in range(255):
S_t = query_sign(3, 2**t)
S_t1 = query_sign(3, 2**(t+1))
doubled = point_double(S_t)
bits.append(0 if doubled.y == S_t1.y else 1)
Key insight: Ed25519's cofactor creates an observable side channel: when scalar multiplication wraps around the subgroup order l, the result shifts by a torsion element (one of 8 points). By querying powers of 2 and checking y-coordinate consistency, each bit of the secret scalar is leaked. Libraries like ecpy that reduce mod l are vulnerable to this when used in multi-user key derivation schemes.
Detection: Ed25519 signing oracle with user-controlled UID or multiplier. Key derivation formula key = master * uid mod l.
ECDSA Nonce Reuse (BearCatCTF 2026)
Pattern (Chatroom): ECDSA signatures on secp256k1 with constant nonce k. When two signatures share the same r value, the nonce and private key are recoverable.
Recovery:
from hashlib import sha256
h1 = int(sha256(msg1).hexdigest(), 16)
h2 = int(sha256(msg2).hexdigest(), 16)
n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
k = ((h1 - h2) * pow(s1 - s2, -1, n)) % n
d = ((s1 * k - h1) * pow(r, -1, n)) % n
Key insight: Same r value across multiple ECDSA signatures means the nonce k was reused. This is the same class of bug that compromised the PlayStation 3 signing key. Always check for repeated r values in signature datasets.
Detection: Multiple ECDSA signatures with identical r component. Challenge mentions "nonce", "deterministic signing", or provides a signing oracle.
Obfuscated Genus-1 Variety → Weierstrass + Hybrid BSGS/MOV/NFS (source: hxp 39C3 AlcoholicVariety)
Trigger: DLP-style challenge on a 10-coordinate projective embedding with degree-2 relations between pairs; group order factors into a small (~31-bit) prime and a medium (~63-bit) prime.
Signals: .sage challenge with coordinates (x0..x9) and constraint polynomials of total degree 2; group order with two clean prime factors of disparate size.
Mechanic: interpolate low-degree polynomials between coord pairs — variety is genus 1 in disguise; convert to Weierstrass form in Magma (jInvariant, EllipticCurveFromjInvariant). Split ECDLP via CRT: BSGS on the small factor, MOV (Weil pairing to GF(p)) + cado-nfs NFS on the large. Recovers the scalar that 10-dim coords hide.
Source: affine.group/writeup/2024-12-hxp-AlcoholicVariety.
Invalid-Point on py_ecc / Jacobian Point Without Curve Check (source: SekaiCTF 2025 Law and Order)
Trigger: homemade elliptic-curve class (py_ecc-style) with add/double in Jacobian coordinates but no on-curve check on inputs.
Signals: class Point: def __add__(self, other): ... with only field arithmetic, no self.curve.is_on_curve(self) assertion before use; SECP/ED25519-like constants.
Mechanic: submit points from a different curve whose order has small factors; Pohlig-Hellman on the small-order subgroup leaks the secret modulo ℓ. Aggregate via CRT. Works because Jacobian add/double only checks algebraic relations, not curve membership.
CTF Crypto - Exotic Algebraic Structures
Table of Contents
Braid Group DH — Alexander Polynomial Multiplicativity (DiceCTF 2026)
Pattern (Plane or Exchange): Diffie-Hellman key exchange built over mathematical braids. Public keys are derived by connecting a private braid to public info, then scrambled with Reidemeister-like moves. Shared secret = sha256(normalize(calculate(connect(my_priv, their_pub)))). The calculate() function computes the Alexander polynomial of the braid.
Protocol structure:
import sympy as sp
import hashlib
t = sp.Symbol('t')
def compose(p1, p2):
return [p1[p2[i]] for i in range(len(p1))]
def inverse(p):
inv = [0] * len(p)
for i, j in enumerate(p):
inv[j] = i
return inv
def connect(g1, g2):
"""Concatenate two braids with a swap at the junction."""
x1, o1 = g1
x2, o2 = g2
l = len(x1)
new_x = list(x1) + [v + l for v in x2]
new_o = list(o1) + [v + l for v in o2]
new_x[l-1], new_x[l] = new_x[l], new_x[l-1]
return (new_x, new_o)
def sweep(ap):
"""Compute winding number matrix from arc presentation."""
l = len(ap)
current_row = [0] * l
matrix = []
for pair in ap:
c1, c2 = sorted(pair)
diff = pair[1] - pair[0]
s = 1 if diff > 0 else (-1 if diff < 0 else 0)
for c in range(c1, c2):
current_row[c] += s
matrix.append(list(current_row))
return matrix
def mine(point):
x, o = point
return sweep([*zip(x, o)])
def calculate(point):
"""Compute Alexander polynomial from braid."""
mat = sp.Matrix([[t**(-x) for x in y] for y in mine(point)])
return mat.det(method='bareiss') * (1 - t)**(1 - len(point[0]))
def normalize(calculation):
"""Convert Laurent polynomial to standard form."""
poly = sp.expand(sp.simplify(calculation))
all_exp = [term.as_coeff_exponent(t)[1] for term in poly.as_ordered_terms()]
min_exp = min(all_exp)
poly = sp.expand(sp.simplify(poly * t**(-min_exp)))
if poly.coeff(t, 0) < 0:
poly *= -1
return poly
The fatal vulnerability — Alexander polynomial multiplicativity:
The Alexander polynomial satisfies Δ(β₁·β₂) = Δ(β₁) × Δ(β₂) under braid concatenation. This makes the scheme abelian:
calc_pub = normalize(calculate(pub_info))
calc_alice = normalize(calculate(alice_pub))
calc_bob = normalize(calculate(bob_pub))
calc_alice_priv = sp.cancel(calc_alice / calc_pub)
shared_poly = normalize(sp.expand(calc_alice_priv * calc_bob))
shared_hex = hashlib.sha256(str(shared_poly).encode()).hexdigest()
key = bytes.fromhex(shared_hex)
while len(key) < len(ciphertext):
key += hashlib.sha256(key).digest()
plaintext = bytes(a ^ b for a, b in zip(ciphertext, key))
Computational trick for large matrices:
Direct sympy Bareiss on rational-function matrices (e.g., 30×30 with entries t^(-w)) is extremely slow. Clear denominators first:
k = max(abs(w) for row in winding_matrix for w in row)
n = len(winding_matrix)
mat_poly = sp.Matrix([[t**(k - w) for w in row] for row in winding_matrix])
det_scaled = mat_poly.det(method='bareiss')
det_true = sp.cancel(det_scaled / t**(k * n))
result = sp.cancel(det_true * (1 - t)**(1 - n))
Validation — palindromic property:
All valid Alexander polynomials are palindromic (coefficients read the same forwards and backwards). Use this as a sanity check on intermediate results:
def is_palindromic(poly, var=t):
coeffs = sp.Poly(poly, var).all_coeffs()
return coeffs == coeffs[::-1]
When to recognize: Challenge mentions braids, knots, permutation pairs, winding numbers, Reidemeister moves, or "topological key exchange." The key mathematical insight is that the Alexander polynomial — while a powerful knot/braid invariant — is multiplicative, making it fundamentally unsuitable as a one-way function for Diffie-Hellman.
Key lessons:
- Diffie-Hellman requires non-abelian hardness. If the invariant used for the shared secret is multiplicative/commutative under the group operation, Eve can compute it from public values.
- Scrambling (Reidemeister moves) doesn't help — the Alexander polynomial is an invariant, so scrambled braids produce the same polynomial.
- Large symbolic determinants need the denominator-clearing trick: multiply by
t^k to get polynomials, compute det, divide back.
References: DiceCTF 2026 "Plane or Exchange"
Monotone Function Inversion with Partial Output
Pattern: A flag is converted to a real number, pushed through an invertible/monotone function (e.g., iterated map, spiral), then some output digits are masked/erased. Recover the masked digits to invert and get the flag.
Identification:
- Output is a high-precision decimal number with some digits replaced by
?
- The transformation is smooth/monotone (invertible via root-finding)
- Flag format constrains the input to a narrow range
- Challenge hints like "brute won't cut it" or "binary search"
Key insight: For a monotone function f, knowing the flag format (e.g., 0xL4ugh{...}) constrains the output to a tiny interval. Many "unknown" output digits are actually fixed across all valid inputs and can be determined immediately.
Attack: Hierarchical Digit Recovery
-
Determine fixed digits: Compute f(flag_min) and f(flag_max) for all valid flags. Digits that are identical in both outputs are fixed regardless of flag content.
-
Sequential refinement: Determine remaining unknown digits one at a time (largest contribution first). For each candidate value (0-9), invert f and check if the result is a valid flag (ASCII, correct format).
-
Validation: The correct digit produces readable ASCII text; wrong digits produce garbage bytes in the flag.
import mpmath
mpmath.mp.prec = 256
phi = (mpmath.mpf(1) + mpmath.sqrt(mpmath.mpf(5))) / 2
def forward(x0):
"""The challenge's transformation (e.g., iterated spiral)."""
x = x0
for i in range(iterations):
r = mpmath.mpf(i) / mpmath.mpf(iterations)
x = r * mpmath.sqrt(x*x + 1) + (1 - r) * (x + phi)
return x
def invert(y_target, x_guess):
"""Invert via root-finding (Newton's method)."""
def f(x0):
return forward(x0) - y_target
return mpmath.findroot(f, x_guess, tol=mpmath.mpf(10)**(-200))
masked = "?7086013?3756162?51694057..."
unknown_positions = [0, 8, 16, 25, 33, ...]
for pos in remaining_unknowns:
for digit in range(10):
output_val = construct_number(known_digits | {pos: digit})
x_inv = invert(output_val, x_guess=0.335)
flag_int = int(x_inv * mpmath.power(10, flag_digits))
flag_bytes = flag_int.to_bytes(30, 'big')
if is_valid_flag(flag_bytes):
known_digits[pos] = digit
break
Why it works: Each unknown digit affects a different decimal scale in the output number. The largest unknown (earliest position) shifts the inverted value by the most, determining several bytes of the flag. Fixing it and moving to the next unknown reveals more bytes. Total work: 10 * num_unknowns inversions (linear, not exponential).
Precision matching: SageMath's RealField(N) uses MPFR with N-bit mantissa. In mpmath, set mp.prec = N (NOT mp.dps). The last few output digits are precision-sensitive and will only match with the correct binary precision.
Derivative analysis: For the spiral-type map x → r*sqrt(x²+1) + (1-r)*(x+φ), the per-step derivative is r*x/sqrt(x²+1) + (1-r) ≈ 1, so the total derivative stays near 1 across all 81 iterations. This means precision is preserved through inversion — 67 known output digits give ~67 digits of input precision.
References: 0xL4ugh CTF "SpiralFloats"
Tropical Semiring Residuation Attack (BearCatCTF 2026)
Pattern (Tropped): Diffie-Hellman key exchange using tropical matrices (min-plus algebra). Per-character shared secret XOR'd with encrypted flag.
Tropical algebra:
- Addition =
min(a, b)
- Multiplication =
a + b
- Matrix multiply:
(A*B)[i,j] = min_k(A[i,k] + B[k,j])
Tropical residuation recovers shared secret from public data:
def tropical_residuate(M, Mb, aM, n):
"""Recover shared secret from public matrices.
M = public matrix, Mb = M*b (Bob's public), aM = a*M (Alice's public)
"""
b_star = [max(Mb[i] - M[i][j] for i in range(n)) for j in range(n)]
aMb = min(aM[j] + b_star[j] for j in range(n))
return aMb
for i, enc_char in enumerate(encrypted):
key = shared_secret % 32
plaintext_char = chr(key ^ ord(enc_char))
Key insight: Tropical DH is broken because the min-plus semiring lacks cancellation — given M and M*b, the "residual" b* can be computed directly via max(Mb[i] - M[i][j]). Unlike standard DH where recovering b from g^b is hard, tropical residuation recovers enough of b's effect to compute the shared secret. This makes tropical matrix DH insecure for any matrix size.
Detection: Challenge mentions "tropical", "min-plus", "exotic algebra", or defines custom matrix multiplication using min and +.
ePrint-Scheme-Killer Linear-Algebra (source: hxp 39C3 Linear-algebra-vs-ePrint)
Trigger: challenge quotes an obscure ePrint paper (2019/717, 2024/792, 2025/007 …) introducing "homomorphism learning", "entropic operator", or "Stickel variation"; scheme advertises post-DLP security.
Signals: references to homomorphism_learning.pdf, bilinear "mixing" functions, claimed reduction to a non-standard assumption.
Mechanic: construct an auxiliary homomorphism π with ker(π) ∩ ker(ψ) = {0}; solve a linear system over the generators to recover the message without ever doing DLP. For bilinear-mix schemes: exploit separability,
mix((a,b),(u,v)) = mix((a,b),(c,d)) · mix((1,1),(u,v)) / mix((1,1),(c,d))
which collapses the DH assumption. Generic recipe: always verify that the scheme genuinely needs its stated hard problem — linear-algebra often bypasses it.
CSIDH / Group-Action KEM Sign-Leak Oracle (source: SekaiCTF 2025 Alter Ego)
Trigger: isogeny-based KEM exposing group_action(e, x) for attacker-controlled x ∈ {±1}; exponent vector e ∈ ℤ^n.
Signals: CSIDH/CSURF code, ideal_to_isogeny, exponent vector stored plainly.
Mechanic: feeding -1 reduces primes in e's factorisation depending on the sign of each coordinate. Observe which primes disappear ⇒ infer sign bits of e one by one ⇒ find the negative counterpart that still validates. Key recovery in O(n) oracle calls.
FCSC 2025 Post-Quantum: Kzber (Kyber) + UOV "Vinegar" (source: hackropole.fr)
Trigger: challenge files with Kyber parameters (n=256, q=3329, module rank 2/3/4) or UOV oil/vinegar split; filenames pk, sk, ct.
Signals: polyvec.h5/ciphertext.bin + README citing NIST PQC round; or vinegar variables with explicit rank.
Mechanic: Kyber path — decapsulation-failure oracle (Ravi et al.) or implicit-rejection timing. UOV path — rank analysis / MinRank over the central map; typically reduces recovery cost to O(q^r) with small r. Run Magma MinRank or Sage HFE helper.
Source: hackropole.fr/fr/fcsc2025/.
Falcon Floating-Point Leakage on Sign Verification (source: 2025-era PQ CTFs, CCS 2024 Falcon papers)
Trigger: Falcon-512 / Falcon-1024 signing or signature verification reachable; reference implementation uses double / fpu math; verifier bounds use sqrt(norm2) < β.
Signals: falcon-ref.c compiled with -lm; signature pairs (r, s) emitted with varying r; check code calls vrfy_norm2 or manipulates int64_t from double.
Mechanic: the Falcon fast FP Gaussian sampler leaks via FP-rounding subnormals. Collect ~10^5 signatures; recover the signing key's secret lattice basis via f, g, F, G relations + Howgrave-Graham/learning-with-rounding CVP. Alternate path: if the verifier casts double → int64_t without explicit bound, mount an "off-by-eps" forgery where norm2 = β² boundary flips due to FP rounding — craft a signature whose FP norm is just under β but integer norm is over. Library: pqs + Sage prototype in CRYSTALS tools repo.
ML-DSA (Dilithium) Hint-Leak via Public-Key Compression (source: 2026 PQC challenges)
Trigger: signature scheme is ML-DSA (NIST FIPS 204) or legacy Dilithium; challenge provides "hints" h alongside (c, z) triples.
Signals: h has Hamming weight ≤ ω (80 for DILITHIUM2); parameters (q, d, γ1, γ2) match ML-DSA; a filter reveals z components bounded by γ1 − β.
Mechanic: each hint bit reveals one parity of HighBits(⟨a_i, y⟩ + c·s1). With enough signatures, build a lattice B = [A | qI] augmented by hint constraints; short-vector recovery via BKZ-40 exposes s1, then s2 follows. For constrained-hint variants (force all hints to 0), the scheme collapses to an LWE instance with biased noise — solved by lattice + primal attack with effective dimension n - ω.
SLH-DSA (SPHINCS+) Signature-Stealing via Tree Reuse (source: 2026 PQC challenges)
Trigger: SPHINCS+ or ML-DSA-derived stateful-ish signing with a bug that reuses the same FORS (Forest Of Random Subsets) instance twice.
Signals: server stores a counter that can be replayed (file-based, not atomic); two signatures derivable from the same (pk, idx) with different messages.
Mechanic: one-time-signatures in FORS guarantee security ONLY under single-use. If idx repeats, pair (msg_1, sig_1) and (msg_2, sig_2) together reveal enough tree leaves to forge a third signature on a chosen message. Equivalent HORS-then-WOTS attack exists in WOTS+ — signing two messages whose hashes share a prefix leaks chained WOTS nodes. Counter-grep: any filesystem-backed signer without atomic counter rename + fsync is vulnerable.
Invalid-Curve Attacks on Post-Quantum KEM Implementations (CSIDH / CTIDH)
Trigger: isogeny-based KEM (CSIDH-512, CTIDH, SeaSign) with public key on attacker-supplied curve parameters.
Signals: API accepts Montgomery A-coefficient directly; no twist-check; class_group_action(A, k) returns deterministically.
Mechanic: send a CSIDH key on a twist / Fp-rational subgroup of smooth order. Deterministic action reveals k mod ℓ_i for each tiny prime ℓ_i via Pohlig-Hellman on the subgroup. Over ~200 queries, CRT-combine to full k. Defense: constant-time twist check (A² - 4 square/non-square test) before every action.
CTF Crypto - Historical Ciphers
Table of Contents
Lorenz SZ40/42 (Tunny) Cipher
The Lorenz cipher uses 12 wheels to encrypt 5-bit ITA2/Baudot characters. With known plaintext, a structured attack recovers all wheel settings.
Machine structure:
- 5 χ (chi) wheels: periods 41, 31, 29, 26, 23 — advance every step
- 5 Ψ (psi) wheels: periods 43, 47, 51, 53, 59 — advance only when μ37=1
- μ61 wheel: period 61 — advances every step, controls μ37 stepping
- μ37 wheel: period 37 — advances only when μ61=1, controls Ψ stepping
Encryption: ciphertext[i] = plaintext[i] XOR chi[i] XOR psi[i] (per 5-bit character)
CRITICAL: The delta (Δ) approach is the fundamental technique:
key_stream = [pt[i] ^ ct[i] for i in range(N)]
delta_k = [key_stream[i] ^ key_stream[i+1] for i in range(N-1)]
for bit in range(5):
P = chi_periods[bit]
delta_chi = []
for phase in range(P):
vals = [delta_k_bit[i] for i in range(phase, len(delta_k_bit), P)]
delta_chi.append(1 if sum(vals) > len(vals)/2 else 0)
chi = [start]
for i in range(P-1):
chi.append(chi[-1] ^ delta_chi[i])
Common mistakes to avoid:
- Do NOT assume psi is "period 2" or just alternating — it has real wheels with periods 43-59
- Do NOT spend time on statistical period-finding for the motor — just use the structured Δ approach
- Do NOT try LFSR analysis on the step sequence — the stepping is from mechanical wheels, not LFSRs
- The "step rate" (~35%) is a consequence of μ37 being on ~50% and μ61 on ~50% = ~25% psi stepping
- Always assume standard wheel periods unless evidence says otherwise
- Total brute force space is tiny (<3M) — don't over-optimize
ITA2/Baudot encoding (5-bit):
char_to_code = {
'A': 24, 'B': 19, 'C': 14, 'D': 18, 'E': 16, 'F': 22, 'G': 11,
'H': 5, 'I': 12, 'J': 26, 'K': 30, 'L': 9, 'M': 7, 'N': 6,
'O': 3, 'P': 13, 'Q': 29, 'R': 10, 'S': 20, 'T': 1, 'U': 28,
'V': 15, 'W': 25, 'X': 23, 'Y': 21, 'Z': 17,
'9': 4, '5': 27, '8': 31, '3': 8, '4': 2, '/': 0,
}
Book Cipher Brute Force (Nullcon 2026)
Pattern (Booking Key): Book cipher encodes password as list of "steps forward" in reference text.
Key insight: Charset constraint drastically reduces candidate starting positions:
def decode_book_cipher(cipher_distances, book_text, valid_chars):
"""Brute-force starting position; filter by charset."""
candidates = []
for start_key in range(len(book_text)):
pos = start_key
password = []
valid = True
for dist in cipher_distances:
pos = (pos + dist) % len(book_text)
ch = book_text[pos]
if ch not in valid_chars:
valid = False
break
password.append(ch)
if valid:
candidates.append((start_key, ''.join(password)))
return candidates
CTF Crypto - Modern Ciphers (2024-2026)
Modern AEAD / MAC / S-box / differential attacks from 2024-2026. For the canonical toolbox (CBC padding oracle, Bleichenbacher, LFSR, length extension), see modern-ciphers.md.
Table of Contents
Non-Permutation S-box Collision Attack
Pattern (Tetraes, Nullcon 2026): Custom AES-like cipher with S-box collisions.
Detection: len(set(sbox)) < 256 means collisions exist. Find collision pairs and their XOR delta.
