Ctf Crypto

CTF Cryptography

Quick reference for crypto CTF challenges. Each technique has a one-liner here; see supporting files for full details with code.

Prerequisites

Python packages (all platforms):

pip install pycryptodome z3-solver sympy gmpy2 hashpumpy fpylll py_ecc

Linux (apt):

apt install hashcat sagemath

macOS (Homebrew):

brew install hashcat

Manual install:

• SageMath — Linux: apt install sagemath, macOS: brew install --cask sage
• RsaCtfTool — git clone https://github.com/RsaCtfTool/RsaCtfTool (automated RSA attacks)

Note: gmpy2 requires libgmp — Linux: apt install libgmp-dev, macOS: brew install gmp.

Additional Resources

• classic-ciphers.md - Classic ciphers: Vigenere (+ Kasiski examination), Atbash, substitution wheels, XOR variants (+ multi-byte frequency analysis), deterministic OTP, cascade XOR, book cipher, OTP key reuse / many-time pad, variable-length homophonic substitution, grid permutation cipher keyspace reduction, image-based Caesar shift ciphers, XOR key recovery via file format headers
• modern-ciphers.md - Modern cipher attacks: AES (CFB-8, ECB leakage), CBC-MAC/OFB-MAC, padding oracle, S-box collisions, GF(2) elimination, LCG partial output recovery, affine cipher over composite modulus, AES-GCM with derived keys, AES-GCM nonce reuse (forbidden attack), Ascon-like reduced-round differential cryptanalysis, custom linear MAC forgery, CBC padding oracle (full block decryption), Bleichenbacher RSA PKCS#1 v1.5 padding oracle (ROBOT), birthday attack / meet-in-the-middle, CRC32 collision signature forgery, AES key recovery via byte-by-byte zeroing oracle, AES-CBC ciphertext forging via error-message decryption oracle
• modern-ciphers-2.md - Modern cipher attacks (Part 2): Blum-Goldwasser bit-extension oracle, hash length extension, compression oracle (CRIME-style), hash function time reversal via cycle detection, OFB mode invertible RNG backward decryption, weak key derivation via public key hash XOR, HMAC-CRC linearity attack, DES weak keys in OFB mode, SRP protocol bypass, modified AES S-Box brute-force, square attack on reduced-round AES, AES-ECB byte-at-a-time chosen plaintext, AES-ECB cut-and-paste block manipulation, AES-CBC IV bit-flip auth bypass, Rabin LSB parity oracle, PBKDF2 pre-hash bypass, MD5 multi-collision via fastcol
• modern-ciphers-3.md - Modern cipher attacks (Part 3): custom hash state reversal, CRC32 brute-force for small payloads, noisy RSA LSB oracle error correction, sponge hash MITM collision, CBC IV forgery + block truncation, padding oracle to CBC bitflip RCE, SPN S-box intersection attack, AES-CFB IV recovery from timestamp-seeded PRNG, three-round XOR protocol key cancellation, AES-CBC UnicodeDecodeError side-channel oracle, SHA-256 basis attack for XOR-aggregate hash bypass, custom MAC forgery via XOR block cancellation, HMAC key recovery via XOR+addition arithmetic
• stream-ciphers.md - Stream cipher attacks: LFSR (Berlekamp-Massey, correlation attack, known-plaintext, Galois vs Fibonacci, Galois tap recovery via autocorrelation), RC4 second-byte bias, XOR consecutive byte correlation
• rsa-attacks.md - RSA attacks: small e (cube root), common modulus, Wiener's, Pollard's p-1, Hastad's broadcast, Hastad with linear padding (Coppersmith), Franklin-Reiter related message (e=3), Coppersmith linearly-related primes, Fermat/consecutive primes, multi-prime, restricted-digit, Coppersmith structured primes, Manger oracle, polynomial hash
• rsa-attacks-2.md - RSA attacks (specialized): RSA p=q validation bypass, cube root CRT gcd(e,phi)>1, factoring from phi(n) multiple, multiplicative homomorphism signature forgery, weak keygen via base representation, RSA with gcd(e,phi)>1 exponent reduction, batch GCD shared prime factoring, partial key recovery from dp/dq/qinv, RSA-CRT fault attack, homomorphic decryption oracle bypass, small prime CRT decomposition, Montgomery reduction timing attack, Bleichenbacher low-exponent signature forgery, RSA signature bypass with e=1 and crafted modulus
• ecc-attacks.md - ECC attacks: small subgroup, invalid curve, Smart's attack (anomalous, with Sage code), fault injection, clock group DLP, Pohlig-Hellman, ECDSA nonce reuse, Ed25519 torsion side channel, DSA nonce reuse, DSA key recovery via MD5 collision on k-generation
• zkp-and-advanced.md - ZKP/graph 3-coloring, Z3 solver guide, garbled circuits, Shamir SSS, bigram constraint solving, race conditions, Groth16 broken setup, DV-SNARG forgery, KZG pairing oracle for permutation recovery, Shamir SSS reused polynomial coefficients
• prng.md - PRNG attacks (foundational): MT19937, MT float recovery via GF(2) magic matrix for token prediction, LCG, GF(2) matrix PRNG, V8 XorShift128+ Math.random state recovery via Z3, middle-square, deterministic RNG hill climbing, random-mode oracle, time-based seeds, C srand/rand synchronization via ctypes, password cracking, logistic map chaotic PRNG
• prng-attacks.md - PRNG attacks (CTF-era, 2017+): MT subset-sum seed recovery, MT19937 constraint propagation, Rule 86 cellular automaton reversal via Z3, Java LCG meet-in-the-middle partial modulo, LCG backward stepping via modular inverse, LFSR bit-fold ASCII parity, Z3 solve-time timing oracle, randcrack DSA k prediction, format-string PRNG seed offset, NTP-poisoned PRNG UUID XOR
• historical.md - Historical ciphers (Lorenz SZ40/42, book cipher implementation)
• advanced-math.md - Advanced mathematical attacks (isogenies, Pohlig-Hellman, baby-step giant-step (BSGS) for general DLP, LLL, Merkle-Hellman knapsack via LLL, Coppersmith, quaternion RSA, GF(2)[x] CRT, S-box collision code, LWE lattice CVP attack, affine cipher over non-prime modulus, introspective CRC via GF(2) linear algebra)
• lattice-and-lwe.md - Lattice attack triage and workflow: LLL/BKZ/Babai, HNP from partial or biased nonces, truncated LCG state recovery, LWE embedding and CVP, Ring-LWE / Module-LWE recognition, orthogonal lattices, subset sum / knapsack, and common failure modes
• exotic-crypto.md - Exotic algebraic structures (braid group DH / Alexander polynomial, monotone function inversion, tropical semiring residuation, Paillier cryptosystem, Hamming code helical interleaving, ElGamal universal re-encryption, FPE Feistel brute-force, icosahedral symmetry group cipher, Goldwasser-Micali replication oracle)
• exotic-crypto-2.md - Exotic algebraic structures (Part 2, 2017+): BB-84 QKD MITM, ElGamal trivial DLP (B=p-1), Paillier LSB oracle via homomorphic doubling, differential privacy noise cancellation, homomorphic encryption bit-extraction, ElGamal over matrices via Jordan normal form, OSS signature forgery via Pollard, Cayley-Purser decryption without private key, BIP39 partial mnemonic checksum brute force, Asmuth-Bloom CRT threshold recovery, Rabin with polynomial primes, LCG period detection, Vandermonde polynomial coefficient recovery

---

When to Pivot

• If the real blocker is understanding a binary, obfuscated client, or weird VM, switch to /ctf-reverse.
• If the challenge is mostly packet carving, disk recovery, or stego extraction before any decryption starts, switch to /ctf-forensics.
• If the task is just implementing an exploit against a vulnerable network service after the crypto part is solved, switch to /ctf-pwn or /ctf-web.
• If the crypto challenge involves adversarial ML, model extraction, or neural-network-based ciphers, switch to /ctf-ai-ml.
• If the challenge is really an encoding puzzle, esoteric cipher, or polyglot trick rather than true cryptanalysis, switch to /ctf-misc.

Quick Start Commands

# Identify cipher type
python3 -c "from Crypto.Util.number import *; n=<N>; print(f'bits={n.bit_length()}')"

# RSA quick check
python3 -c "from sympy import factorint; print(factorint(<n>))"  # Small factors?
openssl rsa -pubin -in key.pub -text -noout  # Extract n, e from PEM

# Quick factorization tools
python3 RsaCtfTool.py -n <n> -e <e> --uncipher <c>

# XOR analysis
python3 -c "from pwn import xor; print(xor(bytes.fromhex('<hex>'), b'flag{'))"

# Hash identification
hashid '<hash>'
hashcat --identify '<hash>'

# SageMath (for lattice/ECC)
sage -c "print(factor(<n>))"

Classic Ciphers

• Caesar: Frequency analysis or brute force 26 keys
• Vigenere: Known plaintext attack with flag format prefix; derive key from (ct - pt) mod 26. Kasiski examination for unknown key length (GCD of repeated sequence distances)
• Atbash: A<->Z substitution; look for "Abashed" hints in challenge name
• Substitution wheel: Brute force all rotations of inner/outer alphabet mapping
• Multi-byte XOR: Split ciphertext by key position, frequency-analyze each column independently; score by English letter frequency (space = 0x20)
• Cascade XOR: Brute force first byte (256 attempts), rest follows deterministically
• XOR rotation (power-of-2): Even/odd bits never mix; only 4 candidate states
• Weak XOR verification: Single-byte XOR check has 1/256 pass rate; brute force with enough budget
• Deterministic OTP: Known-plaintext XOR to recover keystream; match load-balanced backends
• OTP key reuse (many-time pad): C1 XOR C2 XOR known_P = unknown_P; crib dragging when no plaintext known
• Homophonic (variable-length): Multi-character ciphertext groups map to single plaintext chars. Find n-grams with identical sub-n-gram frequencies, replace with symbols, solve as monoalphabetic. See classic-ciphers.md.
• Grid permutation cipher: 5x5 grid with independent row/column permutations collapses keyspace to 5! x 5! = 14,400; brute-force in milliseconds. See classic-ciphers.md.
• Image-based Caesar shift: Pixel rows/columns shifted by per-strip offsets; compare original vs shifted image to extract ASCII-encoded flag from shift amounts. See classic-ciphers.md.
• Polybius square cipher: 5x5 grid maps letter pairs to plaintext; digits/coordinates encode positions. See classic-ciphers.md.
• XOR key recovery via file format headers: File claims to be PDF/PNG/ZIP but file reports "data". XOR first bytes against expected magic bytes to derive repeating key; extend using trailer structures (%%EOF, IEND marker). See classic-ciphers.md.

