メニュー
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.
Codex または Claude でインストール この Prompt をコピーして Codex、Claude、または他のアシスタントに貼り付けると、Skill ページを確認してインストールできます。
SOC 職業分類に基づく
Root-Me app-system (SSH-only): ELF x86/x64/ARM64 & Windows Kernel x64. No local GDB. Libc.rip fingerprint, patchelf, ret2libc/ROP/ret2dlresolve, FSOP glibc 2.35+, BROP, ARM64 AAPCS64 / PAC / TikTag MTE, Windows token steal / PreviousMode / Segment Heap.
Orchestrator for CTF triage: fingerprint binaries, detect manifests (package.json/Cargo/go.mod/foundry.toml), find crypto/forensics/AI artefacts, emit JSON+markdown dispatch pointers into ctf-*/SKILL.md PRI. Bundles pwnsetup/cryptosetup/websetup/foreniq/aiprobe scripts. CTFd client (ctfd.py) for sync/triage/submit workflow.
Digital forensics: disk/memory images (Volatility), PCAP + network steganography, Windows event logs & registry, side-channel power/EM traces, RF/SDR/DTMF/POCSAG decode, logic-analyzer (sigrok), image/audio stego, cryptocurrency tracing. Dispatch on file magic.
Malware & network analysis: obfuscated JS/PowerShell/VBA, PE/.NET analysis, PyInstaller/PyArmor, custom C2 protocols (RC4, AES, DNS), YARA rules, shellcode, memory-forensics IOCs, anti-sandbox/anti-VM bypass.
Miscellaneous CTF: Python/bash jails, encoding puzzles, Z3/SMT, QR codes, RF/SDR, WASM games, esoteric languages, game theory, commitment schemes, AI/ML/LLM agent exploitation (prompt injection, tool-arg injection, federated poisoning, quantum/Qiskit).
OSINT for CTF: social media tracking (X/Tumblr/BlueSky/Discord), username enumeration, reverse image search, geolocation (EXIF/MGRS/Plus Codes/What3Words), DNS/WHOIS, Wayback, FEC/Tor/GitHub mining.
| 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. |
Quick reference for crypto CTF challenges. Each technique has a one-liner here; see supporting files for full details with code.
dMap 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.
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.
dream_multiply Digit-Concatenation Diophantine (SekaiCTF 2025 I Dream of Genni)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:
# p = base + 10^k * x, so x ≡ -base * (10^k)^{-1} (mod p)
# Since p | N, construct polynomial with root x mod N
R.<x> = PolynomialRing(Zmod(N))
inv_10k = inverse_mod(10^k, N)
f = x + (base * inv_10k) % N # Must be monic!
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:
beta=0.5 means we're looking for a factor ≥ N^0.5X parameter is upper bound on root sizePattern (the-clock): Diffie-Hellman on the unit circle group.
Group structure:
# Group law: (x1,y1) * (x2,y2) = (x1*y2 + y1*x2, y1*y2 - x1*x2)
# Identity: (0, 1)
# Inverse of (x, y): (-x, y)
# Group order: p + 1 (NOT p - 1!)
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) # identity
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:
# Given points on the curve, p divides (x^2 + y^2 - 1)
from math import gcd
vals = [x**2 + y**2 - 1 for x, y in known_points]
p = reduce(gcd, vals)
# May need to remove small factors
Pohlig-Hellman when p+1 is smooth:
order = p + 1
factors = factor(order)
# Standard Pohlig-Hellman in the clock group
# Solve d in each prime-power subgroup, CRT combine
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).
Detection: Check if S-box is a permutation:
sbox = [...] # 256 entries
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):
delta at position kct1 == ct2: S-box input at position k was in the collision set {c0, c1}key[k] = v ^ round_const OR key[k] = v ^ round_const ^ deltaTotal oracle queries: 16 x 256 + 1 = 4,097 (reference ciphertext + probes).
Key lessons:
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]:
(r_i, f_i) from server (each f_i is ~32-bit random polynomial)flag = r_i (mod f_i) for all idef 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
Setup:
k < 2^64 (small), RSA modulus n is large (1337+ bits)decrypt < threshold, "error" = decrypt >= thresholdk << nAttack (simplified Manger's):
# Phase 1: Find f1 where k * f1 >= threshold
f1 = 1
while oracle(encrypt(f1)) == "below": # multiply ciphertext by f1^e mod n
f1 *= 2
# f1/2 < threshold/k <= f1, so k is in [threshold/f1, threshold/(f1/2)]
# Phase 2: Binary search for exact key
lo, hi = 0, threshold
while lo < hi:
mid = (lo + hi) // 2
f_test = ceil(threshold, mid + 1) # f such that k*f >= threshold iff k > mid
if oracle(encrypt(f_test)) == "above":
hi = mid
else:
lo = mid + 1
key = lo # ~64 queries for 64-bit key
Total queries: ~128 (64 for phase 1 + 64 for phase 2).
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 # Common LWE modulus (Kyber uses this)
n = 256 # Secret dimension
m = 512 # Number of samples
# A is m×n matrix, b is m-vector, all mod q
# Construct lattice basis for CVP approach
# Lattice: rows of [q*I_m | 0] on top, [A^T | I_n] below
# Target: b
def solve_lwe_cvp(A, b, q, n, m):
# Build lattice basis (m+n) × (m+n)
dim = m + n
B = IntegerMatrix(dim, dim)
# Top m rows: q*I_m (ensures solutions mod q)
for i in range(m):
B[i, i] = q
# Bottom n rows: A columns + identity
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 reduce the basis
LLL.reduction(B)
# Target vector: (b | 0...0)
target = [int(b[i]) for i in range(m)] + [0] * n
# CVP via Babai's nearest plane
closest = CVP.babai(B, target)
# Extract secret from last n components
s_candidate = [closest[m + j] for j in range(n)]
# Project to ternary {-1, 0, 1}
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:
# Try closest ternary value
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:
# If server says big-endian but actually uses little-endian:
s_bytes_le = bytes([(v % 256) for v in s]) # little-endian
s_bytes_be = s_bytes_le[::-1] # big-endian
# Try both interpretations for key derivation
Key derivation after LWE recovery (common pattern):
import hashlib
from Cryptodome.Cipher import AES
s_bytes = bytes([(v % 256) for v in s])
# Recover session nonce: XOR wrapped_nonce with hash of secret
session_nonce = bytes(a ^ b for a, b in
zip(wrapped_nonce, hashlib.sha256(s_bytes).digest()[:16]))
# Derive AES key from secret + nonce
aes_key = hashlib.sha256(s_bytes + session_nonce).digest()
# Decrypt AES-GCM
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:
References: EHAX CTF 2026 "Dream Labyrinth". Related: Kyber/CRYSTALS lattice cryptography.
Pattern: c = A @ p + b (mod m) where A is nxn matrix, m may not be prime (e.g., 65).
Chosen-plaintext attack:
c_i - c_0 = A @ (p_i - p_0) (mod m)A = E @ D^{-1} (mod m) using Gauss-Jordan with GCD invertibility checksb = 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) # Fermat's little theorem
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)] # augmented matrix
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)]
# For m=65=5x13: Gaussian elimination in GF(5) and GF(13) separately
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))]
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:
l=3) → ~1940 framesCount 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
# sliding min/max/mean over 100-sample window to denoise
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)
# Cluster feature sequences by visual pattern (A/B/C) — each cluster maps to one l_i
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.
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.
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.
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.
For 2024-2026 era techniques (LACTF / Nullcon / EHAX / 404CTF / FCSC / SekaiCTF / Midnightflag), see advanced-math-2.md.
Isogeny-based crypto challenges are often graph traversal problems in disguise:
Key concepts:
Modular polynomial approach:
Pathfinding in isogeny graphs:
# Height estimation via random walks to leaves
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: # leaf node
break
curr = random.choice(nbrs)
depth += 1
min_depth = min(min_depth, depth)
return min_depth
# Find path between two nodes via LCA
def find_path(start, end):
# Ascend from both nodes tracking heights
# Find least common ancestor
# Concatenate: path_up(start) + reversed(path_up(end))
Complex multiplication (CM) curves:
For elliptic curves with smooth order (many small prime factors):
from sage.all import *
# Factor curve order
E = EllipticCurve(GF(p), [a, b])
n = E.order()
factors = factor(n)
# Solve DLP in each small subgroup
partial_logs = []
for (prime, exp) in factors:
# Compute subgroup generator
cofactor = n // (prime ** exp)
G_sub = cofactor * G
P_sub = cofactor * P # Target point
# Solve small DLP
d_sub = discrete_log(P_sub, G_sub, ord=prime**exp)
partial_logs.append((d_sub, prime**exp))
# Combine with CRT
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)
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 *
# Collect 3 hints from server
# h_i = f * p_i + n_i (noise is small)
# Construct lattice where short vector reveals primes
M = matrix(ZZ, [
[1, 0, 0, h1],
[0, 1, 0, h2],
[0, 0, 1, h3],
[0, 0, 0, -1] # Scaling factor
])
reduced = M.LLL()
# Short vector contains p1, p2, p3
# Recover f = (h1 - n1) / p1
Pattern (Duality of Key): Two RSA key pairs with d1 ≈ d2 (small difference).
Attack:
# From e1*d1 ≡ 1 mod φ and e2*d2 ≡ 1 mod φ:
# d2 - d1 ≡ (e1*e2)^(-1) * (e1 - e2) mod p
# Construct polynomial f(x) = (r - x) mod p where x = d2-d1
# Use Coppersmith small_roots() to find x
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) # Adjust bounds
# x = d2 - d1, recover p from gcd(f(x), N)
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:
# Quaternion q = a0 + a1*i + a2*j + a3*k
# Components are linear in m, p, q:
a0 = m
a1 = m + α1*p + β1*q # e.g., m + 3p + 7q
a2 = m + α2*p + β2*q # e.g., m + 11p + 13q
a3 = m + α3*p + β3*q # e.g., m + 17p + 19q
# 4x4 matrix representation:
# Row 0: [a0, -a1, -a2, -a3]
# Row 1: [a1, a0, -a3, a2]
# Row 2: [a2, a3, a0, -a1]
# Row 3: [a3, -a2, a1, a0]
# Ciphertext = first row of matrix^e mod n
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
# Extract quaternion components from ciphertext row [ct0, ct1, ct2, ct3]
# Row 0 = [c0, -c1, -c2, -c3], so negate last 3:
c0, c1, c2, c3 = ct[0], (-ct[1]) % n, (-ct[2]) % n, (-ct[3]) % n
# From ratio preservation: c1*a2 = c2*a1 (mod n), c1*a3 = c3*a1 (mod n)
# Substituting a_i = m + αi*p + βi*q and eliminating m between two equations:
# Result: A*p + B*q ≡ 0 (mod n=pq) => q|A, p|B
# For components a1=m+α1p+β1q, a2=m+α2p+β2q, a3=m+α3p+β3q:
# Eliminate m from (c1*a2=c2*a1) and (c1*a3=c3*a1):
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
# More concretely for coefficients [3,7], [11,13], [17,19]:
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) # gives q
p_factor = math.gcd(B, n) # gives p
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:
# Group order for quaternions over F_p divides p²-1
d_p = pow(e, -1, p**2 - 1)
d_q = pow(e, -1, q**2 - 1)
# Decrypt mod p and mod q separately, then CRT
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)
# CRT combine: dec_matrix[0][0] = m (the flag)
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"
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 # quotient, remainder
Applications: CRT in GF(2)[x] for recovering secrets from polynomial remainders, Reed-Solomon-like error correction.
Vulnerability: Using wrong exponent for signing
sign = m^d mod n (private exponent)sign = m^e mod n (public exponent)Exploitation:
# If signature is m^e mod n, we can "encrypt" to verify
# and compute e-th root to forge signatures
from sympy import integer_nthroot
# For small e (e.g., 3), take e-th root if m^e < n
forged_sig, exact = integer_nthroot(message, e)
if exact:
print(f"Forged signature: {forged_sig}")
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:
Lattice construction (Babai's nearest plane via fpylll):
from fpylll import IntegerMatrix, CVP, LLL
# N equations: k_i = a_i * x + b_i (mod q), where |k_i| <= K (bias bound)
# Build basis B and target t so that CVP(B, t) recovers x
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 # bound term (so short vector reveals x)
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]) # we want the "centered" combination
closest = CVP.babai(B, target)
# Read x from the reduced basis — typically closest[-2] or a small post-processing step
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.
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)
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 = []
# Find repeated trigrams and their 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]
# Key length is likely the GCD of distances
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)]
# Try each shift, score by English letter frequency
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:
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.
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{" # Given
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)
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)
# Space is the most common character in English text
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.
Pattern (Shifty XOR): Each byte XORed with previous ciphertext byte.
# c[i] = p[i] ^ c[i-1] (or similar cascade)
# Brute force first byte, rest follows deterministically
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))
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:
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) # Fixed zero response
result = r.recvline()
if b"successful" in result:
break
Pattern (DumCows): Service encrypts data with deterministic keystream that resets per connection. Multiple backends with different keystreams behind a load balancer.
Attack:
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.
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...")
# If one plaintext is known (or guessable, e.g., padded 'A' chars)
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.
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.
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:
from collections import Counter
ct = "6di16ovhtmnzslsxqcjo8fkdmtyrbn..." # cleaned ciphertext
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]}")
8f, fk, and kd each appear exactly 36 times, check whether 8fkd also appears 36 times. If so, it is a single substitution unit:# Iteratively replace most-frequent fixed groups with single symbols
substitutions = {
'8fkd': 'E', '4bg9': 'I', 'lsxq': 'A', 'fmrk': 'B',
'9gle': 'C', 'mtyr': 'D', 'cjo': 'F', 'htm': 'G',
# ... continue for all identified groups
}
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' # chars with uncertain mapping
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.
# SageMath ECC basics
E = EllipticCurve(GF(p), [a, b])
G = E.gens()[0] # generator
order = E.order()
If point validation is missing, send points on weaker curves. Craft points with small-order subgroups to leak secret key bits.
If discriminant delta = 0, curve is singular. DLP becomes easy (maps to additive/multiplicative group).
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)
# Sage's discrete_log handles anomalous curves automatically
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) # p-adic field with precision 2
Ep = EllipticCurve(Qp, [a, b])
# Lift points to p-adics
Gp = Ep.lift_x(ZZ(G[0]), all=True) # try both lifts
Qp_point = Ep.lift_x(ZZ(Q[0]), all=True)
for gp in Gp:
for qp in Qp_point:
try:
# Multiply by p to get points in kernel of reduction
pG = p * gp
pQ = p * qp
# Extract p-adic logarithm
x_G = ZZ(pG[0] / pG[1]) / p # or pG.xy()
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.
Pattern (Faulty Curves): Bit flip during ECC computation reveals private key bits.
Attack: Compare correct vs faulty ciphertext, recover key bit-by-bit:
# For each key bit position:
# If fault at bit i changes output -> key bit i affects computation
# Binary distinguisher: faulty_output == correct_output -> bit is 0
Pattern (the-clock): Diffie-Hellman on unit circle group: x^2 + y^2 = 1 (mod p).
Key facts:
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) # identity
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:
# Given points on the curve, p divides (x^2 + y^2 - 1)
from math import gcd
vals = [x**2 + y**2 - 1 for x, y in known_points]
p = reduce(gcd, vals)
# May need to remove small factors
Attack when p+1 is smooth:
# 1. Recover p from points: gcd(x^2 + y^2 - 1) across known points
# 2. Factor p+1 into small primes
# 3. Pohlig-Hellman: solve DLP in each small subgroup, CRT combine
# 4. Compute shared secret, derive AES key (e.g., via MD5)
Identification: Challenge mentions "clock", "circle", or gives points satisfying x^2+y^2=1. Always check if p+1 (not p-1) is smooth.
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:
8*l, but scalars are reduced mod lMASTER_KEY * 2^t wraps around l, multiplication produces a torsion component visible as y-coordinate changeKey extraction via binary decomposition:
# Query sign(uid=3, 2^t) for t = 0..255
# S_t = (MASTER_KEY * 2^t mod l) * P3
# Check: does doubling S_t match S_{t+1}?
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)
# Wrap occurred if doubled.y != S_{t+1}.y (torsion shift)
bits.append(0 if doubled.y == S_t1.y else 1)
# Reconstruct: MASTER_KEY ≈ l * (0.bit0 bit1 bit2 ...)_binary
# Try all 8 torsion corrections for exact value
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.
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
# Two signatures (r, s1) and (r, s2) with same r → same nonce k
h1 = int(sha256(msg1).hexdigest(), 16)
h2 = int(sha256(msg2).hexdigest(), 16)
n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 # secp256k1 order
k = ((h1 - h2) * pow(s1 - s2, -1, n)) % n
d = ((s1 * k - h1) * pow(r, -1, n)) % n # private key
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.
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.
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.
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]
# Swap at junction
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
# Key exchange:
# alice_pub = scramble(connect(pub_info, alice_priv), 1000)
# bob_pub = scramble(connect(pub_info, bob_priv), 1000)
# shared = sha256(str(normalize(calculate(connect(alice_priv, bob_pub)))))
The fatal vulnerability — Alexander polynomial multiplicativity:
The Alexander polynomial satisfies Δ(β₁·β₂) = Δ(β₁) × Δ(β₂) under braid concatenation. This makes the scheme abelian:
# Eve computes shared secret from public values only:
calc_pub = normalize(calculate(pub_info))
calc_alice = normalize(calculate(alice_pub))
calc_bob = normalize(calculate(bob_pub))
# Recover Alice's private polynomial
calc_alice_priv = sp.cancel(calc_alice / calc_pub) # exact division
# Shared secret = calc(alice_priv) * calc(bob_pub) = calc(bob_priv) * calc(alice_pub)
shared_poly = normalize(sp.expand(calc_alice_priv * calc_bob))
shared_hex = hashlib.sha256(str(shared_poly).encode()).hexdigest()
# Decrypt XOR stream cipher
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:
# Winding numbers range from w_min to w_max (e.g., -1 to 5)
# Multiply all entries by t^w_max to get polynomial matrix
k = max(abs(w) for row in winding_matrix for w in row)
n = len(winding_matrix)
# Original: M[i][j] = t^(-w[i][j])
# Scaled: M'[i][j] = t^(k - w[i][j]) (all non-negative powers)
mat_poly = sp.Matrix([[t**(k - w) for w in row] for row in winding_matrix])
det_scaled = mat_poly.det(method='bareiss') # Much faster!
# Recover true determinant: det(M) = det(M') / t^(k*n)
det_true = sp.cancel(det_scaled / t**(k * n))
# Then: (1-t)^(n-1) divides det_true (topological property)
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:
t^k to get polynomials, compute det, divide back.References: DiceCTF 2026 "Plane or Exchange"
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:
?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
# Match SageMath's RealField(N) precision exactly:
# RealField(256) = 256-bit MPFR mantissa
mpmath.mp.prec = 256 # BINARY precision (not decimal!)
# For decimal: mpmath.mp.dps = N sets decimal places
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))
# Hierarchical search: determine unknown digits sequentially
masked = "?7086013?3756162?51694057..."
unknown_positions = [0, 8, 16, 25, 33, ...]
# Step 1: Fix digits that are constant across all valid flags
# (compute forward for min/max valid flag, compare)
# Step 2: For each remaining unknown (largest positional weight first):
for pos in remaining_unknowns:
for digit in range(10):
# Set this digit, others to middle value (5)
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')
# Check: starts with prefix? Ends with suffix? All ASCII?
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"
Pattern (Tropped): Diffie-Hellman key exchange using tropical matrices (min-plus algebra). Per-character shared secret XOR'd with encrypted flag.
Tropical algebra:
min(a, b)a + b(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)
"""
# Right residual: b*[j] = max_i(Mb[i] - M[i][j])
b_star = [max(Mb[i] - M[i][j] for i in range(n)) for j in range(n)]
# Shared secret: aMb = min_j(aM[j] + b*[j])
aMb = min(aM[j] + b_star[j] for j in range(n))
return aMb
# Decrypt per-character: key = aMb % 32; plaintext = key ^ ciphertext
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 +.
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.
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.
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/.
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.
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 - ω.
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.
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.
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:
Encryption: ciphertext[i] = plaintext[i] XOR chi[i] XOR psi[i] (per 5-bit character)
CRITICAL: The delta (Δ) approach is the fundamental technique:
# Step 1: Get keystream from known plaintext
key_stream = [pt[i] ^ ct[i] for i in range(N)]
# Step 2: Compute delta keystream (THE key insight)
delta_k = [key_stream[i] ^ key_stream[i+1] for i in range(N-1)]
# delta_k = delta_chi XOR delta_psi
# Since psi only moves ~25% of the time, delta_k BIASES toward delta_chi
# Step 3: Recover delta_chi via majority vote at each wheel position
# Assume wheels start at position 1
for bit in range(5):
P = chi_periods[bit] # [41, 31, 29, 26, 23]
delta_chi = []
for phase in range(P):
# Collect all delta_k values at this wheel phase
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)
# Step 4: Integrate delta_chi to get chi (2 candidates per wheel, start 0 or 1)
chi = [start] # start = 0 or 1
for i in range(P-1):
chi.append(chi[-1] ^ delta_chi[i])
# Circular consistency: chi[0] ^ chi[-1] should equal delta_chi[P-1]
# Step 5: Subtract chi from keystream to get psi contribution
# Identify when psi steps: delta_psi = delta_k XOR delta_chi
# When ALL 5 bits of delta_psi are 0 → μ37 was off (psi didn't step)
# (Statistically very rare for all 5 cams to not change when stepping)
# Step 6: From stepping pattern, determine μ61 (period 61)
# μ61[pos] = 1 when we see psi resume stepping after being stopped
# Step 7: Cross-reference to get μ37 (period 37)
# μ37 position advances only when μ61=1
# Step 8: Determine psi wheels from delta_psi values when stepping occurs
# Look for repeating patterns with periods 43, 47, 51, 53, 59
# Step 9: Brute force remaining ambiguity
# Total candidates: 2^5 (chi) × 2^5 (psi) × 61×37 (μ positions) = 2,313,472
# Trivially brutable - decrypt and check if known plaintext matches
Common mistakes to avoid:
ITA2/Baudot encoding (5-bit):
# Standard ITA2 mapping used in Lorenz challenges
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,
}
# Code 27 = FIGS shift, Code 31 = LTRS shift
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 # Typically 3-4 candidates out of ~56k positions
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.
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.
Attack: For each key byte, try 256 plaintexts differing by delta. When ct1 == ct2, S-box input was in collision set. 2-way ambiguity per byte, 2^16 brute-force. Total: 4,097 oracle queries.
See advanced-math.md for full S-box collision analysis code.
Known parameters: If LCG (Linear Congruential Generator) constants (M, A, C) are known and output is state mod N, iterate by N through modulus to find state:
# output = state % N, state = (A * prev + C) % M
for candidate in range(output, M, N):