Ctf Crypto

CTF 密码学攻击

深入参考

以下参考资料按需加载，根据识别出的具体方向选择对应文件：

• 古典密码（Vigenere/Atbash/XOR/OTP/同音替换） → references/classic-ciphers.md
• 现代密码攻击（AES/CBC/Padding Oracle/LFSR/MAC伪造） → references/modern-ciphers.md
• RSA 攻击（小指数/Wiener/Pollard/Coppersmith/Hastad/CRT） → references/rsa-attacks.md
• ECC 攻击（小子群/无效曲线/Smart/ECDSA nonce重用） → references/ecc-attacks.md
• 高级数学攻击（格/LWE/同源/Pohlig-Hellman/LLL） → references/advanced-math.md
• PRNG 攻击（MT19937/LCG/V8 XorShift128+/混沌映射） → references/prng.md
• ZKP 与约束求解（Z3/图着色/Groth16/Shamir SSS） → references/zkp-and-advanced.md
• 历史密码（Lorenz SZ40/42/Book Cipher） → references/historical.md
• 奇异代数结构（辫群DH/热带半环/FPE/Goldwasser-Micali） → references/exotic-crypto.md
• 格与LWE攻击（LLL/BKZ/Babai CVP/Coppersmith格/NTRU） → references/lattice-and-lwe.md
• 现代密码攻击续（Blum-Goldwasser/Hash长度扩展/RC4统计） → references/modern-ciphers-2.md
• 现代密码攻击Part3（自定义Hash反转/CRC32爆破/HMAC时序） → references/modern-ciphers-3.md
• RSA专项技术（p=q绕过/CRT立方根/多素数分解/部分密钥） → references/rsa-attacks-2.md
• 流密码攻击（LFSR/RC4第二字节偏差/Salsa20/ChaCha20） → references/stream-ciphers.md

---

分类决策树

题目涉及加密？
├─ 古典密码（Caesar/Vigenere/XOR/替换） → [references/classic-ciphers.md](references/classic-ciphers.md)
├─ 对称加密（AES/DES/RC4/分组密码）
│  ├─ ECB → 块重排 / 逐字节oracle
│  ├─ CBC → 比特翻转 / Padding Oracle
│  └─ 流密码 → LFSR / Berlekamp-Massey
├─ RSA
│  ├─ 小e → 开根号         ├─ 小d → Wiener
│  ├─ p≈q → Fermat          ├─ 公共模数 → ExtGCD
│  └─ 部分已知因子 → Coppersmith (SageMath)
├─ ECC
│  ├─ 阶有小因子 → Pohlig-Hellman
│  ├─ 奇异曲线 → 映射到加法群
│  └─ ECDSA nonce重用 → 恢复私钥
├─ 格/LWE → Babai CVP / LLL 短向量
├─ PRNG → MT19937 untemper / LCG / V8 xs128p
├─ ZKP → 碰撞/预测盐 / Z3求解
└─ 哈希 → 长度扩展(hashpump) / 生日攻击

速查工具

常用 Python 库

pip install pycryptodome z3-solver sympy gmpy2

RSA 基础速查

from Crypto.Util.number import inverse, long_to_bytes
phi = (p-1)*(q-1)
d = inverse(e, phi)
m = pow(c, d, n)
print(long_to_bytes(m))

常见模式

• RSA 乘法同态：未填充 RSA S(a)*S(b) mod n = S(a*b)，可组合签名伪造
• CBC Padding Oracle：~4096 次查询解密一个16字节块
• Bleichenbacher (ROBOT)：RSA PKCS#1 v1.5 填充oracle → ~10K 次查询恢复明文
• CRC32 线性：追加4字节可伪造任意CRC32签名
• 哈希长度扩展：Merkle-Damgard 结构 hash(SECRET||data) 可追加数据

RSA 小指数攻击

• 当 e=3 时，若 m^3 < n（不取模、没有模运算），可直接开立方恢复明文

Padding Oracle 细节

• 每字节最多 256 次尝试，暴力尝试所有可能值

CTF Crypto - Advanced Mathematical Attacks

Table of Contents

• Elliptic Curve Isogenies
• Pohlig-Hellman Attack (Weak ECC)
• LLL Algorithm for Approximate GCD
• Merkle-Hellman Knapsack Cryptosystem via LLL (ASIS 2014)
• Coppersmith's Method (Close Private Keys)
• Coppersmith's Method (Structured Primes, LACTF 2026)
• Clock Group (x^2+y^2=1 mod p) DLP (LACTF 2026)
• Quaternion RSA
• [Polynomial Arithmetic in GF(2)[x]](#polynomial-arithmetic-in-gf2x)
• RSA Signing Bug
• Non-Permutation S-box Collision Attack (Nullcon 2026)
• [Polynomial CRT in GF(2)[x] (Nullcon 2026)](#polynomial-crt-in-gf2x-nullcon-2026)
• Manger's RSA Padding Oracle Attack (Nullcon 2026)
• LWE Lattice Attack via CVP (EHAX 2026)
• Affine Cipher over Non-Prime Modulus (Nullcon 2026)

---

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:

# 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:

• 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 *

# 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)

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 *

# 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

Merkle-Hellman Knapsack Cryptosystem via LLL (ASIS 2014)

The Merkle-Hellman knapsack is a broken asymmetric scheme. Given public key P = [p0, ..., pn-1] and ciphertext C (sum of selected public key elements), recover the binary plaintext vector:

# Sage
nbit = len(pubKey)
A = Matrix(ZZ, nbit + 1, nbit + 1)

# Identity matrix in upper-left (tracks which elements are selected)
for i in range(nbit):
    A[i, i] = 1
    A[i, nbit] = pubKey[i]

# Target sum in bottom-right
A[nbit, nbit] = -int(encoded)

# LLL reduction finds short vector where last element is 0
res = A.LLL()

# Find row with last element == 0 and all others in {0, 1}
for row in res:
    if row[-1] == 0 and all(b in (0, 1) for b in row[:-1]):
        plaintext_bits = list(row[:-1])
        break

Key insight: The knapsack problem becomes easy when reformulated as a shortest vector problem. The LLL-reduced basis contains a row representing the binary plaintext when the last column is zero.

Coppersmith's Method (Close Private Keys)

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)

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:

# 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:

• Polynomial MUST be monic (leading coefficient 1)
• beta=0.5 means we're looking for a factor ≥ N^0.5
• X 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:

# 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).

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:

# 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"

---

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  # quotient, remainder

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:

# 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}")

---

Non-Permutation S-box Collision Attack (Nullcon 2026)

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): 1. Try all 256 values v: encrypt two plaintexts differing by delta at position k 2. When ct1 == ct2: S-box input at position k was in the collision set {c0, c1} 3. Deduce: key[k] = v ^ round_const OR key[k] = v ^ round_const ^ delta 4. 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]: 1. Collect ~20 pairs (r_i, f_i) from server (each f_i is ~32-bit random polynomial) 2. Filter for coprime pairs using polynomial GCD 3. Apply CRT to combine: flag = r_i (mod f_i) for all i 4. 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):

# 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).

---

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  # 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:

• 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: 1. Send n+1 crafted inputs to get n+1 ciphertext blocks 2. Difference attack: c_i - c_0 = A @ (p_i - p_0) (mod m) 3. Build difference matrices D (plaintext) and E (ciphertext) 4. Solve: A = E @ D^{-1} (mod m) using Gauss-Jordan with GCD invertibility checks 5. 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)  # 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))]

CTF Crypto - Classic Ciphers

Table of Contents

• Vigenere Cipher
• Atbash Cipher
• Substitution Cipher with Rotating Wheel
• Kasiski Examination for Key Length
• XOR Variants
• Multi-Byte XOR Key Recovery via Frequency Analysis
• Cascade XOR (First-Byte Brute Force)
• XOR with Rotation: Power-of-2 Bit Isolation (Pragyan 2026)
• Weak XOR Verification Brute Force (Pragyan 2026)
• Deterministic OTP with Load-Balanced Backends (Pragyan 2026)
• OTP Key Reuse / Many-Time Pad XOR (BYPASS CTF 2025)
• Book Cipher
• Variable-Length Homophonic Substitution (ASIS CTF Finals 2013)