See classic-ciphers.md for full code examples.

Modern Cipher Attacks

• AES-ECB: Block shuffling, byte-at-a-time chosen-plaintext suffix recovery (256 queries per byte, tool: FeatherDuster ecb_cpa_decrypt); image ECB preserves visual patterns. ECB cut-and-paste: splice ciphertext blocks to forge JSON fields (e.g., is_admin: true). See modern-ciphers-2.md.
• AES-CBC: Bit flipping to change plaintext; padding oracle for decryption without key. IV bit-flip: flip specific bits in the IV to change first plaintext block (requires no MAC). See modern-ciphers-2.md.
• CBC IV forgery + block truncation: XOR IV bytes to change decrypted block 0; strip trailing ciphertext blocks (no length integrity in CBC). Forges authenticated tokens when MAC is embedded in the ciphertext. See modern-ciphers-2.md.
• Padding oracle to CBC bitflip RCE: Chain padding oracle (recover plaintext) with CBC bitflipping (inject shell metacharacters) for command injection via encrypted parameters. See modern-ciphers-2.md.
• AES-CFB-8: Static IV with 8-bit feedback allows state reconstruction after 16 known bytes
• CBC-MAC/OFB-MAC: XOR keystream for signature forgery: new_sig = old_sig XOR block_diff
• S-box collisions: Non-permutation S-box (len(set(sbox)) < 256) enables 4,097-query key recovery
• GF(2) elimination: Linear hash functions (XOR + rotations) solved via Gaussian elimination over GF(2)
• Padding oracle: Byte-by-byte decryption by modifying previous block and testing padding validity
• LFSR stream ciphers: Berlekamp-Massey recovers feedback polynomial from 2L keystream bits; correlation attack breaks combined generators with biased combining functions
• Galois LFSR tap recovery: XOR known file header (PNG/PDF/ZIP) with ciphertext to get keystream; split into N-bit windows, compute (state >> 1) XOR next_state for LSB=1 transitions to directly recover tap mask. Autocorrelation sliding finds correct length. See stream-ciphers.md.
• OFB with invertible RNG: Known plaintext in any block leaks RNG state; if state transition is bijective, run RNG backwards to decrypt all blocks. See modern-ciphers-2.md.
• Weak key derivation (public key hash XOR): AES key derived from SHA256(public_key) XOR seed is fully recoverable without private key; "hybrid" RSA+AES provides no security. See modern-ciphers-2.md.
• HMAC-CRC linearity: CRC is linear over GF(2), so HMAC-CRC key is recoverable from a single message-MAC pair via polynomial arithmetic. See modern-ciphers-2.md.
• DES weak keys in OFB: 4 DES weak keys make encryption self-inverse; OFB keystream cycles with period 2, reducing to 16-byte repeating XOR. See modern-ciphers-2.md.
• Square attack (reduced-round AES): 4-round AES broken by integral cryptanalysis: 256-plaintext lambda set, guess last round key bytes via XOR-sum = 0 distinguisher. See modern-ciphers-2.md.
• AES-GCM nonce reuse (forbidden attack): Same nonce = CTR keystream reuse + GHASH authentication key recovery via polynomial factoring over GF(2^128). Tool: nonce-disrespect. See modern-ciphers.md.
• SRP protocol bypass: Send A = 0 or A = n to force shared secret to 0, bypassing password verification entirely. See modern-ciphers-2.md.
• Modified AES S-Box brute force: Custom S-Box with only 16 unique outputs reduces key entropy; brute-force feasible key bytes per round. See modern-ciphers-2.md.
• Rabin LSB parity oracle: Rabin ciphertext c = m^2 mod n with LSB oracle enables binary search plaintext recovery in log2(n) queries via multiplicative homomorphism (c * 4 mod n doubles plaintext). See modern-ciphers-2.md.
• Noisy RSA LSB oracle error correction: When LSB oracle has sporadic errors, run standard attack then inspect output charset. Flip oracle results at error positions to correct remaining decryption. See modern-ciphers-2.md.
• PBKDF2 pre-hash bypass: HMAC pre-hashes keys > 64 bytes (SHA-1/SHA-256 block size). Login with SHA1(password) instead of password when original exceeds 64 bytes. See modern-ciphers-2.md.
• MD5 multi-collision (fastcol): Chain fastcol runs to produce 2^k files with identical MD5. Merkle-Damgard composition: collisions propagate through appended suffixes. See modern-ciphers-2.md.
• Custom hash state reversal: When iterative hash leaks intermediate states, isolate per-block hash values by inverting the state update equation, then brute-force each 4-byte block independently. See modern-ciphers-2.md.
• CRC32 brute-force (small payloads): ZIP CRC32 headers are unencrypted; brute-force content of small files (≤ 6 bytes) by checking all printable strings against stored CRC32. See modern-ciphers-2.md.
• Custom MAC forgery via XOR block cancellation: When MAC key stream repeats periodically, craft three queries where filler blocks cancel via XOR, forging any target command's MAC. See modern-ciphers-2.md.
• HMAC key recovery (XOR + addition arithmetic): Flawed HMAC using sha256((key XOR msg) + msg) leaks key bits: msg=0 gives sha256(key), msg=2^i matches iff key bit i is set. See modern-ciphers-2.md.
• AES-CBC ciphertext forging (error-message oracle): Server leaks decrypted bytes in error messages; send zero blocks to learn intermediate state, XOR with desired plaintext to forge ciphertext block-by-block. See modern-ciphers.md.

See modern-ciphers.md and modern-ciphers-2.md for full code examples.

RSA Attacks

• Small e with small message: Take eth root
• Common modulus: Extended GCD attack
• Wiener's attack: Small d
• Fermat factorization: p and q close together
• Pollard's p-1: Smooth p-1
• Hastad's broadcast: Same message, multiple e=3 encryptions
• Consecutive primes: q = next_prime(p); find first prime below sqrt(N)
• Multi-prime: Factor N with sympy; compute phi from all factors
• Restricted-digit primes: Digit-by-digit factoring from LSB with modular pruning
• Coppersmith structured primes: Partially known prime; f.small_roots() in SageMath
• Manger oracle (simplified): Phase 1 doubling + phase 2 binary search; ~128 queries for 64-bit key
• Manger on RSA-OAEP (timing): Python or short-circuit skips expensive PBKDF2 when Y != 0, creating fast/slow timing oracle. Full 3-step attack (~1024 iterations for 1024-bit RSA). Calibrate timing bounds with known-fast/known-slow samples.
• Polynomial hash (trivial root): g(0) = 0 for polynomial hash; craft suffix for msg = 0 (mod P), signature = 0
• Polynomial CRT in GF(2)[x]: Collect ~20 remainders r = flag mod f, filter coprime, CRT combine
• Affine over composite modulus: CRT in each prime factor field; Gauss-Jordan per prime
• RSA p=q validation bypass: Set p=q so server computes wrong phi=(p-1)^2 instead of p*(p-1); test decryption fails, leaking ciphertext
• RSA cube root CRT (gcd(e,phi)>1): When all primes ≡ 1 mod e, compute eth roots per-prime via nthroot_mod, enumerate CRT combinations (3^k feasible for small k)
• Factoring from phi(n) multiple: Any multiple of phi(n) (e.g., e*d-1) enables factoring via Miller-Rabin square root technique; succeeds with prob ≥ 1/2 per attempt
• Weak keygen via base representation: Primes p = kp*B + tp with small kp create mixed-radix structure in n; brute-force kp*kq (2^24) to factor
• RSA with gcd(e,phi)>1 (exponent reduction): Reduce e' = e/g, compute d' = e'^(-1) mod phi, partial decrypt to m^g, then take g-th root over integers
• RSA partial key recovery (dp/dq/qinv): CRT exponents from partial PEM leak allow O(e) prime recovery: iterate k, check if (dp*e-1)/k+1 is prime. See rsa-attacks-2.md.
• RSA-CRT fault attack: Single faulty CRT signature leaks factor via gcd(s^e - m, n) (Bellcore attack). See rsa-attacks-2.md.
• RSA homomorphic decryption bypass: Multiplicative homomorphism lets you decrypt c by querying oracle with c * r^e mod n, then dividing result by r. See rsa-attacks-2.md.
• RSA small prime CRT decomposition: When n has many small prime factors, factor with trial division, solve m mod p_i per prime, CRT combine. See rsa-attacks-2.md.
• Hastad broadcast with linear padding (Coppersmith): When each of e recipients applies a known affine transform a_i*m+b_i before encryption, CRT + Coppersmith small_roots recovers m. See rsa-attacks.md.
• RSA Montgomery reduction timing attack: Leaked extra-subtraction counts in Montgomery multiplication reveal private key bits MSB-to-LSB via statistical correlation. See rsa-attacks-2.md.
• Bleichenbacher low-exponent signature forgery: With e=3, forge PKCS#1 v1.5 signatures by computing cube root of a value with correct padding prefix; trailing garbage absorbs the remainder. See rsa-attacks-2.md.
• Franklin-Reiter related message attack (e=3): Two ciphertexts of m+pad1 and m+pad2 with known padding difference; polynomial GCD in Zmod(n) recovers m directly. See rsa-attacks.md.
• RSA signature bypass (e=1, crafted modulus): Verifier accepts user-supplied (n, e); set e=1 and n = sig - PKCS1_pad(msg) so pow(sig, 1, n) equals expected padded hash. See rsa-attacks-2.md.
• Coppersmith on linearly-related primes: When q ~ k*p for known k, approximate q ~ sqrt(k*n) and use Coppersmith small_roots on the error term. Generalizes Fermat factorization to non-consecutive primes. See rsa-attacks.md.

