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.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
• [modern-ciphers.md](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, CBC padding oracle (full block decryption), Bleichenbacher RSA PKCS#1 v1.5 padding oracle (ROBOT), birthday attack / meet-in-the-middle, LFSR stream cipher attacks (Berlekamp-Massey, correlation attack), CRC32 collision signature forgery, Blum-Goldwasser bit-extension oracle, hash length extension, compression oracle (CRIME-style), RC4 second-byte bias, XOR consecutive byte correlation
• [rsa-attacks.md](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, multiplicative homomorphism signature forgery, weak keygen via base representation, RSA with gcd(e,phi)>1 exponent reduction
• [ecc-attacks.md](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-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.md) - PRNG attacks (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)
• [historical.md](historical.md) - Historical ciphers (Lorenz SZ40/42, book cipher implementation)
• [advanced-math.md](advanced-math.md) - Advanced mathematical attacks (isogenies, Pohlig-Hellman, 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)
• [exotic-crypto.md](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)

---

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: AZ 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](classic-ciphers.md#variable-length-homophonic-substitution-asis-ctf-finals-2013).

See [classic-ciphers.md](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)) 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

See [rsa-attacks.md](rsa-attacks.md) and [advanced-math.md](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](exotic-crypto.md#braid-group-dh--alexander-polynomial-multiplicativity-dicectf-2026)
• 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](ecc-attacks.md), [advanced-math.md](advanced-math.md), and [exotic-crypto.md](exotic-crypto.md) for full code examples.

Lattice / LWE Attacks

• 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.
• 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](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 -e --uncipher — automated RSA attack suite (tries Wiener, Hastad, Fermat, Pollard, and many more)
• quipqiup.com: Automated substitution cipher solver (frequency + word pattern analysis)

Source & license

This open-source skill is cataloged on AgentStack and links to its original source — we do not rehost the code.

• Author: dailyyarn
• Source: dailyyarn/CTF-agent
• License: MIT

Install and usage instructions live in the source repository linked above.