---

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 = []

    # 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: 1. Key may not repeat - could be as long as message 2. Key derived from challenge theme (character names, phrases) 3. Key may have "padding" - repeated letters (IICCHHAA instead of ICHA) 4. 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{"  # 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)

---

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)
    # 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.

Cascade XOR (First-Byte Brute Force)

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))

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: 1. 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 2. Only 4 candidate states -> try all, verify against all frames 3. 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)  # Fixed zero response
    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: 1. Send known plaintext (e.g., 18 bytes of 'A'), XOR with ciphertext -> recover keystream 2. XOR keystream with target ciphertext -> decrypt secret 3. 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...")

# 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.

---

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:

1. Collapse whitespace and compute n-gram frequencies (1 through 6):

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]}")

2. 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:

# 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)

3. The reduced text is now a monoalphabetic substitution — solve with quipqiup.com or statistical analysis on English.

4. 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.

CTF Crypto - Elliptic Curve Attacks

Table of Contents

• Small Subgroup Attacks
• Invalid Curve Attacks
• Singular Curves
• Smart's Attack (Anomalous Curves)
• ECC Fault Injection
• Clock Group DLP via Pohlig-Hellman (LACTF 2026)
• ECDSA Nonce Reuse (BearCatCTF 2026)
• Ed25519 Torsion Side Channel (BearCatCTF 2026)

---

Small Subgroup Attacks

• Check curve order for small factors
• Pohlig-Hellman: solve DLP in small subgroups, combine with CRT

# SageMath ECC basics
E = EllipticCurve(GF(p), [a, b])
G = E.gens()[0]  # generator
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)
# 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.

---

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:

# 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

---

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 - x1*x2)
• 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)  # 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.

---

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:

# 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.

---

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

# 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.

CTF Crypto - Exotic Algebraic Structures

Table of Contents

• Braid Group DH — Alexander Polynomial Multiplicativity (DiceCTF 2026)
• Monotone Function Inversion with Partial Output
• Tropical Semiring Residuation Attack (BearCatCTF 2026)
• Paillier Cryptosystem Attack (SECCON 2015)
• Hamming Code Error Correction with Helical Interleaving (Sharif CTF 2016)
• ElGamal Universal Re-encryption (Sharif CTF 2016)
• Paillier Oracle Size Bypass via Ciphertext Factoring (BSidesSF 2025)
• Format-Preserving Encryption Feistel Brute-Force (BSidesSF 2026)
• Icosahedral Symmetry Group Cipher (BSidesSF 2026)
• Goldwasser-Micali Ciphertext Replication Oracle (BSidesSF 2026)

---

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]
    # 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:

• 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

1. 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.

2. 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).

3. 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"