See rsa-attacks.md and advanced-math.md for full code examples.

Elliptic Curve Attacks

• Small subgroup: Check curve order for small factors; Pohlig-Hellman + CRT
• Invalid curve: Send points on weaker curves if validation missing
• Singular curves: Discriminant = 0; DLP maps to additive/multiplicative group
• Smart's attack: Anomalous curves (order = p); p-adic lift solves DLP in O(1)
• Baby-step giant-step (BSGS): General DLP in O(sqrt(n)) time/space. Combined with Pohlig-Hellman for smooth-order groups (all factors of p-1 or curve order are small). Sage: discrete_log(Mod(h,p), Mod(g,p)). See advanced-math.md.
• Fault injection: Compare correct vs faulty output; recover key bit-by-bit
• Clock group (x^2+y^2=1): Order = p+1 (not p-1!); Pohlig-Hellman when p+1 is smooth
• Isogenies: Graph traversal via modular polynomials; pathfinding via LCA
• ECDSA nonce reuse: Same r in two signatures leaks nonce k and private key d via modular arithmetic. Check for repeated r values
• Braid group DH: Alexander polynomial is multiplicative under braid concatenation — Eve computes shared secret from public keys. See exotic-crypto.md
• Ed25519 torsion side channel: Cofactor h=8 leaks secret scalar bits when key derivation uses key = master * uid mod l; query powers of 2, check y-coordinate consistency
• Tropical semiring residuation: Tropical (min-plus) DH is broken — residual b* = max(Mb[i] - M[i][j]) recovers shared secret directly from public matrices
• FPE Feistel brute-force: Format-preserving encryption with 16-bit round key is brute-forceable; remaining affine GF(2) mixing layer solved via Gaussian elimination. See exotic-crypto.md
• Icosahedral symmetry cipher: Dodecahedron face permutations form order-120 group; build lookup table of all permutations via API probing, match visible face patterns. See exotic-crypto.md
• Goldwasser-Micali replication oracle: GM encrypts one bit per ciphertext; replaying a single ciphertext value N times as an N-bit key forces all-zero or all-one key, distinguishable via hash oracle. 128 queries recover full AES key. See exotic-crypto.md
• DSA nonce reuse: Same r in two DSA signatures leaks private key via same formula as ECDSA nonce reuse. See ecc-attacks.md.
• DSA limited k brute force: When nonce k is small (e.g., 20-bit), brute-force all k values and check which yields the known r. See ecc-attacks.md.
• ECC shared prime GCD: Multiple ECC curves sharing a prime factor in their modulus; gcd(n1, n2) reveals the shared prime. See ecc-attacks.md.
• DSA key recovery via MD5 collision on k-generation: When nonce k derives from MD5(prefix+counter), use fastcoll to produce MD5 prefix collision forcing nonce reuse, then standard private key recovery. See ecc-attacks.md.
• BB-84 QKD MITM: Simulated BB-84 without authenticated classical channels allows full MITM -- independently negotiate keys with both parties, force constant value to one side. See exotic-crypto-2.md.

See ecc-attacks.md, advanced-math.md, and exotic-crypto.md for full code examples.

Lattice / LWE Attacks

• Quick triage: If the challenge gives modular linear equations plus a promise that the hidden quantity is small, sparse, biased, or only partially leaked, treat it as a lattice candidate first. See lattice-and-lwe.md.
• LLL / BKZ / Babai: Start with LLL, move to BKZ when LLL almost works, and use Babai after reduction for approximate CVP. See lattice-and-lwe.md.
• HNP from partial nonce leakage: Partial or biased ECDSA/Schnorr nonces often reduce to Hidden Number Problem lattices; normalize equations, isolate bounded error, reduce, then brute-force the last few bits if needed. See lattice-and-lwe.md.
• Truncated LCG state recovery: High-bit or low-bit leakage from affine recurrences is often just HNP in disguise; write each state as observed * 2^t + hidden and solve for the small hidden corrections. See lattice-and-lwe.md.
• LWE via CVP (Babai): Construct lattice from [q*I | 0; A^T | I], use fpylll CVP.babai to find closest vector, project to ternary {-1,0,1}. Watch for endianness mismatches between server description and actual encoding.
• Ring-LWE / Module-LWE recognition: Polynomial or negacyclic structure often looks scary but many CTFs weaken it with tiny coefficients, buggy representations, or enough leakage to flatten back into plain LWE. See lattice-and-lwe.md.
• Orthogonal lattices: Hidden subset or hidden subspace problems may need you to recover an orthogonal lattice first, then reconstruct the actual binary or short basis from its complement. See lattice-and-lwe.md.
• LLL for approximate GCD: Short vector in lattice reveals hidden factors
• Subset sum / knapsack: Binary knapsack and low-density subset-sum instances are still classic lattice territory; build the standard basis and look for a reduced row with a zero final coordinate. See lattice-and-lwe.md.
• Multi-layer challenges: Geometry → subspace recovery → LWE → AES-GCM decryption chain

See advanced-math.md for worked LWE solving code and lattice-and-lwe.md for attack selection, embeddings, and failure-mode triage.

ZKP & Constraint Solving

• ZKP cheating: For impossible problems (3-coloring K4), find hash collisions or predict PRNG salts
• Graph 3-coloring: nx.coloring.greedy_color(G, strategy='saturation_largest_first')
• Z3 solver: BitVec for bit-level, Int for arbitrary precision; BPF/SECCOMP filter solving
• Garbled circuits (free XOR): XOR three truth table entries to recover global delta
• Bigram substitution: OR-Tools CP-SAT with automaton constraint for known plaintext structure
• Trigram decomposition: Positions mod n form independent monoalphabetic ciphers
• Shamir SSS (deterministic coefficients): One share + seeded RNG = univariate equation in secret
• Race condition (TOCTOU): Synchronized concurrent requests bypass counter < N checks
• Groth16 broken setup (delta==gamma): Trivially forge: A=alpha, B=beta, C=-vk_x. Always check verifier constants first
• Groth16 proof replay: Unconstrained nullifier + no tracking = infinite replays from setup tx
• DV-SNARG forgery: With verifier oracle access, learn secret v values from unconstrained pairs, forge via CRS entry cancellation
• Shamir SSS reused polynomial coefficients: When same random coefficients are used for every secret byte, subtracting shares cancels all randomness, leaving only plaintext differences. See zkp-and-advanced.md.

See zkp-and-advanced.md for full code examples and solver patterns.

Modern Cipher Attacks (Additional)

• Affine over composite modulus: c = A*x+b (mod M), M composite (e.g., 65=5*13). Chosen-plaintext recovery via one-hot vectors, CRT inversion per prime factor. See modern-ciphers.md.
• Custom linear MAC forgery: XOR-based signature linear in secret blocks. Recover secrets from ~5 known pairs, forge for target. See modern-ciphers.md.
• Manger oracle (RSA threshold): RSA multiplicative + binary search on m*s < 2^128. ~128 queries to recover AES key.
• AES key recovery via byte-by-byte zeroing oracle: Integer overflow in key slot indexing allows selective byte zeroing; brute-force one byte at a time (256 per byte, 4096 total). See modern-ciphers.md.

Introspective CRC via GF(2) Linear Algebra

Self-referential CRC: find ASCII string whose CRC equals itself. CRC is linear over GF(2), so the constraint becomes a solvable linear system. Free variables chosen for printable ASCII range. See advanced-math.md.

CBC Padding Oracle Attack

Server reveals valid/invalid padding → decrypt any CBC ciphertext without key. ~4096 queries per 16-byte block. Use PadBuster or padding-oracle Python library. See modern-ciphers.md.

Bleichenbacher RSA Padding Oracle (ROBOT)

RSA PKCS#1 v1.5 padding validation oracle → adaptive chosen-ciphertext plaintext recovery. ~10K queries for RSA-2048. Affects TLS implementations via timing. See modern-ciphers.md.

Birthday Attack / Meet-in-the-Middle

n-bit hash collision in ~2^(n/2) attempts. Meet-in-the-middle breaks double encryption in O(2^k) instead of O(2^(2k)). See modern-ciphers.md.

• Sponge hash MITM collision: When sponge rate < state size, uncontrolled state bytes enable MITM — precompute forward encryptions keyed on uncontrolled bytes, search backward for matches. Reduces 2^48 to 2^24. See modern-ciphers-2.md.

CRC32 Collision-Based Signature Forgery (iCTF 2013)

CRC32 is linear — append 4 chosen bytes to force any target CRC32, forging CRC32(msg || secret) signatures without the secret. See modern-ciphers.md.

Blum-Goldwasser Bit-Extension Oracle (PlaidCTF 2013)

Extend ciphertext by one bit per oracle query to leak plaintext via parity. Manipulate BBS squaring sequence to produce valid extended ciphertexts. See modern-ciphers-2.md.

Hash Length Extension Attack

Exploits Merkle-Damgard hashes (hash(SECRET || user_data)) — append arbitrary data and compute valid hash without knowing the secret. Use hashpump or hashpumpy. See modern-ciphers-2.md.

Compression Oracle (CRIME-Style)

Compression before encryption leaks plaintext via ciphertext length changes. Send chosen plaintexts; matching n-grams compress shorter. Same class as CRIME/BREACH. See modern-ciphers-2.md.

RC4 Second-Byte Bias

RC4's second output byte is biased toward 0x00 (probability 1/128 vs 1/256). Distinguishes RC4 from random with ~2048 samples. See stream-ciphers.md.

RSA Multiplicative Homomorphism Signature Forgery

Unpadded RSA: S(a) * S(b) mod n = S(a*b) mod n. If oracle blacklists target message, sign its factors and multiply. See rsa-attacks-2.md.

Common Patterns

• RSA basics: phi = (p-1)*(q-1), d = inverse(e, phi), m = pow(c, d, n). See rsa-attacks.md for full examples.
• XOR: from pwn import xor; xor(ct, key). See classic-ciphers.md for XOR variants.

C srand/rand Prediction via ctypes (L3akCTF 2024, MireaCTF)

