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. 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 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 rsa-attacks.md - RSA attacks: small e (cube root), common modulus, Wiener's, Pollard's p-1, Hastad's broadcast, Fermat/consecutive primes, multi-prime, restricted-digit, Coppersmith structured primes, Manger oracle, polynomial hash, RSA p=q validation bypass, cube root CRT gcd(e,phi)>1, factoring from phi(n) multiple 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 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 prng.md - PRNG attacks (MT19937, 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, password cracking, logistic map chaotic PRNG) historical.md - Historical ciphers (Lorenz SZ40/42, book cipher implementation) advanced-math.md - Advanced mathematical attacks (isogenies, Pohlig-Hellman, LLL, Coppersmith, quaternion RSA, GF(2)[x] CRT, S-box collision code, LWE lattice CVP attack, affine cipher over non-prime modulus) exotic-crypto.md - Exotic algebraic structures (braid group DH / Alexander polynomial, monotone function inversion, tropical semiring residuation) 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 See classic-ciphers.md for full code examples. Modern Cipher Attacks AES-ECB: Block shuffling, byte-at-a-time oracle; image ECB preserves visual patterns AES-CBC: Bit flipping to change plaintext; padding oracle for decryption without key 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 See modern-ciphers.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., ed-1 ) enables factoring via Miller-Rabin square root technique; succeeds with prob ≥ 1/2 per attempt 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) 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 See ecc-attacks.md , advanced-math.md , and exotic-crypto.md for full code examples. Lattice / LWE Attacks LWE via CVP (Babai): Construct lattice from [qI | 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. LLL for approximate GCD: Short vector in lattice reveals hidden factors Multi-layer challenges: Geometry → subspace recovery → LWE → AES-GCM decryption chain See advanced-math.md for full LWE solving code and multi-layer patterns. 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 See zkp-and-advanced.md for full code examples and solver patterns. Modern Cipher Attacks (Additional) Affine over composite modulus: c = Ax+b (mod M) , M composite (e.g., 65=513). 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 ms < 2^128 . ~128 queries to recover AES key. 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. 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 . 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. 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 -e --uncipher — automated RSA attack suite (tries Wiener, Hastad, Fermat, Pollard, and many more) quipqiup.com: Automated substitution cipher solver (frequency + word pattern analysis)