---

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)
    """
    # 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 +.

---

Paillier Cryptosystem Attack (SECCON 2015)

The Paillier cryptosystem is a homomorphic encryption scheme where c = g^m * r^n mod n^2. When given oracle equations involving c, o, h values:

1. Recover n: Compute lower bound sqrt(max(c, o, h)) to approximate n, then brute-force nearby values 2. Validate n: Check equation h = (c * o) % (n^2) for correctness 3. Factor n: Use standard methods (e.g., factordb) to find p, q 4. Decrypt: Apply Paillier decryption:

from sympy import lcm, mod_inverse

# n = p * q (factored)
lam = lcm(p - 1, q - 1)  # Carmichael function
n2 = n * n

def L(x):
    return (x - 1) // n

# Compute mu
g_lam = pow(g, lam, n2)
mu = mod_inverse(L(g_lam), n)

# Decrypt
c_lam = pow(c, lam, n2)
m = (L(c_lam) * mu) % n

Key insight: Paillier operates mod n^2, so ciphertext values are much larger than RSA. The homomorphic property E(m1) * E(m2) = E(m1 + m2) can leak relationships between plaintexts.

---

Hamming Code Error Correction with Helical Interleaving (Sharif CTF 2016)

When data is protected by Hamming(31,26) codes with helical scan interleaving:

1. Determine matrix dimensions: Brute-force width/height (30x30 search space) by testing which dimensions produce valid Hamming codewords 2. Read data in helical pattern: Extract bits diagonally from the interleaved matrix 3. Apply Hamming parity check: Multiply codeword by parity check matrix H to detect/correct errors

import numpy as np

def check_hamming(codeword, H):
    """Syndrome = H * c^T; zero syndrome means valid codeword"""
    syndrome = np.dot(H, codeword) % 2
    return np.all(syndrome == 0)

# Brute-force dimensions
for w in range(1, 31):
    for h in range(1, 31):
        # Reshape data into w x h matrix
        matrix = data[:w*h].reshape(h, w)
        # Read diagonals (helical scan)
        bits = read_helical(matrix)
        # Check if bits form valid Hamming codewords
        if validate_hamming_stream(bits, H):
            print(f"Dimensions: {w}x{h}")

Key insight: Try 8 different bit alignment offsets when the start position is unknown. Valid Hamming codewords have zero syndrome under multiplication by the parity check matrix.

---

ElGamal Universal Re-encryption (Sharif CTF 2016)

Given an ElGamal-like ciphertext tuple (a, b, c, d) = (g^r, h^r, g^s, m*h^s), produce a different valid ciphertext decrypting to the same message without knowing the private key:

Transform exponents r -> 2r, s -> r+s:

def reencrypt(a, b, c, d, p):
    return [
        (a * a) % p,    # g^(2r)
        (b * b) % p,    # h^(2r)
        (a * c) % p,    # g^(r+s)
        (d * b) % p     # m*h^(r+s)
    ]

Key insight: ElGamal's homomorphic property allows re-randomizing ciphertexts by multiplying components. The relationship between exponents must remain consistent: both pairs must share the same exponent offset.

---

Paillier Oracle Size Bypass via Ciphertext Factoring (BSidesSF 2025)

When a Paillier decryption oracle rejects messages exceeding a size limit (e.g., >2000 bits), exploit the homomorphic property to factor the encrypted flag into smaller pieces:

1. Paillier additive homomorphism: E(m1) * E(m2) mod n^2 = E(m1 + m2 mod n) 2. Multiplicative (scalar): E(m)^k mod n^2 = E(k*m mod n) 3. Factoring ciphertext: Divide n into small ranges, query oracle with E(flag) * E(-offset)^1 to determine which range contains the flag 4. Chunk extraction: Split the flag value into pieces that each fit within the oracle's size limit, decrypt individually, sum to recover original

from Crypto.Util.number import inverse

def paillier_sub(c, plaintext_sub, n):
    """Compute E(m - plaintext_sub) from E(m) using homomorphic property"""
    n2 = n * n
    # E(-plaintext_sub) = E(n - plaintext_sub) = (n+1)^(n-plaintext_sub) * r^n mod n^2
    neg_enc = pow(n + 1, n - plaintext_sub, n2)
    return (c * neg_enc) % n2

# Binary search for flag value using oracle
def recover_flag(enc_flag, n, oracle_decrypt):
    low, high = 0, n
    while high - low > 1:
        mid = (low + high) // 2
        test_ct = paillier_sub(enc_flag, mid, n)
        result = oracle_decrypt(test_ct)
        if result < n // 2:  # Positive (flag > mid)
            low = mid
        else:  # Negative (flag < mid, wraps around)
            high = mid
    return low

Key insight: Paillier's additive homomorphism allows computing E(flag - offset) without decryption. If the oracle reveals whether the decrypted value is "small" (within limit) or "large" (rejected/wraps), binary search recovers the flag in O(log n) queries.

---

Format-Preserving Encryption Feistel Brute-Force (BSidesSF 2026)

Pattern (tokencrypt): Format-preserving encryption (FPE) using a Feistel network with a small round key. The 96-bit key splits into three components with different roles: a brute-forceable core, a GF(2) mixing matrix, and an affine offset.

Key structure:

• s (16 bits): Feistel round subkey — only 2^16 = 65536 possibilities
• seed56 (56 bits): Generates an invertible GF(2) affine mixing matrix M (24x24)
• b24 (24 bits): Affine offset applied after mixing

Attack: 1. Collect encrypt pairs: Get multiple (plaintext, ciphertext) pairs from the FPE oracle 2. Brute-force `s`: For each of 65536 candidate round keys, run the Feistel network on known plaintexts. If the Feistel core is correct, the remaining transformation is affine over GF(2) 3. Solve linear system: With correct s, the relationship ciphertext = M * feistel_output XOR b24 is linear. Collect 24+ pairs, build a GF(2) matrix equation, solve for M and b24 via Gaussian elimination

import numpy as np

def feistel_encrypt(pt_24bit, s, rounds=3):
    """24-bit Feistel with 16-bit round key s."""
    L, R = pt_24bit >> 12, pt_24bit & 0xFFF
    for r in range(rounds):
        f = (R * s + r) & 0xFFF  # Round function (example)
        L, R = R, L ^ f
    return (L << 12) | R

# Brute-force s (16-bit)
for s_candidate in range(1 << 16):
    feistel_outputs = [feistel_encrypt(pt, s_candidate) for pt in known_pts]
    # Check if feistel_outputs -> known_cts is affine over GF(2)
    # Build system: for each bit position, collect equations
    # If consistent -> found correct s, solve for M and b24

When to recognize: Challenge mentions "format-preserving encryption", "FPE", or uses a Feistel structure with suspiciously small key components. Any round key under 32 bits is brute-forceable.

Key lessons:

• FPE with small Feistel round keys is trivially broken despite the total key looking large (96 bits)
• After recovering the Feistel core, the remaining affine layer is solvable as a linear system over GF(2)
• Collect enough plaintext-ciphertext pairs to overdetermine the linear system

References: BSidesSF 2026 "tokencrypt"

---

Icosahedral Symmetry Group Cipher (BSidesSF 2026)

Pattern (dodecacrypt): Encryption maps message bytes to face permutations of a dodecahedron. The icosahedral symmetry group has order 120 (the rotation group of a regular dodecahedron/icosahedron), so each "digit" in base-120 encodes one group element as a specific arrangement of 12 face labels.

How it works: 1. Message is converted to a large integer and expressed in base 120 2. Each base-120 digit selects one of 120 possible face permutations 3. The dodecahedron is rendered from a fixed viewing angle, showing only 6 of 12 faces 4. Despite only 6 faces being visible, collisions between the 120 permutations are rare enough for unique recovery

Attack: 1. Build lookup table: Probe the encryption API with all 120 single-digit inputs (0-119 in base 120), capture the rendered face arrangement for each 2. Match visible faces: For each encrypted symbol in the ciphertext, compare the visible face pattern against the lookup table to recover the base-120 digit 3. Reconstruct message: Convert the sequence of base-120 digits back to an integer, then to bytes

import itertools

# Build lookup: probe API with single-digit values
lookup = {}
for digit in range(120):
    # Send digit, capture 6 visible face labels from rendered image
    visible = get_visible_faces(encrypt_single(digit))
    lookup[tuple(visible)] = digit

# Decrypt ciphertext
base120_digits = []
for symbol in ciphertext_symbols:
    visible = get_visible_faces(symbol)
    base120_digits.append(lookup[tuple(visible)])

# Convert base-120 to bytes
value = sum(d * 120**i for i, d in enumerate(reversed(base120_digits)))
plaintext = value.to_bytes((value.bit_length() + 7) // 8, 'big')

When to recognize: Challenge involves polyhedra, dodecahedra, icosahedra, or mentions "120 rotations", "symmetry group", or shows 3D-rendered geometric objects with labeled faces.

Key insight: The icosahedral rotation group is small enough (order 120) that a complete lookup table fits easily in memory. Even with partial information (only 6 of 12 faces visible), the permutations are sufficiently distinct to avoid collisions in practice.

References: BSidesSF 2026 "dodecacrypt"

---

Goldwasser-Micali Ciphertext Replication Oracle (BSidesSF 2026)

Pattern (kproof): A "proof of knowledge" protocol encrypts a user-chosen AES key using Goldwasser-Micali (GM) bit-by-bit encryption. The service decrypts GM ciphertext bits to reconstruct the AES key, then uses it to decrypt and hash a probe payload. The vulnerability: individual GM ciphertext values can be replayed, and 128 copies of the same GM-encrypted bit produce an AES key of either 0x00...00 or 0xFF...FF.

Goldwasser-Micali basics:

• Encrypts one bit at a time: bit 0 → quadratic residue mod n, bit 1 → non-residue
• Decryption tests whether each ciphertext value is a quadratic residue
• Each ciphertext value independently encodes exactly one bit

The vulnerability: The service accepts 128 GM ciphertext lines as the AES key. By sending the SAME GM ciphertext value 128 times, the decrypted key is either all-zeros (if the bit was 0) or all-ones (if the bit was 1). Since you control the probe plaintext and IV, you can precompute both possible SHA-256 hashes and compare against the service response.

Attack (128 oracle queries for full key recovery):

from Crypto.Cipher import AES
import hashlib

def recover_bit(gm_ciphertext_line, probe_ct, probe_iv, oracle):
    """Determine if a single GM ciphertext encodes 0 or 1."""
    # Replicate the single GM bit 128 times as the AES key
    key_all_zero = b'\x00' * 16
    key_all_ones = b'\xff' * 16

    # Precompute expected hashes for both possible keys
    hash0 = hashlib.sha256(
        AES.new(key_all_zero, AES.MODE_CBC, probe_iv).decrypt(probe_ct)
    ).hexdigest()
    hash1 = hashlib.sha256(
        AES.new(key_all_ones, AES.MODE_CBC, probe_iv).decrypt(probe_ct)
    ).hexdigest()

    # Query oracle with replicated GM line
    result_hash = oracle.query(gm_ciphertext_line, copies=128)

    if result_hash == hash0:
        return 0
    elif result_hash == hash1:
        return 1

# Recover all 128 bits of the AES key
captured_gm_lines = parse_transcript(transcript)  # 128 GM ciphertext values
key_bits = [recover_bit(line, probe_ct, probe_iv, oracle)
            for line in captured_gm_lines]

# Reconstruct AES key and decrypt the captured payload
aes_key = bits_to_bytes(key_bits)
plaintext = AES.new(aes_key, AES.MODE_CBC, captured_iv).decrypt(captured_ct)

Key insight: Goldwasser-Micali's bit-by-bit encryption means each ciphertext value independently encodes one bit. If a protocol allows replaying individual GM values as components of a larger key, each bit can be isolated and determined via a distinguishing oracle (here, SHA-256 hash comparison). This reduces key recovery from 2^128 brute-force to 128 linear queries.

When to recognize: Challenge uses bit-by-bit public-key encryption (GM, Rabin) combined with a symmetric key derivation step. The service decrypts individual ciphertext values without binding them to a position or preventing replay.

Broader principle: Any protocol that (1) encrypts a key bit-by-bit and (2) provides an oracle on the reconstructed key is vulnerable to bit-by-bit recovery via replication. The specific oracle (hash, decryption check, timing) varies but the attack structure is the same.

References: BSidesSF 2026 "kproof"

CTF Crypto - Historical Ciphers

Table of Contents

• Lorenz SZ40/42 (Tunny) Cipher
• Book Cipher Brute Force (Nullcon 2026)

---

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:

# 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:

• 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):

# 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

---

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  # Typically 3-4 candidates out of ~56k positions

CTF Crypto - Lattice and LWE Attacks

Table of Contents

• Quick Triage: Is This a Lattice Problem?
• Core Tools: LLL, BKZ, Babai, CVP, SVP
• LLL
• BKZ
• Babai nearest plane
• CVP vs SVP
• Hidden Number Problem (HNP): Partial Nonce / Biased Nonce
• Minimal ECDSA partial-nonce workflow
• LCG and Truncated Output as a Lattice Problem
• Minimal truncated-LCG workflow
• LWE via Embedding and CVP
• Embedding-style lattice
• For ternary or sparse secrets
• Ring-LWE / Module-LWE Recognition Notes
• Flattening Ring-LWE to plain LWE
• Orthogonal Lattices: HSSP / AHSSP Style Recovery
• Subset Sum / Knapsack via Lattice Reduction
• Common Failure Modes
• Quick Checklist Before You Commit to Lattices

---

Quick Triage: Is This a Lattice Problem?

Use lattice tools when the challenge gives you:

• many modular equations plus a promise that the hidden values are small, sparse, or close to each other
• partial leakage of a secret nonce, seed, or state bits
• linear relations with bounded error terms
• vectors or matrices over Z_q where the true solution should be unusually short
• a subset-sum or knapsack instance that "looks too structured"

Typical CTF phrasing:

• "high bits of k are known"
• "the error is small"
• "the secret coefficients are in {-1,0,1}"
• "recover seed from truncated outputs"
• "find a short vector"
• "solve noisy linear equations modulo q"

First question to ask: what is supposed to be small?

• the secret itself
• the error vector
• the nonce difference
• a subset indicator vector in {0,1}^n
• a correction term caused by modular wraparound

That "small thing" is usually what the lattice is trying to expose.

---

Core Tools: LLL, BKZ, Babai, CVP, SVP (ASIS CTF Finals 2015, CTFZone 2017)

LLL

Default first move. Fast, easy, often enough for CTF-sized parameters.

Use it when:

• dimensions are moderate
• the hidden vector is very short
• the challenge author clearly expects a standard embedding attack
• you want structure first, exact recovery second

from sage.all import Matrix, ZZ

M = Matrix(ZZ, basis_rows)
R = M.LLL()
print(R[0])

BKZ

Use when LLL almost works but not quite.

• better for harder CVP/SVP instances
• useful when the gap between the target vector and random lattice vectors is small
• in CTFs, BKZ(block_size=20..35) is often already enough

R = M.BKZ(block_size=25)

Babai nearest plane

Good for approximate CVP after reduction.

• reduce basis with LLL or BKZ first
• then apply Babai to recover the nearby vector
• often enough for ternary or small-error LWE

from fpylll import IntegerMatrix, CVP

# After building and reducing the lattice basis:
closest = CVP.babai(B, target)

CVP vs SVP

• SVP: "find an unusually short non-zero lattice vector"
• CVP: "find the lattice vector closest to a target"

Rule of thumb:

• if you only know "some relation must be very short", think SVP / embedding
• if you already have a target vector and want the nearest valid lattice point, think CVP / Babai

---

Hidden Number Problem (HNP): Partial Nonce / Biased Nonce (nullcon HackIM 2020, Ledger Donjon CTF 2020)

Pattern: signatures or RNG equations leak a few bits of a hidden value k, or k is sampled from a small / biased range.

This is the classic route from:

• ECDSA partial nonce leakage
• Schnorr biased nonce leakage
• custom congruence systems where only high bits or low bits are known

Generic shape:

a_i * x + b_i ≡ e_i (mod q)

where:

• x is the secret key
• e_i is small or partially known

That "small error" is what turns the problem into a lattice instance.

When to use:

• repeated signatures with leaked high bits / low bits of k
• same signing scheme with biased or short nonces
• LCG-like recurrence where each output leaks only part of the internal state

Practical workflow:

1. normalize all equations so the secret key is the same unknown in every row 2. isolate the bounded error term 3. scale rows so all coordinates have comparable size 4. run LLL 5. test the candidate secret against the original equations

Skeleton:

from sage.all import Matrix, ZZ

def build_hnp_lattice(q, coeffs, bounds):
    n = len(coeffs)
    rows = []
    for i in range(n):
        row = [0] * (n + 1)
        row[i] = q
        rows.append(row)

    last = [c for c in coeffs] + [bounds]
    rows.append(last)
    return Matrix(ZZ, rows)

Key insight: HNP attacks usually do not require a perfect lattice model. In CTFs, once the true secret produces a vector much shorter than random noise, LLL often exposes it directly or gets you close enough to brute-force the last few bits.

Minimal ECDSA partial-nonce workflow

If a challenge leaks the top bits of each nonce k_i, write:

k_i = leaked_i * 2^t + delta_i

where delta_i is small. For ECDSA:

s_i * k_i - h_i ≡ r_i * d (mod q)

Substitute the leaked form of k_i:

r_i * d - s_i * delta_i ≡ s_i * leaked_i * 2^t - h_i (mod q)

Now the unknowns are:

• the private key d
• a set of small corrections delta_i

That is the lattice hook.

Minimal starter code:

from sage.all import Matrix, ZZ

def build_ecdsa_partial_nonce_lattice(q, rs, ss, hs, leaked, t):
    n = len(rs)
    M = Matrix(ZZ, n + 2, n + 2)

    for i in range(n):
        M[i, i] = q

    for i in range(n):
        M[n, i] = ss[i]
        M[n + 1, i] = (hs[i] - ss[i] * leaked[i] * (1 << t)) % q

    M[n, n] = 1
    M[n + 1, n + 1] = q // (1 << t)
    return M

What to do next:

1. build the lattice 2. run LLL 3. inspect short rows for a plausible d 4. verify d against all signatures 5. if one or two bits are off, brute-force the remaining uncertainty

When this works best: many signatures, enough leaked bits per nonce, and a single long-term signing key shared across all samples.

---

LCG and Truncated Output as a Lattice Problem (X-MAS CTF 2018, FwordCTF 2020)

Pattern: internal state follows an affine recurrence, but you only see:

• high bits
• low bits
• several states with unknown parameters
• several consecutive outputs plus a small hidden correction

Typical examples:

• unknown seed, known modulus
• known modulus, known a, known b, only top bits of outputs
• unknown a, unknown b, several exact or truncated outputs

The trick is to rewrite:

state_i = observed_i * 2^t + hidden_i

where hidden_i is small. Then the recurrence becomes a modular linear relation in those small hidden values.

When to use:

• high-bit leakage from LCG states
• recurrence modulo a large prime
• multiple consecutive outputs
• exact algebra seems messy but every step differs only by a small hidden remainder

Key insight: truncated-state recovery is often just HNP wearing different clothes. If the unknown carries per row are small enough, the lattice will expose them.

Minimal truncated-LCG workflow

Suppose:

x_{i+1} = a*x_i + b (mod m)

but the service leaks only the high bits:

y_i = x_i >> t

Then write:

x_i = y_i * 2^t + z_i

where z_i is the hidden low-bit part and is small.

Plugging into the recurrence gives:

y_{i+1} * 2^t + z_{i+1} ≡ a*(y_i * 2^t + z_i) + b (mod m)

Rearrange:

z_{i+1} - a*z_i ≡ a*y_i*2^t + b - y_{i+1}*2^t (mod m)

Now the unknowns are the small z_i. That is exactly the kind of bounded modular relation lattices like.

Minimal starter code:

from sage.all import Matrix, ZZ

def build_truncated_lcg_lattice(m, a, b, ys, t):
    n = len(ys) - 1
    M = Matrix(ZZ, n + 1, n + 1)

    for i in range(n):
        M[i, i] = m

    for i in range(n):
        rhs = (a * ys[i] * (1 << t) + b - ys[i + 1] * (1 << t)) % m
        M[n, i] = rhs

    M[n, n] = 1 << t
    return M

What to do next:

1. use several consecutive outputs 2. run LLL 3. recover candidate low bits z_i 4. reconstruct full states x_i 5. verify the recurrence exactly

When this works best: modulus is known, leakage is consecutive, and the hidden low part is much smaller than the modulus.

---

LWE via Embedding and CVP (PlaidCTF 2016, Aero CTF 2020)

Pattern: given A, b, modulus q, and the promise:

b = A*s + e (mod q)

where:

• s is small or sparse
• e is small

This is the standard LWE shape.

Immediate checks:

• are coefficients of s in {-1,0,1} or a tiny range?
• is the error noticeably smaller than q?
• does the challenge give many rows and only a few columns?
• does solving over the integers almost work except for modular wraparound?

Embedding-style lattice

from sage.all import Matrix, ZZ, identity_matrix, zero_matrix, block_matrix

def lwe_embedding(A, q):
    m, n = A.nrows(), A.ncols()
    top = block_matrix([[q * identity_matrix(m), zero_matrix(ZZ, m, n)]])
    bottom = block_matrix([[A.transpose(), identity_matrix(n)]])
    return block_matrix([[top], [bottom]])

Then:

• reduce the basis
• use Babai / nearest-plane on the target
• recover the short secret / error pair

For ternary or sparse secrets

After CVP:

• map near-zero values back into {-1,0,1}
• test both endian choices
• test both "row vectors" and "column vectors" conventions

Key insight: many CTF LWE instances are intentionally below the "real cryptography" hardness line. The challenge is usually not defeating production-grade LWE, but noticing that the secret or error was chosen tiny enough for LLL + Babai to work.

---

Ring-LWE / Module-LWE Recognition Notes (PlaidCTF 2016, DiceCTF 2022)

You should suspect Ring-LWE / Module-LWE when:

• objects are polynomials modulo x^n ± 1
• multiplication is cyclic or negacyclic convolution
• samples look like (a(x), b(x)=a(x)s(x)+e(x))
• coefficients are reduced modulo q

In many CTFs, the intended shortcut is not a full Ring-LWE attack, but one of these:

• coefficients are tiny enough to lift to integers directly
• the ring structure decouples into easier scalar problems
• the service leaks enough evaluations to turn the problem into plain LWE
• one representation bug breaks the intended hardness

Practical advice:

• first try to flatten the polynomial problem into vectors
• test coefficient embedding before chasing deeper algebra
• check whether NTT / inverse NTT is used incorrectly
• check sign conventions, endian order, and whether coefficients were centered into [-q/2, q/2]

Flattening Ring-LWE to plain LWE

from sage.all import Matrix, ZZ, vector

def ring_lwe_to_matrix(a_poly, n, q):
    """Flatten a(x) in Z_q[x]/(x^n+1) to its negacyclic rotation matrix."""
    coeffs = list(a_poly) + [0] * (n - len(list(a_poly)))
    rows = []
    for i in range(n):
        row = [0] * n
        for j in range(n):
            idx = (i - j) % n
            sign = -1 if (i - j) < 0 and ((i - j) % n) != 0 else 1
            # negacyclic: x^n = -1
            if j <= i:
                row[j] = coeffs[i - j]
            else:
                row[j] = -coeffs[n + i - j]
        rows.append(row)
    return Matrix(ZZ, rows)
# After flattening, treat as plain LWE: b_vec = A_mat * s_vec + e_vec (mod q)

Key insight: most Ring-LWE / Module-LWE CTF challenges are weakened by implementation mistakes, tiny errors, or over-structured secrets. Flatten to plain LWE first and check whether standard lattice tools solve it before pursuing ring-specific attacks.

---

Orthogonal Lattices: HSSP / AHSSP Style Recovery (zer0pts CTF 2022)

Pattern: you do not directly know the secret matrix or subset, but you can construct vectors that should be orthogonal to it modulo M or p.

This often appears in hidden-subset style problems:

• recover a hidden binary matrix
• recover a hidden low-weight subspace
• reconstruct unknown rows from modular inner-product relations

Core workflow:

1. build a lattice whose short vectors represent orthogonal relations 2. reduce it 3. recover the orthogonal lattice 4. take the kernel / orthogonal complement 5. reduce again to expose the hidden binary or short basis

from sage.all import Matrix, ZZ, identity_matrix, block_matrix

def orthogonal_lattice_recovery(H, M):
    """Recover hidden binary basis from h = alpha * A (mod M).

    H: observed matrix (k x n) over Z_M
    M: modulus
    Returns: LLL-reduced orthogonal lattice whose kernel reveals A.
    """
    k, n = H.nrows(), H.ncols()
    # Build lattice: [M*I_k | 0; H^T | I_n]
    top = block_matrix([[M * identity_matrix(k), Matrix(ZZ, k, n)]])
    bot = block_matrix([[H.change_ring(ZZ).transpose(), identity_matrix(n)]])
    L = block_matrix([[top], [bot]])
    L_reduced = L.LLL()
    # Short rows in the bottom-right block are orthogonal to the hidden basis
    return L_reduced

When to use:

• challenge gives h = αA or affine variants of that relation
• unknown matrix entries are in {0,1} or another tiny alphabet
• direct solving fails because the structure lives in an unknown subspace

Key insight: in these problems, the shortest vectors are not the answer itself. They are the doorway to the answer: first recover the orthogonal space, then turn back and reconstruct the hidden basis.

---

Subset Sum / Knapsack via Lattice Reduction (HITCON CTF 2017, BackdoorCTF 2023)

Pattern: recover a binary vector x_i ∈ {0,1} such that:

sum(a_i * x_i) = target

This is the classic subset-sum / knapsack lattice setup.

Use it when:

• the instance is intentionally low-density
• the hidden vector is binary
• direct meet-in-the-middle is still too large

Skeleton:

from sage.all import Matrix, ZZ

def knapsack_lattice(weights, target):
    n = len(weights)
    M = Matrix(ZZ, n + 1, n + 1)
    for i in range(n):
        M[i, i] = 1
        M[i, n] = weights[i]
    M[n, n] = -target
    return M

Then:

• run LLL
• look for a row whose last coordinate is 0
• check whether the remaining coordinates are in {0,1} or {−1,0,1}

Key insight: the lattice is built so that the correct subset produces a vector with an abnormally small final coordinate. In easy CTF instances, that vector survives reduction.

---

Common Failure Modes

• Wrong scaling: one coordinate dominates the basis and hides the short vector.
• Wrong centering: values should be mapped to [-q/2, q/2], not kept in [0, q).
• Wrong orientation: rows vs columns are swapped.
• Too few samples: the lattice exists, but not enough equations pin the secret down.
• Noise too large: LLL is not enough; try BKZ, better scaling, or a different embedding.
• Mistaken problem type: what looks like LWE may actually be plain linear algebra, CRT, or a bugged encoding problem.
• Forgot brute-force finish: lattice often gets you "almost correct"; the last few bits or signs may still need a tiny brute force.

---

Quick Checklist Before You Commit to Lattices

• Can I write the unknown as "small secret" or "small error"?
• Is there a bounded term that should make one vector much shorter than random?
• Did I try centering coefficients?
• Did I test both row/column conventions?
• Did I try LLL first before building something more exotic?
• If LLL almost works, did I try BKZ or Babai?
• If the instance is polynomial-based, did I first flatten it into coefficient vectors?

If most answers are "yes", the challenge is very likely meant to be solved with lattice reduction.

CTF Crypto - Modern Cipher Attacks (Continued)

Hash-based attacks, protocol-level exploits, ECB oracles, Rabin/RSA parity attacks, and specialized cipher weaknesses. For core AES/CBC/padding oracle techniques, see modern-ciphers.md. For stream cipher attacks (LFSR, RC4, XOR), see stream-ciphers.md.

Table of Contents

• Blum-Goldwasser Bit-Extension Oracle (PlaidCTF 2013)
• Hash Length Extension Attack (PlaidCTF 2014)
• Compression Oracle / CRIME-Style Attack (BCTF 2015)
• Hash Function Time Reversal via Cycle Detection (BSidesSF 2025)
• OFB Mode with Invertible RNG Backward Decryption (BSidesSF 2026)
• Weak Key Derivation via Public Key Hash XOR (BSidesSF 2026)
• HMAC-CRC Linearity Attack (Boston Key Party 2016)
• DES Weak Keys in OFB Mode (Boston Key Party 2016)
• SRP (Secure Remote Password) Protocol Bypass via Modular Arithmetic (ASIS CTF Finals 2016)
• Modified AES S-Box Brute-Force Recovery (H4ckIT CTF 2016)
• Square Attack on Reduced-Round AES (0CTF 2016)
• AES-ECB Byte-at-a-Time Chosen Plaintext (ABCTF 2016)
• AES-ECB Cut-and-Paste Block Manipulation (NDH Quals 2016)
• AES-CBC IV Bit-Flip Authentication Bypass (Google CTF 2016)
• Rabin Cryptosystem LSB Parity Oracle (PlaidCTF 2016)
• PBKDF2 Pre-Hash Bypass for Long Passwords (BackdoorCTF 2016)
• MD5 Multi-Collision via Fastcol (BackdoorCTF 2016)

See modern-ciphers-3.md for custom hash reversal, CRC32 brute-force, noisy RSA oracle, sponge collisions, CBC IV forgery, padding oracle bit-flip, SPN S-box intersection, AES-CFB IV recovery, three-round XOR, Unicode side channel, SHA-256 basis attack, and HMAC key recovery.

---

Blum-Goldwasser Bit-Extension Oracle (PlaidCTF 2013)

Pattern: Exploit a decryption oracle for Blum-Goldwasser-style encryption by extending ciphertext length by one bit per query to leak plaintext via parity.

Key insight: Extend ciphertext by one bit (L+1), shift ciphertext left (c << 1), and submit a modified y value. The oracle reveals the LSB (parity) of each decrypted chunk. The squaring sequence y = pow(y, 2, N) can be manipulated to produce valid extended ciphertexts the server hasn't seen.

# Iterative plaintext recovery via bit-extension
for i in range(msg_length):
    extended_c = original_c << 1        # Shift ciphertext left by 1
    new_y = pow(original_y, 2, N)       # Advance squaring sequence
    response = oracle(extended_c, new_y, msg_length + 1)
    leaked_bit = response & 1           # LSB reveals one plaintext bit
    plaintext_bits.append(leaked_bit)
    original_y = new_y

When to use: Blum-Goldwasser or BBS-based (Blum Blum Shub) encryption with a decryption oracle that accepts variable-length ciphertexts. The parity leak accumulates one bit per query.

---

Hash Length Extension Attack (PlaidCTF 2014)

Pattern: Server computes hash(SECRET || user_data) using MD5, SHA-1, or SHA-256 (Merkle-Damgard constructions). Given a valid hash and the original data, extend it with arbitrary appended data and compute a valid hash — without knowing the secret.

# Using HashPump (install: apt install hashpump)
hashpump --keylength 8 \
  --signature 'ef16c2bffbcf0b7567217f292f9c2a9a50885e01e002fa34db34c0bb916ed5c3' \
  --data 'original_data' \
  --additional ';admin=true'
# Outputs: new_signature and new_data (with padding bytes)

# Python: hashpumpy
import hashpumpy
new_hash, new_data = hashpumpy.hashpump(
    original_hash, original_data, append_data, secret_length
)

Key insight: Merkle-Damgard hashes (MD5, SHA-1, SHA-256) process data in blocks, and the hash output IS the internal state. Given H(secret || msg), you can compute H(secret || msg || padding || extension) without knowing secret — just initialize the hash state from the known output and continue hashing. Only HMAC (H(K XOR opad || H(K XOR ipad || msg))) is immune. If the secret length is unknown, try lengths 1-32.

See also [ctf-web/auth-infra.md — Hash Length Extension Attack (ASIS CTF 2017)](../ctf-web/auth-infra.md#hash-length-extension-attack-asis-ctf-2017) for the same primitive applied to a web auth token bypass.

---

Compression Oracle / CRIME-Style Attack (BCTF 2015)

Pattern: Server compresses plaintext (LZW, zlib, etc.) before encrypting. By observing ciphertext length changes with chosen plaintexts, leak the unknown plaintext character-by-character.

import base64

def oracle(plaintext):
    """Send chosen plaintext, get ciphertext length."""
    resp = send_to_server(plaintext)
    return len(base64.b64decode(resp))

# Baseline: empty input
base_len = oracle("")

# Recover secret byte-by-byte
known = ""
for pos in range(secret_length):
    for c in string.printable:
        candidate = known + c
        length = oracle(candidate)
        if length <= base_len + len(known):  # Compressed = match
            known += c
            break

Key insight: Compression algorithms (LZW, DEFLATE, zlib) replace repeated sequences with back-references. If SALT + user_input is compressed before encryption, sending input that matches part of the salt produces shorter ciphertext (the match compresses). This is the same class as CRIME (TLS), BREACH (HTTP), and HEIST attacks. The oracle is ciphertext length.

---

Hash Function Time Reversal via Cycle Detection (BSidesSF 2025)

When a system uses iterated hashing as a "time" function (state_t = H(state_{t-1})), reverse time by exploiting the finite cycle structure:

1. Detect cycle: Use Floyd's tortoise-and-hare or Brent's algorithm to find cycle length L 2. Compute backward steps: To go from time T to earlier time T_goal: iterate forward (L - (T - T_goal)) % L steps

import hashlib

def hash_step(state):
    return hashlib.md5(state).digest()[:8]  # Truncated hash

def find_cycle(start):
    """Brent's cycle detection: returns (cycle_length, start_of_cycle)"""
    power = lam = 1
    tortoise = start
    hare = hash_step(start)
    while tortoise != hare:
        if power == lam:
            tortoise = hare
            power *= 2
            lam = 0
        hare = hash_step(hare)
        lam += 1
    # lam = cycle length; find cycle start
    tortoise = hare = start
    for _ in range(lam):
        hare = hash_step(hare)
    mu = 0
    while tortoise != hare:
        tortoise = hash_step(tortoise)
        hare = hash_step(hare)
        mu += 1
    return lam, mu  # cycle_length, cycle_start_offset