Pattern: Binary uses srand(time(NULL)) + rand() for keys/XOR masks. Python's random module uses a different PRNG. Use ctypes.CDLL('./libc.so.6') to call C's srand(int(time())) and rand() directly, reproducing the exact sequence. See prng.md for XOR decryption examples and timing tips.

V8 XorShift128+ (Math.random) State Recovery

Pattern: V8 JavaScript engine uses xs128p PRNG for Math.random(). Given 5-10 consecutive outputs of Math.floor(CONST * Math.random()), recover internal state (state0, state1) with Z3 QF_BV solver and predict future values. Values must be reversed (LIFO cache). Tool: d0nutptr/v8_rand_buster. See prng.md.

MT State Recovery from Float Outputs (PHD CTF Quals 2012)

Pattern: Server exposes random.random() floats. Standard untemper needs 624 × 32-bit integers, but floats yield only ~8 usable bits each. A precomputed GF(2) magic matrix (not_random library) recovers the full MT state from 3360+ float observations. Use to predict password reset tokens, session IDs, or CSRF tokens derived from random.random(). See prng.md.

Chaotic PRNG (Logistic Map)

• Logistic map: x = r * x * (1 - x), r ≈ 3.99-4.0; seed recovery by brute-forcing high-precision decimals
• Keystream: struct.pack("<f", x) per iteration; XOR with ciphertext

See prng.md for full code.

SPN S-box Intersection Attack

Divide-and-conquer SPN key recovery: attack each S-box position independently, intersect valid key candidates across multiple plaintext-ciphertext pairs. Reduces exponential key space to independent sub-key searches. See modern-ciphers-2.md.

Useful Tools

• Python: pip install pycryptodome z3-solver sympy gmpy2
• SageMath: sage -python script.py (required for ECC, Coppersmith, lattice attacks)
• RsaCtfTool: python RsaCtfTool.py -n <n> -e <e> --uncipher <c> — automated RSA attack suite (tries Wiener, Hastad, Fermat, Pollard, and many more)
• quipqiup.com: Automated substitution cipher solver (frequency + word pattern analysis)

CTF Crypto - Advanced Mathematical Attacks

Table of Contents

• Elliptic Curve Isogenies
• Pohlig-Hellman Attack (Weak ECC)
• Baby-Step Giant-Step for General DLP
• 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)
• Introspective CRC via GF(2) Linear Algebra (Google CTF 2017)
• Baby-Step Giant-Step for Sparse/Low Hamming Weight Exponents (SEC-T CTF 2017)
• Hensel's Lemma: Polynomial Root Lifting mod p^k (CONFidence CTF 2019 Teaser)

---

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)

Baby-Step Giant-Step for General DLP

Pattern: Compute discrete logarithm x where g^x = h (mod p) in O(sqrt(n)) time and space, where n is the group order. Works for any cyclic group — multiplicative groups mod p, elliptic curves, or abstract groups. Combined with Pohlig-Hellman for smooth-order groups, solves DLP when p-1 (or group order) has only small prime factors.

Baby-step giant-step algorithm:

from math import isqrt

def bsgs(g, h, p, order=None):
    """Baby-step giant-step: find x such that g^x = h (mod p).

    Time/space: O(sqrt(order)). For subgroups, pass the subgroup order.
    """
    if order is None:
        order = p - 1
    m = isqrt(order) + 1

    # Baby step: build table of g^j for j in [0, m)
    table = {}
    power = 1
    for j in range(m):
        table[power] = j
        power = (power * g) % p

    # Giant step: compute g^(-m), then check h * (g^(-m))^i
    factor = pow(g, -m, p)  # g^(-m) mod p
    gamma = h
    for i in range(m):
        if gamma in table:
            return i * m + table[gamma]
        gamma = (gamma * factor) % p
    return None  # No solution found (order was wrong)

# Example: ElGamal with smooth p-1 (MMA CTF 2015 "Alicegame")
# p-1 = 2 * 3^4 * 5 * 13 * 397 * 34703 * ... (all small factors)
# Pohlig-Hellman: solve DLP in each prime-power subgroup, combine with CRT

Full Pohlig-Hellman + BSGS pipeline:

from sympy.ntheory import factorint
from sympy.ntheory.modular import crt

def pohlig_hellman(g, h, p):
    """Solve g^x = h (mod p) when p-1 is smooth."""
    order = p - 1
    factors = factorint(order)  # {prime: exponent}

    residues = []
    moduli = []
    for prime, exp in factors.items():
        pe = prime ** exp
        # Project to subgroup of order prime^exp
        cofactor = order // pe
        gi = pow(g, cofactor, p)  # Generator of subgroup
        hi = pow(h, cofactor, p)  # Target in subgroup

        # Solve DLP in small subgroup via BSGS
        xi = bsgs(gi, hi, p, order=pe)
        if xi is None:
            return None
        residues.append(xi)
        moduli.append(pe)

    # Combine via CRT
    x, _ = crt(moduli, residues)
    assert pow(g, x, p) == h % p
    return x

Key insight: BSGS runs in O(sqrt(q)) for a subgroup of order q. Pohlig-Hellman decomposes the full DLP into subgroup DLPs. If p-1 = q1^e1 * q2^e2 * ... where all qi are small, the total cost is O(sum(sqrt(qi^ei))). A 1024-bit prime with smooth p-1 (all factors under ~40 bits) is solvable in seconds. Sage's discrete_log() automatically applies Pohlig-Hellman + BSGS.

When to recognize:

• ElGamal, DSA, or Diffie-Hellman with a randomly generated prime — check if p-1 is smooth: factor(p-1) in Sage
• ECC with smooth curve order — same approach, replace modular exponentiation with point multiplication
• Challenge generates new parameters on each connection — retry until you get a smooth prime
• Challenge description mentions "weak parameters" or uses suspiciously small primes

Sage one-liner: discrete_log(Mod(h, p), Mod(g, p)) handles everything automatically.

References: MMA CTF 2015 "Alicegame", SEC-T CTF "Madlog", Crypto CTF 2021 "RoHaLd"

---

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

---

Introspective CRC via GF(2) Linear Algebra (Google CTF 2017)

Pattern: Find an ASCII string whose CRC-N value equals the string itself (self-referential CRC). Model CRC as a linear function over GF(2) and solve the resulting system.

# CRC is linear over GF(2): CRC(a XOR b) = CRC(a) XOR CRC(b)
# Goal: find x where CRC(x) = x (as ASCII hex)
# 1. Compute CRC of all-zeros baseline
# 2. For each bit position, compute the CRC difference (remainder)
# 3. Set up GF(2) linear system: CRC(x) XOR x = 0
# 4. Solve with Gaussian elimination over GF(2)
from sage.all import *
F = GF(2)
# Build matrix where each column represents flipping one bit
# Rows represent the CRC output bits XOR input bits
M = Matrix(F, n_bits, n_bits)
# ... fill with CRC remainders ...
solution = M.solve_right(target_vector)

Key insight: CRC is a linear function over GF(2). The self-referential constraint CRC(x)=x becomes a system of linear equations over GF(2), solvable by Gaussian elimination. The ASCII constraint requires choosing free variables to keep all bytes in the printable range.

References: Google CTF 2017

---

Baby-Step Giant-Step for Sparse/Low Hamming Weight Exponents (SEC-T CTF 2017)

Pattern: DLP where the exponent is known to have low Hamming weight — e.g., at most k=11 bits set in a 128-bit exponent. Split the exponent into two halves e = e1 * 2^64 + e2. Precompute baby steps for all e1 values with ⌊k/2⌋ = 5 bits set, then do giant steps for all e2 values with ⌈k/2⌉ = 6 bits set.

Complexity: C(128, 5) ≈ 10^8 baby steps + C(128, 6) ≈ 10^9 giant steps — vastly less than O(2^128) brute force or O(2^64) standard BSGS.

from itertools import combinations
from math import comb

# Parameters: g^x = a (mod p), x has at most k=11 bits set in 128 bits
# Split: x = x1 * 2^64 + x2, where x1 has 5 bits set, x2 has 6 bits set
half = 64
k_low, k_high = 5, 6

# Baby step: g^(x1 * 2^64) for all x1 with k_low bits set
baby = {}
for bit_positions in combinations(range(half), k_low):
    x1 = sum(1 << b for b in bit_positions)
    val = pow(g, x1 * (2**half), p)
    baby[val] = x1

# Giant step: check if a * g^(-x2) is in baby table
# a = g^x = g^(x1*2^64) * g^x2, so g^(x1*2^64) = a * g^(-x2)
g_inv = pow(g, -1, p)
for bit_positions in combinations(range(half), k_high):
    x2 = sum(1 << b for b in bit_positions)
    candidate = (a * pow(g_inv, x2, p)) % p
    if candidate in baby:
        x1 = baby[candidate]
        x = x1 * (2**half) + x2
        assert pow(g, x, p) == a
        print(f"Found exponent: {x}")
        break

Verification:

# Check Hamming weight of recovered exponent
assert bin(x).count('1') <= 11

Key insight: Sparse-exponent DLP with only k bits set is attackable with meet-in-the-middle: each half uses C(n, k/2) entries, reducing complexity from O(2^k) to O(C(n, k/2)). For k=11 in 128 bits, this is ~10^8 vs 2^128. Always check if the challenge reveals or constrains the Hamming weight of the exponent.

References: SEC-T CTF 2017

---

Hensel's Lemma: Polynomial Root Lifting mod p^k (CONFidence CTF 2019 Teaser)

