name: ctf-crypto description: Provides cryptography attack techniques for CTF challenges. Use when attacking encryption, hashing, signatures, ZKP, PRNG, or mathematical crypto problems involving RSA, AES, ECC, lattices, LWE, CVP, number theory, Coppersmith, Pollard, Wiener, padding oracle, GCM, key derivation, or stream/block cipher weaknesses. license: MIT compatibility: Requires filesystem-based agent (Claude Code or similar) with bash, Python 3, and internet access for tool installation. allowed-tools: Bash Read Write Edit Glob Grep Task WebFetch WebSearch metadata: user-invocable: "false"

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
# Coppersmith (optional): pip install coppersmith
# Alternative Coppersmith lib: git clone https://github.com/jvdsn/crypto-attacks ~/.ctf-tools/crypto-attacks && pip install -r ~/.ctf-tools/crypto-attacks/requirements.txt

Linux (apt):

apt install hashcat

macOS (Homebrew):

brew install hashcat

Manual install:

SageMath (optional — only for legacy Sage fallback snippets (collapsed sections)) — Linux: apt install sagemath, macOS: brew install --cask sage
RsaCtfTool — git clone https://github.com/RsaCtfTool/RsaCtfTool (automated RSA attacks)
crypto-attacks (Coppersmith) — git clone https://github.com/jvdsn/crypto-attacks ~/.ctf-tools/crypto-attacks + pip install -r ~/.ctf-tools/crypto-attacks/requirements.txt (alternative to pip install coppersmith)

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
modern-ciphers-4.md - Modern cipher attacks (Part 4): ChaCha20-Poly1305 nonce reuse forbidden attack over $2^{130}-5$ (RFC 8439, CTR $C_1\oplus C_2=P_1\oplus P_2$, Poly1305 $\sum c_i r^{n-i}$ via galois/sympy, 2-msg $ad=""$ vectors), partitioning-oracle / key-committing AEAD splitting lattice, sponge generality (SHA-3/Keccak $0x06$ vs $0x01$, Ascon/Gimli/Sparkle rate/capacity/rounds/pad table + endianness workflow), eSTREAM Trivium 1152-round warmup & cube attack outline (Grain)
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

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

# Quick factorization (sympy, primary)
python3 -c "from sympy import factorint; print(factorint(<n>))"
# Sage alternative: 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 .

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

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; small_roots via coppersmith lib (Sage fallback in details)
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 , then take g-th root over integers

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). sympy/fpylll BSGS+Pohlig-Hellman (Sage alternative collapsed). 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

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

Diffie-Hellman Attacks

Trivial g: Try g = 0, 1, p-1 and peer values A = 0, 1, p-1, p first; unvalidated range checks give known-constant secrets. See dh-attacks.md.
Pohlig-Hellman: Factor p-1; smooth means full DLP via BSGS per subgroup + CRT. See dh-attacks.md.
Small-subgroup confinement / Lim-Lee: Static key + composite p-1 with small factors; send order-r element, brute b mod r via MAC/decrypt oracle, CRT across r_i. See dh-attacks.md.
X25519 low-order: Cofactor 8 + clamping means small-order u forces all-zero K; u = 0, 1 always probe. Missing all-zero check = 1-2 query break. See ecc-attacks.md.

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: fpylll LLL.reduction / BKZ.reduction / GSO.Mat.babai / CVP.closest_vector (Sage Matrix(ZZ).LLL() / M.BKZ fallback in details) — start with LLL, move to BKZ when LLL almost works, use Babai 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 GSO.Mat.babai or CVP.closest_vector 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: fpylll LLL.reduction (Sage Matrix(ZZ).LLL() fallback in details) — 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 .

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

Useful Tools

Python: pip install pycryptodome z3-solver sympy gmpy2
SageMath (optional fallback): sage -python script.py — only for collapsed Sage alternatives
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

Install

Related skills