# Reverse from T_known to T_goal
cycle_len, _ = find_cycle(known_state)
forward_steps = (cycle_len - (t_known - t_goal)) % cycle_len
state = known_state
for _ in range(forward_steps):
    state = hash_step(state)
# state is now the value at t_goal

Key insight: For truncated hashes (e.g., MD5 -> 64 bits), the expected cycle length is ~2^32, making cycle detection feasible. Going "backward" N steps is equivalent to going forward (cycle_length - N) steps. Assumes the target state is within the main cycle, not on a tail.

---

OFB Mode with Invertible RNG Backward Decryption (BSidesSF 2026)

Pattern (randcrypt): A custom block cipher uses OFB (Output Feedback) mode with a homemade RNG as the keystream generator. The last plaintext block is known (zero padding), leaking one RNG state. If the RNG's state transition function is invertible (bijective), all previous states can be recovered by running the RNG backwards, decrypting the entire ciphertext from the end to the beginning.

def rng_forward(state):
    """Custom RNG state transition (from challenge)."""
    # Example: linear congruential or reversible mixing
    return (state * A + B) % M

def rng_inverse(state):
    """Inverted RNG — recover previous state."""
    return ((state - B) * pow(A, -1, M)) % M

# Last block is zero-padded → ciphertext XOR 0 = keystream = RNG state
leaked_state = int.from_bytes(ciphertext_blocks[-2], 'big')