Pattern (Bro, do you even lift?): Challenge gives a polynomial P(x) whose unique root mod N = p^k is the flag, where p is a small known prime and k is large (e.g. p ~ 2^16, k = 100). Brute force over p^k is hopeless, but Hensel's lemma lifts any simple root mod p to a unique root mod p^k via Newton iteration: given P(r) ≡ 0 mod p^i, the lift is r' = r - P(r) * inverse(P'(r), p) mod p^(i+1). Factor out the intermediate reductions to mod p^(i+1) each step or the integers blow up exponentially.

# sage
R.<x> = PolynomialRing(ZZ)
pol   = ...           # polynomial with huge coefficients
p     = 35671
k     = 100

# Step 1: roots mod p (small, enumerable)
roots_p = [r for r in range(p) if pol(r) % p == 0]

# Step 2: Newton lift to p, p^2, ..., p^k
def hensel_lift(pol, root, p, k):
    dpol = pol.derivative()
    r = root
    mod = p
    for i in range(1, k):
        mod_next = mod * p
        # r' = r - P(r) * inverse(P'(r), p) mod p^(i+1)
        inv = inverse_mod(int(dpol(r)) % p, p)
        r = (r - int(pol(r)) * inv) % mod_next
        mod = mod_next
    return r

flag_int = hensel_lift(pol, roots_p[0], p, k)

Key insight: Any polynomial equation P(x) ≡ 0 mod p^k with p small and p not dividing P'(root) collapses to enumerating roots mod p (cheap) plus k - 1 Newton-style lifts. Each lift requires reducing intermediate values mod `p^(i+1)` at every step — Sage's naive solve_right or unreduced iteration grinds to a halt because P(r) grows as large integers. Works for any N = p^k or more generally N = prod(p_i^{k_i}) by lifting each prime-power factor independently and recombining via CRT.

CTF Crypto - Classic Ciphers

Table of Contents

• Vigenere Cipher
• Atbash Cipher
• Polybius Square Cipher (Qiwi-Infosec 2016)
• 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)
• Grid Permutation Cipher Keyspace Reduction (BSidesSF 2026)
• Image-Based Caesar Shift Ciphers (BSidesSF 2026)
• Variant A — Vertical Strip Shift (caesar1)
• Variant B — Horizontal Shift with ASCII Encoding (caesar2)
• XOR Key Recovery via File Format Headers (MetaCTF Flash 2026)
• 3D Vigenere Palindrome Symmetry Key Recovery (SECCON 2017)
• Nihilist Cipher Double-Crib Key Recovery (Security Fest CTF 2018)
• 16-Byte XOR Block Cipher Structural Reversal (h4ckc0n 2018)
• Flag Semaphore Photo Decoding (DefCamp CTF 2018)
• Two-Byte Nibble Reassembly with Random Padding (Trend Micro 2018)

---

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.

---

Polybius Square Cipher (Qiwi-Infosec 2016)

5x5 grid cipher where each letter maps to a two-digit coordinate (row, column). I/J typically share a cell.

import string

def polybius_decrypt(ciphertext, key="ABCDEFGHIKLMNOPQRSTUVWXYZ"):
    """Decrypt Polybius square cipher (pairs of digits 1-5)"""
    grid = {}
    for i, ch in enumerate(key):
        row, col = i // 5 + 1, i % 5 + 1
        grid[(row, col)] = ch

    digits = [int(d) for d in ciphertext if d.isdigit()]
    plaintext = ""
    for i in range(0, len(digits), 2):
        plaintext += grid.get((digits[i], digits[i+1]), '?')
    return plaintext

# Example: "5211251521531412" -> pairs (5,2)(1,1)(2,5)(1,5)(2,1)(5,3)(1,4)(1,2)
print(polybius_decrypt("5211251521531412"))

Key insight: Polybius ciphers produce digit-only ciphertext with values 1-5. The 5x5 grid merges I/J into one cell. Custom key alphabets change the grid layout but the two-digit coordinate structure remains constant.

---

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.

---

Grid Permutation Cipher Keyspace Reduction (BSidesSF 2026)

Pattern (ghostcrypt): A substitution cipher built on a 5x5 grid where the key permutes rows and columns independently. Row permutations and column permutations commute — applying all row swaps then all column swaps gives the same result regardless of order. This collapses the keyspace from potentially huge to just 5! x 5! = 14,400 combinations, making brute-force trivial.

from itertools import permutations

# 5x5 grid substitution cipher — brute force row+column permutations
grid_size = 5
ciphertext = "..."  # encrypted text
wordlist = set(open("/usr/share/dict/words").read().split())

for row_perm in permutations(range(grid_size)):
    for col_perm in permutations(range(grid_size)):
        # Apply inverse permutation to grid
        decrypted = apply_grid_permutation(ciphertext, row_perm, col_perm)
        words = decrypted.split()
        if sum(1 for w in words if w.lower() in wordlist) > len(words) * 0.5:
            print(f"Key: rows={row_perm}, cols={col_perm}")
            print(decrypted)
            break

Key insight: Row and column permutations on a grid are independent operations that commute. The total keyspace is the product of row permutations x column permutations (n!^2), NOT the factorial of total cells. For a 5x5 grid: 120 x 120 = 14,400 — brute-forceable in milliseconds.

When to recognize: Challenge uses a grid-based cipher, mentions "row/column shuffling", or provides a substitution table that looks like a permuted matrix. Any grid cipher where rows and columns are shuffled independently has this n!^2 keyspace property.

---

Image-Based Caesar Shift Ciphers (BSidesSF 2026)

Two variants of applying Caesar cipher concepts to 2D image data:

Variant A — Vertical Strip Shift (caesar1)

Each vertical strip of pixels is shifted downward by (column / strip_width) * multiplier mod height. The multiplier is a small integer (1-50), making it brute-forceable.

from PIL import Image
import sys

img = Image.open("shifted.png")
w, h = img.size
pixels = img.load()
strip_width = 10  # Determined by visual inspection

