--- id: sm-ctf-crypto name: "ctf-crypto" url: https://skills.yangsir.net/skill/sm-ctf-crypto author: ljagiello domain: security tags: ["ctf-challenges", "cryptography", "security-puzzles", "encryption/decryption"] install_count: 3800 rating: 4.40 (20 reviews) github: https://github.com/ljagiello/ctf-skills --- # ctf-crypto > 提供针对CTF（夺旗赛）挑战的密码学攻击技术，帮助安全爱好者和参赛者破解加密难题，提升实战能力。 **Stats**: 3,800 installs · 4.4/5 (20 reviews) ## Before / After 对比 ### 掌握CTF密码学攻击，提升解题能力。 ## Readme # 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 - [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 - [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 - [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, 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.md) - Historical ciphers (Lorenz SZ40/42, book cipher implementation) - [advanced-math.md](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-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](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](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., `e*d-1`) enables factoring via Miller-Rabin square root technique; succeeds with prob ≥ 1/2 per attempt 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 < 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](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](modern-ciphers.md#affine-cipher-over-composite-modulus-nullcon-2026). - **Custom linear MAC forgery:** XOR-based signature linear in secret blocks. Recover secrets from ~5 known pairs, forge for target. See [modern-ciphers.md](modern-ciphers.md#custom-linear-mac-forgery-nullcon-2026). - **Manger oracle (RSA threshold):** RSA multiplicative + binary search on `m*s < 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](rsa-attacks.md) for full examples. - **XOR:** `from pwn import xor; xor(ct, key)`. See [classic-ciphers.md](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](prng.md#v8-xorshift128-state-recovery-mathrandom-prediction). ## 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(" -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: https://skills.yangsir.net/skill/sm-ctf-crypto* *Markdown mirror: https://skills.yangsir.net/api/skill/sm-ctf-crypto/markdown*