# Decrypt backwards
state = leaked_state
plaintext_blocks = []
for i in range(len(ciphertext_blocks) - 3, -1, -1):
    state = rng_inverse(state)
    pt = xor_bytes(ciphertext_blocks[i], state.to_bytes(block_size, 'big'))
    plaintext_blocks.insert(0, pt)

Key insight: OFB mode decouples encryption from the plaintext — the keystream is deterministic from the initial state. If ANY block's plaintext is known (padding, headers, magic bytes), the corresponding RNG state is leaked. An invertible RNG then reveals ALL states. Always check if the RNG transition function has a mathematical inverse.

When to recognize: Custom OFB/CTR mode with a non-standard PRNG. Look for: (1) XOR-based encryption, (2) a state-update function that's bijective (no information loss), (3) predictable plaintext in any block position. Files with known padding (PKCS#7 zero-fill, null-terminated strings) are ideal leak points.

---

Weak Key Derivation via Public Key Hash XOR (BSidesSF 2026)

Pattern (ran-somewhere): Hybrid RSA+AES encryption where the AES key is derived as SHA256(DER_encoded_public_key) XOR seed, with the seed hardcoded or predictable. Since the public key is public, the AES key is fully recoverable without the RSA private key.

from Crypto.PublicKey import RSA
from Crypto.Cipher import AES
from hashlib import sha256