for multiplier in range(1, 51):
    out = Image.new("RGB", (w, h))
    out_px = out.load()
    for x in range(w):
        shift = (x // strip_width) * multiplier % h
        for y in range(h):
            out_px[x, (y - shift) % h] = pixels[x, y]
    out.save(f"attempt_{multiplier}.png")

Variant B — Horizontal Shift with ASCII Encoding (caesar2)

Each row is shifted horizontally by a different amount. The shift value for each strip directly encodes an ASCII character of the flag.

from PIL import Image

original = Image.open("original.png")
shifted = Image.open("shifted.png")
w, h = original.size

flag = ""
prev_shift = -1
for y in range(h):
    orig_row = [original.getpixel((x, y)) for x in range(w)]
    shift_row = [shifted.getpixel((x, y)) for x in range(w)]
    # Find shift by comparing rows
    for offset in range(128):
        if all(orig_row[(x + offset) % w] == shift_row[x] for x in range(min(20, w))):
            if offset != prev_shift:
                flag += chr(offset)
                prev_shift = offset
            break
print(flag)

Key insight: Image pixel shifts are a visual form of Caesar cipher. When comparing an original and shifted image, the shift amount per row/column directly encodes hidden data. Always compare row-by-row or column-by-column when given two versions of the same image.

When to recognize: Challenge provides one or two image files with visible horizontal or vertical "shearing" artifacts. If an original image is provided alongside a shifted version, compute per-row or per-column offsets and check if they decode as ASCII.

---

XOR Key Recovery via File Format Headers (MetaCTF Flash 2026)

Pattern (In The Door): A file claims to be a known format (e.g., PDF, PNG, ZIP) but file reports it as "data". The file has been XOR-encrypted with a repeating key. Recover the key by XOR-ing the encrypted bytes against the expected file format header, then extend the key using known structural elements at the end of the file.

# Step 1: XOR first bytes against expected header to derive key start
encrypted = open('encrypted.pdf', 'rb').read()

# PDF files always start with %PDF-1.
expected_header = b'%PDF-1.'
key_start = bytes(a ^ b for a, b in zip(encrypted[:len(expected_header)], expected_header))
print(f"Key prefix: {key_start}")  # e.g., b'h4ck4ll'

# Step 2: Extend key using known trailer structures
# PDF files end with %%EOF (possibly followed by newline)
# Try known trailer patterns at the end of the file
pdf_trailers = [b'%%EOF\n', b'%%EOF\r\n', b'%%EOF']
for trailer in pdf_trailers:
    tail = encrypted[-len(trailer):]
    key_tail = bytes(a ^ b for a, b in zip(tail, trailer))
    print(f"Key tail candidate: {key_tail}")

# Step 3: Once key length is known, combine fragments
# Common structures to anchor: 'startxref', 'trailer', 'endobj'
key = b'h4ck4llth3cryp70'  # 16-byte repeating key
key_len = len(key)

# Step 4: Decrypt entire file
decrypted = bytes(encrypted[i] ^ key[i % key_len] for i in range(len(encrypted)))
with open('decrypted.pdf', 'wb') as f:
    f.write(decrypted)

# Verify
import subprocess
result = subprocess.run(['file', 'decrypted.pdf'], capture_output=True, text=True)
print(result.stdout)  # Should show: PDF document

Key insight: Every file format has known byte sequences at fixed positions -- magic bytes at the start, structural markers throughout, and trailer signatures at the end. XOR with a repeating key is fully recoverable when you know enough plaintext at known offsets. For a key of length N, you need N bytes of known plaintext at known positions (they need not be contiguous, but you must know their offset modulo the key length).

Common file format anchors for key recovery:

When to recognize: Challenge provides a file that should be a known format (filename extension or description says so) but file reports "data" or wrong type. Hex dump shows no recognizable magic bytes. XOR the first few bytes against the expected header -- if the result looks like an ASCII string or repeating pattern, it is a repeating XOR key.

Determining key length: If the header-derived key fragment repeats or the key is a readable string, try common lengths (8, 16, 32). Alternatively, XOR the file against itself shifted by candidate key lengths and look for low-entropy output (many null bytes indicate correct shift = key length).

References: MetaCTF Flash CTF 2026 "In The Door"

---

3D Vigenere Palindrome Symmetry Key Recovery (SECCON 2017)

Pattern: When k2 = reverse(k1) in a 3D Vigenere cipher, the encryption depends only on k1[i] + k1[key_len-1-i] (symmetric sums). Only half the key needs recovery:

# Encryption: ct[i] = table[k1[i%kl]][k2[i%kl]][pt[i]]
# With k2 = reverse(k1): ct[i] depends on k1[i%kl] + k1[(kl-1-i)%kl]
# Known-plaintext with flag prefix recovers kl/2 sum values
# Then brute-force one half of the key (the sums constrain the other)
for c1 in range(len(s)):
    for c2 in range(len(s)):
        if (c1 + c2) % len(s) == known_sum:
            # test this key pair

Key insight: Palindrome key structure (k2 = reverse(k1)) halves the effective keyspace. Each plaintext position depends on the sum of two key characters at mirrored positions. Known plaintext of length >= key_length/2 fully constrains these sums, reducing the remaining brute-force dramatically. This generalizes to any polyalphabetic cipher where key symmetry reduces independent key variables.

References: SECCON CTF 2017

---

Nihilist Cipher Double-Crib Key Recovery (Security Fest CTF 2018)

Pattern (Mission Impossible): Nihilist cipher encrypts via Polybius square lookup + additive numeric key. Each plaintext letter becomes a two-digit Polybius coordinate, then the key's digit stream is added to produce ciphertext digits.

Key insight: The flag format midnight{...} contains two i characters at known positions. Both must produce the same Polybius coordinates (e.g., 24), so their ciphertext differences directly reveal two key digit pairs — enough to constrain the additive key. Every valid Polybius coordinate must be in range 1-5, which prunes invalid key candidates aggressively.

Recovery approach:

# For each pair of key digits (k1, k2) in 1..9:
#   for each ciphertext two-digit group:
#     plain = ((c1 - k1) % 10, (c2 - k2) % 10)
#     if plain[0] not in 1..5 or plain[1] not in 1..5: reject
#   otherwise test frequency (most common letter => 'e') and look up Polybius

Use the two repeated-character constraints from the flag prefix to cut the keyspace to a handful, then brute-force the Polybius square from remaining ciphertext frequency.

References: Security Fest CTF 2018 — writeup 10210

---

16-Byte XOR Block Cipher Structural Reversal (h4ckc0n 2018)

Pattern (custom XOR block cipher): Encryption operates on 16-byte blocks split into four 4-byte lanes. Each output byte is an XOR of several input bytes from the same block; one lane can be recovered as the XOR of the other three.

Exploit: Because every encrypted byte is a linear combination of plaintext bytes in the same block, XOR three lanes together to reconstruct the fourth. No key recovery needed — the algorithm is self-inverting once the linear structure is identified.

def decrypt(ciphertext):
    out = bytearray()
    for i in range(0, len(ciphertext), 16):
        for j in range(4):
            xorsum = 0
            for k in range(4):
                if k != j:
                    for l in range(i + k*4, i + k*4 + 4):
                        xorsum ^= ciphertext[l]
            for m in range(i + j*4, i + j*4 + 4):
                out.append(ciphertext[m] ^ xorsum)
    return bytes(out)

Key insight: Any unkeyed cipher built from XOR-only operations over fixed-size blocks is a linear system. If each output bit is a linear combination of input bits, invert by solving for the dependent lane — no key or brute force required.

References: h4ckc0n 2018 — writeup 10806

---

Flag Semaphore Photo Decoding (DefCamp CTF 2018)

Pattern: Challenge provides photos of a person holding flags in fixed positions. Map each pose to a letter using the standard flag semaphore chart (8 compass directions × 2 arms = ~32 letters). Two special poses — J (shift to "letters") and # (shift to "numbers") — switch between modes; maintain a mode flag while decoding.

SEMAPHORE = {
    ('NW','N'): 'A', ('NW','NE'): 'B', ('NW','E'): 'C', ('NW','SE'): 'D',
    # ... full table on Wikipedia
    ('N','NE'):  'J',  # letters shift
    ('NE','SE'): '#',  # numbers shift
}
letters = [SEMAPHORE[pose] for pose in pose_sequence]

Key insight: Semaphore is often disguised as "person dancing" or "art installation" photos. The presence of exactly two outstretched limbs per frame is the tell.

References: DefCamp CTF 2018 — Multiple Flags, writeup 12005

---

Two-Byte Nibble Reassembly with Random Padding (Trend Micro 2018)

Pattern: Custom encoding outputs two bytes for every input byte, where each input byte is split into high and low nibbles, and each nibble is padded with a random high nibble. Recover the original by masking low nibbles and recombining.

def decode(src):
    return bytes(((src[2*i] & 0xf) << 4) | (src[2*i+1] & 0xf)
                 for i in range(len(src)//2))

Key insight: Random padding in the high nibble can be ignored entirely — only the low nibbles carry signal. Spot the pattern when the encoded length is exactly 2x the plaintext length and histograms show uniform high-nibble distribution.

References: Trend Micro CTF 2018 — J1, writeup 12874

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)
• DSA Nonce Reuse for Private Key Recovery (VolgaCTF 2016)
• DSA Limited k-Value Brute Force (ASIS CTF Finals 2016)
• ECC Shared Prime Factor via GCD (ASIS CTF Finals 2016)
• DSA Key Recovery via MD5 Collision on k-Generation (CONFidence CTF 2017)
• Ed25519 Same-Nonce Key Recovery (hxp 2018)
• Singular Curve ECDLP to Additive/Multiplicative Group (hxp 2018)

---

Small Subgroup Attacks

• Check curve order for small factors
• Pohlig-Hellman: solve DLP (Discrete Logarithm Problem) in small subgroups, combine with CRT (Chinese Remainder Theorem)

# SageMath ECC basics
E = EllipticCurve(GF(p), [a, b])
G = E.gens()[0]  # generator
order = E.order()

Key insight: When the curve order has small prime factors, Pohlig-Hellman decomposes the DLP into small subgroup problems solvable independently, then combines results with CRT. Always factor the curve order first -- if it is smooth (all small factors), the DLP is trivially solvable.

---

Invalid Curve Attacks

If point validation is missing, send points on weaker curves. Craft points with small-order subgroups to leak secret key bits.

Key insight: Invalid curve attacks exploit missing point-on-curve validation. Send crafted points that lie on a different curve with a small-order subgroup, and the server will compute scalar multiplication on the weak curve, leaking secret key bits modulo the small order.

---

Singular Curves

If discriminant delta = 0, curve is singular. DLP becomes easy (maps to additive/multiplicative group).

Key insight: Check the discriminant 4a^3 + 27b^2 mod p first. If it is zero, the curve is singular and the ECDLP reduces to a simple discrete log in the additive group (cusp) or multiplicative group (node) of the field, both solvable in polynomial time.

---

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.

Key insight: Always check E.order() == p first. If the curve order equals the field prime, the ECDLP is solved instantly via p-adic lifting (Smart's attack). SageMath's discrete_log handles this automatically, but manual p-adic lift code is needed when the built-in method fails.

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.

---

DSA Nonce Reuse for Private Key Recovery (VolgaCTF 2016)

Pattern: Two DSA (Digital Signature Algorithm) signatures sharing the same nonce k (same r value) leak the private key. Identical in principle to ECDSA nonce reuse but uses DSA-specific group parameters.

# Two signatures (r, s1, H(m1)) and (r, s2, H(m2)) with same r
k = ((H_m1 - H_m2) * pow(s1 - s2, -1, q)) % q
x = ((s1 * k - H_m1) * pow(r, -1, q)) % q  # private key
# Then forge signatures for arbitrary messages

Key insight: DSA nonce reuse is identical in principle to ECDSA nonce reuse. Look for repeated r values in any DSA/ECDSA signature set. The same recovery formula applies to both.

---

DSA Limited k-Value Brute Force (ASIS CTF Finals 2016)

DSA implementation generates k from a restricted space (e.g., only 1024 possibilities). Given multiple signatures, brute-force k values and solve for the private key.

from Crypto.Util.number import inverse

def recover_dsa_key(signatures, q, g, p):
    """Recover DSA private key when k has limited possible values"""
    (r1, s1, h1), (r2, s2, h2) = signatures[0], signatures[1]

    for k1 in range(1, 1024):
        for k2 in range(1, 1024):
            # From DSA: s = k^-1 * (h + x*r) mod q
            # With two signatures: x = (s2*k2*h1 - s1*k1*h2) / (s1*k1*r2 - s2*k2*r1) mod q
            num = (s2 * k2 * h1 - s1 * k1 * h2) % q
            den = (s1 * k1 * r2 - s2 * k2 * r1) % q
            if den == 0:
                continue
            x = (num * inverse(den, q)) % q
            # Verify: check if r1 == (g^k1 mod p) mod q
            if pow(g, k1, p) % q == r1:
                return x
    return None

Key insight: Standard DSA nonce reuse attacks require k1 == k2. When k values are drawn from a small space (e.g., 1024 values), brute-force all (k1, k2) pairs across two signatures to solve the linear system for private key x.

---

ECC Shared Prime Factor via GCD (ASIS CTF Finals 2016)

Multiple ECC public keys generated with a flawed prime generator that filters prime % 3 == 2, reducing the keyspace enough for shared factors to appear.

from math import gcd
from Crypto.Util.number import inverse

# Collect moduli from multiple ECC public keys
moduli = [key.n for key in public_keys]

# Find shared factors via pairwise GCD
for i in range(len(moduli)):
    for j in range(i + 1, len(moduli)):
        g = gcd(moduli[i], moduli[j])
        if 1 < g < moduli[i]:
            p = g
            q = moduli[i] // p
            print(f"Key {i} factored: p={p}, q={q}")
            # Now decrypt using recovered factors

Key insight: When a prime generator excludes primes based on modular conditions (e.g., p % 3 == 2), the reduced keyspace makes GCD collisions between independently generated keys much more likely. Always try pairwise GCD across multiple public keys.

---

DSA Key Recovery via MD5 Collision on k-Generation (CONFidence CTF 2017)

Pattern: When DSA nonce k is derived from MD5(prefix + counter), generate MD5 prefix collisions to force two different counter values to produce the same k, enabling the standard nonce-reuse private key recovery.

# k = int(MD5("K = {n: " + str(counter) + ...))
# Use fastcoll to find MD5 collision on prefix "K = {n: "
# Two different counter values -> same MD5 -> same k -> nonce reuse

import subprocess
# Generate collision pair
subprocess.run(["fastcoll", "-p", prefix_file, "-o", "col1", "col2"])

# Get two signatures with same k (same r value)
sig1 = sign(msg1, counter1)  # uses MD5(prefix + counter1)
sig2 = sign(msg2, counter2)  # uses MD5(prefix + counter2) = same hash!

# Standard DSA nonce reuse recovery
k = (hash1 - hash2) * modinv(sig1.s - sig2.s, q) % q
private_key = (sig1.s * k - hash1) * modinv(sig1.r, q) % q

Key insight: MD5 collision generators like fastcoll produce pairs of inputs with identical hashes from a chosen prefix. When a signature scheme derives its nonce from an MD5 hash of controllable data, manufacturing a collision produces nonce reuse, enabling standard private key recovery.

References: CONFidence CTF 2017

---

Ed25519 Same-Nonce Key Recovery (hxp 2018)

Pattern: An Ed25519 signer reuses the same private-key scalar with deterministic nonce derivation, but the public key changes between signatures (fault injection or swapped key material). Two signatures (R1, S1, h1) and (R2, S2, h2) share a, so a = (S1 - S2) * inverse(h1 - h2) mod L.

L = 2**252 + 27742317777372353535851937790883648493
a = (S1 - S2) * pow(h1 - h2, -1, L) % L   # recovered scalar

Key insight: Ed25519 is deterministic, but any implementation bug that desyncs (r, k) from (H(privkey, msg)) produces classical nonce-reuse. Check implementations that sign across key rotations — the scalar often survives rekey.

References: hxp CTF 2018 — writeup 12561

---

Singular Curve ECDLP to Additive/Multiplicative Group (hxp 2018)

Pattern: Challenge publishes an "elliptic curve" that is actually singular — its discriminant is zero. Compute the singularity by finding the double root of f(x) = x^3 + ax + b. Map the curve to either the additive group (GF(p), +) (cusp) or the multiplicative group GF(p)^* (node) where DLP is easy.

# Find singular point r
P.<x> = PolynomialRing(GF(p))
f = x^3 + a*x + b
r = (f.derivative()).roots()[0][0]
# Shift curve so singularity is at origin
# Then map (x, y) -> (x - r) / y  for nodal singularity

Key insight: Discriminant -16(4a^3 + 27b^2) zero means singular. Singular curves are either cusps (map to (GF(p), +)) or nodes (map to GF(p)^*) — both with polynomial-time DLP.

References: hxp CTF 2018 — writeup 12563

CTF Crypto - Exotic Algebraic Structures (Part 2)

Covers 2017+ era exotic crypto attacks (BB-84 QKD, ElGamal variants, Paillier oracles, differential privacy, homomorphic bit extraction, Jordan normal form, OSS forgery, Cayley-Purser, BIP39 brute, Asmuth-Bloom, Rabin polynomial primes, LCG period, Vandermonde recovery). For Part 1 foundational exotic structures, see exotic-crypto.md.

Table of Contents

• BB-84 Quantum Key Distribution MITM Attack (PlaidCTF 2017)
• ElGamal Trivial DLP When B = p-1 (Hack.lu 2017)
• Paillier LSB Oracle via Homomorphic Doubling (CODE BLUE 2017)
• Differential Privacy Laplace Noise Cancellation (Pwn2Win 2017)
• Homomorphic Encryption Oracle Bit-Extraction (Tokyo Westerns 2017)
• ElGamal over Matrices via Jordan Normal Form (SharifCTF 8)
• OSS (Ong-Schnorr-Shamir) Signature Forgery via Pollard's Method (SharifCTF 8)
• Cayley-Purser Decryption Without Private Key (TJCTF 2018)
• BIP39 Partial-Mnemonic Brute Force via Checksum (SECCON 2018)
• Asmuth-Bloom Threshold Secret Sharing via CRT (X-MAS 2018)
• Rabin Cryptosystem with Polynomial Primes (X-MAS 2018)
• LCG Period Detection for Unlimited Output Prediction (X-MAS 2018)
• Polynomial Coefficient Recovery via Vandermonde Linear System (X-MAS 2018)
• Rabin Decryption via Four-Roots CRT Combination (Pragyan CTF 2019)

---

BB-84 Quantum Key Distribution MITM Attack (PlaidCTF 2017)

Pattern: In simulated BB-84 QKD without authentication, perform a full man-in-the-middle by independently negotiating with both Alice and Bob.

# Strategy: Always use basis Z, always send value 1 to Bob
# Alice side: measure in random bases, record results
# Bob side: always receives 1 in basis Z
# Bob's key = all 1s (known to attacker)
# Alice's key = attacker's measured qbit values

# Heuristic: throttle Bob's correct-guess count to match Alice's
# Both parties verify by comparing subset of bits — attacker controls both sides
for qbit in alice_qbits:
    my_basis = 'Z'  # always measure in Z basis
    my_value = measure(qbit, my_basis)
    send_to_bob(basis='Z', value=1)  # always send 1

# After basis reconciliation:
# key_with_alice = [measured values where bases matched]
# key_with_bob = [all 1s]

Key insight: BB-84 QKD is secure only with authenticated classical channels. Without authentication, an attacker can independently negotiate keys with both parties. Forcing a constant value to one party makes their key entirely predictable, while the other party's key is captured through measurement.

References: PlaidCTF 2017

---

ElGamal Trivial DLP When B = p-1 (Hack.lu 2017)

Pattern: ElGamal public key B = g^key mod p. If B + 1 == p, then B = p-1 = -1 mod p. By Euler's criterion, g^((p-1)/2) ≡ -1 (mod p) for any primitive root g. Therefore g^key ≡ g^((p-1)/2) (mod p), so key = (p-1)/2 directly. No DLP algorithm needed.

# Check for trivial case
if (B + 1) == p:
    key = (p - 1) // 2
    # Verify
    assert pow(g, key, p) == B
    # Decrypt ElGamal: shared_secret = pow(ephemeral, key, p)

Key insight: The generator raised to (p-1)/2 always equals -1 mod p (Euler's criterion for quadratic residues). When the public key B equals p-1, the private key is trivially (p-1)/2. Always check B == p-1 (and B == 1 for key=0) before attempting general DLP.

References: Hack.lu CTF 2017

---

Paillier LSB Oracle via Homomorphic Doubling (CODE BLUE 2017)

Pattern: Paillier encryption is additively homomorphic: multiplying a ciphertext by itself (ct^2 mod n^2) doubles the plaintext. Doubling repeatedly and observing when the LSB changes (due to modular reduction by n) reveals plaintext bits one at a time — a binary search identical to the RSA LSB oracle.

Attack (bit-by-bit recovery from MSB to LSB):

def paillier_double(ct, n):
    """Homomorphically double the plaintext."""
    return pow(ct, 2, n * n)

def recover_plaintext(ct, oracle_lsb, n):
    """Oracle returns LSB of decrypted plaintext."""
    lower, upper = 0, n
    current_ct = ct
    for _ in range(n.bit_length()):
        current_ct = paillier_double(current_ct)
        lsb = oracle_lsb(current_ct)
        mid = (lower + upper) // 2
        if lsb == 1:
            lower = mid  # plaintext > n/2, wraparound occurred
        else:
            upper = mid
    return lower

# Alternative: homomorphic subtraction to isolate each bit
def paillier_encrypt_scalar(m, n, g=None):
    """Encrypt scalar m under Paillier (with r=1 for known randomness)."""
    g = g or (n + 1)
    return pow(g, m, n * n)  # simplified (r=1)

def subtract_plaintext(ct, val, n):
    """Compute E(pt - val) = ct * E(-val) mod n^2."""
    neg_enc = paillier_encrypt_scalar(n - val, n)
    return (ct * neg_enc) % (n * n)

Key insight: Paillier's additive homomorphism enables a binary search oracle: doubling the plaintext via ct^2 and observing LSB changes reveals one bit per query. Equivalently, use homomorphic subtraction of known masks to isolate each bit. Total queries: log2(n) ≈ 2048 for 2048-bit modulus.

References: CODE BLUE CTF 2017

---

Differential Privacy Laplace Noise Cancellation (Pwn2Win 2017)

Pattern: Server implements differential privacy by adding Laplace noise (mean 0, scale λ) to character ordinals before returning them. Since Laplace noise has zero mean, querying the same position many times and averaging the results cancels the noise via the Law of Large Numbers.

import requests
import statistics

def recover_char(position, num_queries=1000):
    """Average 1000 noisy responses to cancel Laplace noise."""
    samples = []
    for _ in range(num_queries):
        noisy_val = query_server(position)
        samples.append(noisy_val)
    # Mean converges to true value as queries → ∞
    true_val = round(statistics.mean(samples))
    return chr(true_val)

flag = ''.join(recover_char(i) for i in range(flag_length))

Key insight: Laplace differential privacy with zero mean is breakable with sufficient queries — averaging N samples reduces noise variance by factor N (standard error ∝ 1/sqrt(N)). With λ=1 and 1000 queries, the mean is within ±0.1 of the true value. Round to nearest integer to recover the exact character ordinal. This applies to any additive zero-mean noise mechanism.

References: Pwn2Win CTF 2017

---

Homomorphic Encryption Oracle Bit-Extraction (Tokyo Westerns 2017)

Pattern: An encryption oracle has homomorphic properties — you can add 1 to the plaintext by performing a known operation on the ciphertext. Extract bits from an unknown plaintext by observing how the ciphertext changes as the plaintext value crosses power-of-2 boundaries.

Low-bit extraction (observe overflow):

# Increment plaintext by 1 repeatedly via homomorphic add-1
# Detect when bit N overflows: ciphertext "wraps" at value 2^N
ct = target_ciphertext
for bit_pos in range(num_bits):
    threshold = 2 ** bit_pos
    # Add 1 repeatedly until bit flips
    increments = 0
    prev_ct = ct
    while True:
        ct = homomorphic_add_one(ct)
        increments += 1
        if bit_has_flipped(ct, prev_ct, bit_pos):
            low_bits = (threshold - increments) % threshold
            break

High-bit extraction (divide by 2 on even values):

# Subtract recovered low bits to make value even
even_ct = homomorphic_subtract(target_ct, low_bits)
# Repeatedly divide by 2 and observe the resulting high bits
for i in range(high_bit_count):
    even_ct = homomorphic_halve(even_ct)
    high_bits = (high_bits << 1) | observe_lsb(even_ct)

Key insight: Homomorphic oracles enable bit-extraction: detect overflow in specific bit positions when incrementing for low bits; use division-by-2 on even numbers for high bits. The total number of queries scales linearly with the bit count of the plaintext.

References: Tokyo Westerns CTF 2017

---

ElGamal over Matrices via Jordan Normal Form (SharifCTF 8)

Pattern: Discrete log on matrices: convert generator G to Jordan normal form, then extract exponent from off-diagonal elements.

G = Matrix(GF(p), [[...]])  # generator matrix
H = Matrix(GF(p), [[...]])  # H = G^alpha
J, P = G.jordan_form(transformation=True)
H_prime = ~P * H * P  # H in Jordan basis
# For Jordan block with eigenvalue lambda:
# J^alpha has alpha * lambda^(alpha-1) on super-diagonal
# alpha = J[3][3] * H_prime[3][4] / H_prime[3][3]
alpha = int(J[3][3] * H_prime[3][4] / H_prime[4][4])

Key insight: Matrix DLP reduces to scalar DLP when the matrix is diagonalizable, or to polynomial extraction when Jordan blocks have repeated eigenvalues. The super-diagonal element of J^alpha is alpha * lambda^(alpha-1), giving alpha directly via division when lambda is known. For diagonalizable matrices, the DLP decomposes into independent scalar DLPs per eigenvalue. Always compute the Jordan form first to determine which reduction applies.

References: SharifCTF 8 (2018)

---

OSS (Ong-Schnorr-Shamir) Signature Forgery via Pollard's Method (SharifCTF 8)

Pattern: Given two valid OSS signatures, forge a signature for the product of their messages using Pollard's composition formula:

# OSS signature: (x, y) valid for message m if x^2 + k*y^2 = m (mod n)
# Pollard's forgery for m1*m2:
def forge_product(x1, y1, x2, y2, k, n):
    X = (x1*x2 + k*y1*y2) % n
    Y = (x1*y2 - x2*y1) % n
    return X, Y
# (X, Y) is a valid signature for m1*m2 mod n

Key insight: The OSS signature scheme is based on the quadratic form x^2 + ky^2 = m (mod n). Pollard showed that these forms compose multiplicatively -- given signatures for m1 and m2, you can forge a signature for m1m2 without the private key. This is a fundamental algebraic break, not an implementation bug. To sign an arbitrary target message `m_target`, factor it as a product of signed messages, or use the homomorphic property with `m1 = known_signed_message` and construct `m2 = m_target modinv(m1, n)` if a signature for m2 is obtainable.

References: SharifCTF 8 (2018)

---

Cayley-Purser Decryption Without Private Key (TJCTF 2018)

Pattern: Cayley-Purser is a matrix-based public-key system using 2x2 matrices modulo a prime. Public key is (alpha, beta, gamma) where gamma = alpha^r * beta * alpha^(-r) and epsilon = gamma^s. The private key is r, but decryption only needs a matrix H that satisfies H * gamma = gamma * H.

Exploit: Any matrix H commuting with gamma decrypts correctly, and the Cayley-Hamilton theorem lets you build one entirely from public values — no need to recover r.

from sage.all import matrix, identity_matrix
import operator

# Given public alpha, beta, gamma, epsilon, mu (ciphertext)
invalpha = alpha.inverse()
# Recover scaling entry h via elementwise division
h_elems = (invalpha * gamma - gamma * beta)
h_denom = (beta - invalpha)
h = matrix([[h_elems[i][j] / h_denom[i][j] for j in range(2)] for i in range(2)])

H = h[0][0] * identity_matrix(2) + gamma
plaintext = (H.inverse() * epsilon * H) * mu * (H.inverse() * epsilon * H)

Key insight: Any commuting matrix works as the decryption key. Cayley-Hamilton guarantees that H = c1 * I + c2 * gamma commutes with gamma, and the needed scalar c1 can be read off by comparing entries of alpha^(-1) * gamma against gamma * beta. Always check whether "private key" operations can be replaced by a commutation-equivalent derived from public data.

References: TJCTF 2018 — writeup 10680

---

BIP39 Partial-Mnemonic Brute Force via Checksum (SECCON 2018)

Pattern: Challenge provides 23 of 24 BIP39 mnemonic words (Japanese wordlist) and the target flag = md5(entropy). Each word encodes 11 bits, so the missing word costs only 2^11 = 2048 guesses. Validate each candidate by running BIP39's built-in SHA-256 checksum over the reassembled entropy — only the correct guess passes.

from mnemonic import Mnemonic
lg = Mnemonic("japanese")
known = ["...23 words..."]
for w in lg.wordlist:
    try:
        if lg.check(" ".join(known + [w])):
            entropy = lg.to_entropy(" ".join(known + [w]))
            print(md5(entropy).hexdigest())
    except Exception: pass

Key insight: BIP39 has a built-in 4-bit-per-word checksum, so partial mnemonics are self-verifying. Same trick applies to Electrum's seed format and any mnemonic scheme with internal parity.

References: SECCON 2018 — mnemonic, writeup 12053

---

Asmuth-Bloom Threshold Secret Sharing via CRT (X-MAS 2018)

Pattern: Instead of Shamir's polynomial interpolation, Asmuth-Bloom splits a secret S into shares (s_i, p_i) where each s_i = S mod p_i and p_i are pairwise-coprime primes. Recover S by applying the Chinese Remainder Theorem to any threshold number of shares.

from sympy.ntheory.modular import crt
# shares = [(s1,p1), (s2,p2), ..., (sk,pk)]
residues = [s for s, _ in shares]
moduli   = [p for _, p in shares]
S, M = crt(moduli, residues)
flag = long_to_bytes(int(S))

Key insight: Threshold sharing schemes can be CRT-based, not polynomial. Recognise Asmuth-Bloom by the (residue, modulus) share format; Shamir's scheme only publishes (x, y) coordinates without moduli.

References: X-MAS CTF 2018 — writeup 12660

---

Rabin Cryptosystem with Polynomial Primes (X-MAS 2018)

Pattern: Rabin key generator derives p, q from a polynomial in a base value r, e.g. p = r^2 + 3, q = r^2 + 7. Modulus N = p*q is a polynomial in r; solve for r via iroot(N - known_constant, 4), then recover both primes and decrypt the four sqrt candidates in the usual way.

from gmpy2 import iroot
# N = (r^2+3)(r^2+7) = r^4 + 10 r^2 + 21
r, _ = iroot(N - 21, 4)
p, q = r*r + 3, r*r + 7
x_p = pow(ct, (p+1)//4, p)
x_q = pow(ct, (q+1)//4, q)
# CRT combine x_p, x_q; flag is the candidate with known padding

Key insight: Any cryptosystem whose primes come from a polynomial in a small variable collapses under integer-root extraction. Recognize these by plotting N against hypothetical r guesses, or by seeing suspicious constant differences.

References: X-MAS CTF 2018 — writeups 12657, 12724

---

LCG Period Detection for Unlimited Output Prediction (X-MAS 2018)

Pattern: Server uses an LCG for RNG with a short period. Send repeated requests until you see a previously-observed output — you've found the period. From that point forward, every future value is known because the LCG cycles.

seen = {}
for i in itertools.count():
    v = fetch_next()
    if v in seen:
        period = i - seen[v]
        break
    seen[v] = i
# Now predict: future[i] == history[(i - period_start) % period]

Key insight: All LCGs are periodic and the period is bounded by m. Any output buffer long enough to contain the period gives you free prediction for the rest of the game.

References: X-MAS CTF 2018 — writeups 12668, 12669

---

Polynomial Coefficient Recovery via Vandermonde Linear System (X-MAS 2018)

Pattern: Oracle evaluates a hidden degree-n polynomial at n+1 points. Build the Vandermonde matrix of evaluation inputs and solve the linear system for coefficients; recovered polynomial reveals the secret constants.

from sage.all import matrix, vector, GF
pts = [(x_i, f(x_i)) for x_i in range(degree+1)]
A = matrix([[xi**k for k in range(degree+1)] for xi, _ in pts])
b = vector([yi for _, yi in pts])
coeffs = A.solve_right(b)

Key insight: Any secret polynomial, Shamir-style sharing, or "interpolate a curve" oracle falls to a Vandermonde solve with degree + 1 points. Sage's solve_right handles huge degrees.

References: X-MAS CTF 2018 — writeup 12722

---

Rabin Decryption via Four-Roots CRT Combination (Pragyan CTF 2019)

Pattern (Help Rabin): Rabin encrypts c = m^2 mod n with n = p*q and p, q ≡ 3 mod 4. Once p, q are recovered (here by Fermat-style square-root search because q = nextPrime(p+1) sits right next to p), compute mp = c^((p+1)/4) mod p and mq = c^((q+1)/4) mod q, then combine via extended GCD to yield four square roots ±r, ±s. Only one of the four decodes to readable text — that's the plaintext.

from Crypto.Util.number import inverse

def ext_gcd(a, b):
    c0, c1, a0, a1, b0, b1 = a, b, 1, 0, 0, 1
    while c1:
        q, r = divmod(c0, c1)
        c0, c1 = c1, r
        a0, a1 = a1, a0 - q * a1
        b0, b1 = b1, b0 - q * b1
    return a0, b0, c0

# p, q already recovered (e.g. via Fermat: p ~ sqrt(n))
pe, qe = (p + 1) // 4, (q + 1) // 4
mp, mq = pow(c, pe, p), pow(c, qe, q)
yp, yq, _ = ext_gcd(p, q)                      # yp*p + yq*q == 1

r1 = (yp * p * mq + yq * q * mp) % n
r2 = n - r1
s1 = (yp * p * mq - yq * q * mp) % n
s2 = n - s1

for cand in (r1, r2, s1, s2):
    try:
        pt = bytes.fromhex(hex(cand)[2:])
        if pt.isascii(): print(pt)            # pick the readable one
    except Exception: pass

Key insight: Rabin decryption inherently produces four candidates because x^2 ≡ c mod n has four roots mod n = p*q. When p, q ≡ 3 mod 4, per-prime roots are the closed-form exponentiation c^((p+1)/4) mod p — no Tonelli-Shelanks needed. Combine with Bezout coefficients yp*p + yq*q = 1 to get the four CRT candidates ±(yp*p*mq ± yq*q*mp) mod n, and select by plaintext sanity (ASCII, magic bytes, known prefix). The four-root ambiguity is why Rabin typically needs redundancy in the plaintext to be useful as a cryptosystem.