# Public key is available
pubkey = RSA.import_key(open("public.pem").read())
der_bytes = pubkey.export_key("DER")

# Seed from challenge (hardcoded/predictable)
seed = b'BSidesSFCTF2026!'

# Derive AES key the same way the encryptor did
key_hash = sha256(der_bytes).digest()
aes_key = bytes(a ^ b for a, b in zip(key_hash, seed.ljust(32, b'\x00')))

# Decrypt
ct = open("flag.enc", "rb").read()
iv, ct_body = ct[:16], ct[16:]
cipher = AES.new(aes_key, AES.MODE_CBC, iv)
plaintext = cipher.decrypt(ct_body)

Key insight: Key derivation that incorporates only public information (public keys, known constants) provides zero security regardless of the hash function used. The "hybrid" design creates a false sense of security — RSA protects nothing if the AES key doesn't depend on the RSA private key.

When to recognize: Challenge provides both a public key AND an encrypted file, but no private key or ciphertext for RSA. Look for key derivation code that hashes the public key, uses the public key's modulus/exponent as seed material, or XORs with a constant.

---

HMAC-CRC Linearity Attack (Boston Key Party 2016)

Pattern: HMAC constructed with CRC as the hash function is completely broken because CRC is linear over GF(2). The key is directly recoverable from a single message-MAC pair via polynomial arithmetic over GF(2^64).

# CRC is linear: CRC(a XOR b) = CRC(a) XOR CRC(b)
# HMAC-CRC(key, msg) = CRC(key_opad || CRC(key_ipad || msg))
# Rewrite as polynomial in GF(2): K = known_terms * inverse(x^(128+M) + x^128) mod CRC_POLY

Key insight: CRC's linearity over GF(2) means HMAC-CRC provides zero security. Always verify the underlying hash function is non-linear before trusting HMAC.

---

DES Weak Keys in OFB Mode (Boston Key Party 2016)

Pattern: DES has 4 weak keys where E(E(P,K),K) = P (encryption is self-inverse). In OFB (Output Feedback) mode this causes the keystream to cycle with period 2: even blocks XOR with IV, odd blocks with E(IV,K). Reduces to a 16-byte repeating XOR key.

# DES weak keys: 0x0000000000000000, 0xFFFFFFFFFFFFFFFF,
#                0xE1E1E1E1F0F0F0F0, 0x1E1E1E1E0F0F0F0F
# OFB with weak key: keystream = [IV, E(IV,K), IV, E(IV,K), ...]
# Recovery: try all 4 weak keys; or treat as 16-byte repeating XOR

Key insight: DES weak keys cause OFB keystream to cycle with period 2. When you see DES+OFB, always try the 4 weak keys first.

---

Square Attack on Reduced-Round AES (0CTF 2016)

Pattern: 4-round AES is vulnerable to the square (integral) attack. Choose 256 plaintexts differing in one byte (a "lambda set"). After 3 rounds, the XOR sum at any byte position equals 0. Guess one byte of the last round key and partially decrypt -- if XOR sum is 0, the guess is correct.

# For each byte position in the last round key:
for candidate in range(256):
    xor_sum = 0
    for ct in ciphertexts:
        xor_sum ^= inv_sub_bytes(ct[pos] ^ candidate)
    if xor_sum == 0:
        key_byte = candidate  # correct guess
# Reduces 2^128 key recovery to ~16 * 256 = 4096 operations

Key insight: Integral cryptanalysis exploits the "balanced" property (XOR-sum = 0) that propagates through AES rounds. Effective against 4-round AES; 5+ rounds require more sophisticated variants.

---

SRP (Secure Remote Password) Protocol Bypass via Modular Arithmetic (ASIS CTF Finals 2016)

SRP implementations that only check A != 0 and A != N can be bypassed by sending A = 2*N, causing the server to compute a zero session key.

from hashlib import sha256
import hmac

# SRP protocol: server computes session key from A (client's public value)
# S = (A * v^u) ^ b mod N
# If A = 2*N: S = (2*N * v^u) ^ b mod N = 0 (since 2*N mod N = 0)

N = server_modulus
# Send A = 2*N (bypasses checks for A != 0 and A != N)
A_malicious = 2 * N

# Server computes S = 0, so session key K = SHA256(0)
K = sha256(b'\x00').digest()

# Now compute valid HMAC proof with known K
proof = hmac.new(K, salt, sha256).hexdigest()

Key insight: SRP implementations must validate A % N != 0, not just A != 0 and A != N. Sending A = k*N for any integer k forces the shared secret to zero, allowing authentication without knowing the password.

---

Modified AES S-Box Brute-Force Recovery (H4ckIT CTF 2016)

AES implementation with a custom S-Box created by swapping 3 elements of the standard S-Box. Brute-force all C(256,3) * 2 = 5,527,040 possible permutations.

// Three elements swapped from standard AES S-Box
// Total permutations: C(256,3) * 2 = ~5.5 million (feasible to brute-force)
#include <openssl/aes.h>

void bruteforce_sbox(uint8_t ciphertext[], uint8_t key[], int ct_len) {
    uint8_t standard_sbox[256]; // standard AES S-Box
    // Try all 3-element swaps
    for (int i = 0; i < 256; i++)
        for (int j = i+1; j < 256; j++)
            for (int k = j+1; k < 256; k++) {
                // Swap pairs: (i,j), (i,k), (j,k)
                uint8_t sbox[256];
                memcpy(sbox, standard_sbox, 256);
                swap(sbox[i], sbox[j]); // try each 2-element swap from the triple
                // Decrypt and check for valid plaintext
                if (try_decrypt_with_sbox(sbox, ciphertext, key, ct_len))
                    return; // found it
            }
}

Key insight: When a custom AES S-Box differs from standard by only a few element swaps, the search space is small enough to brute-force. For 3 swapped elements: C(256,3) permutation groups times the swap combinations within each group.

---

AES-ECB Byte-at-a-Time Chosen Plaintext (ABCTF 2016)

Pattern (Encryption Service): Server encrypts user_input || secret_suffix under AES-ECB. Recover the secret suffix one byte at a time by controlling the input length.

1. Send inputs of decreasing length to push one unknown byte into a known block position 2. For each position, try all 256 byte values and compare the encrypted block:

from pwn import *
import cryptanalib as ca  # FeatherDuster's cryptanalib

def oracle(pt):
    """Send plaintext, receive ECB-encrypted ciphertext."""
    r = remote('target', 7765)
    r.recvuntil('Send me some hex-encoded data to encrypt:\n')
    r.sendline(pt.hex())
    r.recvuntil('Here you go:')
    ct = bytes.fromhex(r.recvline().strip().decode())
    r.close()
    return ct

# Automated byte-at-a-time recovery
flag = ca.ecb_cpa_decrypt(oracle, block_size=16, verbose=True)
print(flag)

Manual approach without library:

block_size = 16
known = b''

for i in range(len(secret)):
    # Pad so next unknown byte is at end of a block
    pad_len = block_size - 1 - (len(known) % block_size)
    pad = b'A' * pad_len

    # Get target block
    target_ct = oracle(pad)
    target_block_idx = (pad_len + len(known)) // block_size
    target_block = target_ct[target_block_idx*16:(target_block_idx+1)*16]

    # Try all 256 byte values
    for byte_val in range(256):
        test = pad + known + bytes([byte_val])
        test_ct = oracle(test)
        if test_ct[target_block_idx*16:(target_block_idx+1)*16] == target_block:
            known += bytes([byte_val])
            break

Key insight: ECB mode encrypts identical plaintext blocks to identical ciphertext blocks. By controlling the prefix length, the attacker shifts one unknown byte at a time to a position where it completes a known block prefix. Comparing the target ciphertext block against all 256 possibilities recovers each byte in at most 256 queries. Total queries: ~256 * secret_length. Tool: FeatherDuster's cryptanalib.ecb_cpa_decrypt() automates this completely.

---

AES-ECB Cut-and-Paste Block Manipulation (NDH Quals 2016)

Pattern (Toil33t): Server encrypts JSON session data in AES-ECB mode. Fields like is_admin: false span predictable block boundaries. Construct chosen plaintext blocks via registration, then splice ciphertext blocks to change false to true.

1. Detect ECB mode: register with repeating username (e.g., 'A' * 64), look for identical ciphertext blocks 2. Map block boundaries by varying username length until block count changes 3. Determine field ordering by independently varying username and email lengths 4. Craft target block containing true by aligning it at a block boundary via padding:

# Align "true" at start of a block using space padding (JSON ignores whitespace)
# Original:  {"username": "AA", "is_admin": false, "email": ""}
# Target:    {"username": "AA", "is_admin":            true, "email": ""}
#                                              ^-- 16-byte block boundary

# Get the "            true" block from:
username = "AAA" + " " * 12 + "true"
# Extract block 2 of the resulting ciphertext

# Get prefix blocks from a short username
# Get suffix block from a padded username
# Concatenate: prefix_blocks + true_block + suffix_block

Key insight: AES-ECB encrypts each 16-byte block independently with no chaining. Identical plaintext blocks produce identical ciphertext blocks, allowing block-level cut-and-paste. JSON's tolerance for extra whitespace enables block alignment without breaking parsing. The attack requires: (a) detecting ECB via repeated blocks, (b) mapping field layout via length probing, (c) crafting and splicing blocks.

---

AES-CBC IV Bit-Flip Authentication Bypass (Google CTF 2016)

Pattern (Eucalypt Forest): Server encrypts JSON session blob under AES-CBC and returns both IV and ciphertext as a cookie. No integrity check (no MAC/HMAC). Flip bits in the IV to change the first plaintext block.

1. Register with username one bit away from target (e.g., ` dmin ` instead of admin` — flip LSB of 'a') 2. Identify the IV byte position corresponding to the target character in the first block 3. Flip the same bit in the IV byte — XOR propagates directly to the plaintext:

import binascii
cookie = binascii.unhexlify(auth_cookie)
iv = bytearray(cookie[:16])
ciphertext = cookie[16:]

# Flip LSB of byte at position where 'a'/'`' appears in first block
# Position depends on JSON structure: {"username":"`dmin"}
# 'a' (0x61) vs '`' (0x60) differ only in bit 0
target_pos = 13  # position of first char of username in block
iv[target_pos] ^= 0x01

forged = binascii.hexlify(bytes(iv) + ciphertext)

Key insight: AES-CBC decryption XORs the previous ciphertext block (or IV for block 0) with the AES-decrypted block. Flipping bit i in the IV flips bit i in the first plaintext block with no other side effects. This only works when the server performs no integrity verification (no HMAC, AEAD, or authenticated encryption).

---

Rabin Cryptosystem LSB Parity Oracle (PlaidCTF 2016)

Pattern (rabit): Server encrypts flag with the Rabin cryptosystem (c = m^2 mod n) and provides an LSB oracle — for any ciphertext, it returns the least significant bit of the decrypted plaintext. Binary search recovers the full plaintext in log2(n) queries.

from Crypto.Util.number import long_to_bytes

def lsb_oracle_attack(enc_flag, N, oracle_fn):
    """Recover plaintext from Rabin/RSA LSB oracle via binary search."""
    lower = 0
    upper = N
    C = enc_flag
    # Rabin: encrypt(2,N) = 4; multiplying ciphertext by 4 doubles plaintext
    e2 = pow(2, 2, N)  # For Rabin; use pow(2, e, N) for RSA

    for i in range(N.bit_length()):
        C = (e2 * C) % N  # Multiply plaintext by 2
        lsb = oracle_fn(C)
        if lsb == 1:
            # 2*m > N (odd remainder after mod), increase lower bound
            lower = (upper + lower) // 2
        else:
            # 2*m < N (even remainder), decrease upper bound
            upper = (upper + lower) // 2
        # Progressive decryption visible:
        print(long_to_bytes(upper))
    return upper

Key insight: Rabin (and textbook RSA) are multiplicatively homomorphic: multiplying ciphertext by 2^e mod N doubles the plaintext mod N. Since N is odd, doubling causes a modular wraparound iff the plaintext exceeds N/2, which changes the LSB parity. This creates a binary search: each oracle query halves the candidate range, recovering the full plaintext in exactly log2(N) queries (~1024 for RSA-1024).

---

PBKDF2 Pre-Hash Bypass for Long Passwords (BackdoorCTF 2016)

Pattern (Mindblown): PBKDF2 (and HMAC generally) pre-hashes passwords longer than the hash block size (64 bytes for SHA-1/SHA-256). If the target password exceeds 64 bytes, PBKDF2(password) equals PBKDF2(SHA1(password)), enabling authentication with the hash instead of the original password.

import hashlib

original_password = "complexPasswordWhichContainsManyCharactersWithRandomSuffixeghjrjg"
# len > 64, so HMAC pre-hashes it
equivalent = hashlib.sha1(original_password.encode()).digest()
# Login with equivalent — PBKDF2 produces the same derived key

Key insight: HMAC's inner construction is H((K XOR ipad) || message). When the key (password) exceeds the hash block size, HMAC first reduces it via K = H(password). This means HMAC(long_password, ...) equals HMAC(H(long_password), ...). Any system using PBKDF2/HMAC with a !== identity check after hash comparison is vulnerable when passwords exceed 64 bytes. This is a HMAC specification behavior, not an implementation bug.

---

MD5 Multi-Collision via Fastcol (BackdoorCTF 2016)

Pattern (Forge): Generate 2^k files with identical MD5 hashes by chaining fastcol (Marc Stevens' tool). Each run produces two suffixes (A, B) that when appended yield the same MD5. Chain 3 runs to produce 8 collisions:

[prefix][suffix1A][suffix2A][suffix3A]  \
[prefix][suffix1A][suffix2A][suffix3B]   |
[prefix][suffix1A][suffix2B][suffix3A]   |-- all have same MD5
[prefix][suffix1A][suffix2B][suffix3B]   |
[prefix][suffix1B][suffix2A][suffix3A]   |
[prefix][suffix1B][suffix2B][suffix3B]  /

# Install: git clone https://github.com/cr-marcstevens/hashclash
# Generate one collision pair (~minutes on modern CPU):
./fastcol -o suffix1A.bin suffix1B.bin < prefix.bin
# Chain: append suffix1A to prefix, run fastcol again for suffix2A/2B, etc.

Key insight: MD5 collision generation is practical with fastcol (~minutes per pair). Because MD5 uses Merkle-Damgard construction, collisions compose: if H(A||X) == H(A||Y), then H(A||X||Z) == H(A||Y||Z) for any suffix Z. Chaining k collision pairs produces 2^k files with identical MD5. For CRC32 collisions, append bytes after PNG IEND chunk (parsers ignore trailing data) and brute-force the 4-byte CRC adjustment.

---

See modern-ciphers-3.md for custom hash reversal, CRC32 brute-force, noisy RSA LSB oracle, sponge collisions, CBC IV forgery + block truncation, padding oracle + bit-flip command injection, SPN S-box intersection, AES-CFB IV recovery, three-round XOR, Unicode decode side channel, SHA-256 basis attack, MAC forgery via XOR block cancellation, and bit-by-bit HMAC key recovery.