crypto-attack-patterns

Files (32)

• SKILL.md
• attack-taxonomy.md · references/
• easyfault-solved-workflow.md · references/
• easyfault-techniques-tried.md · references/
• easyrsa-p2plus1-family.md · references/
• ecc-playbook.md · references/
• fhe-ksk-key-recovery.md · references/
• lattice-playbook.md · references/
• number-theory-toolbox.md · references/
• oracle-attacks-playbook.md · references/
• packed-nuitka-lwe-payload-notes.md · references/
• playbook-aes-block-cipher-attacks.md · references/
• playbook-classic-cipher-attacks.md · references/
• playbook-crypto-attacks-overview.md · references/
• playbook-crypto-attacks-roadmap.md · references/
• playbook-ecc-attacks-cheatsheet.md · references/
• playbook-encoding-cheatsheet.md · references/
• playbook-lattice-lwe-attacks.md · references/
• playbook-prng-stream-cipher-attacks.md · references/
• playbook-rsa-attacks-cheatsheet.md · references/
• reversing-packed-python-crypto.md · references/
• rsa-fault-xor-missing-modulus.md · references/
• rsa-playbook.md · references/
• rsa-psq-plus-one-hidden-modulus.md · references/
• statistical-lwe-bypass-binary-secret.md · references/
• symmetric-hash-prng-playbook.md · references/
• writeup-template.md · references/
• bundle_oracle.py · scripts/
• oracle_skeleton.py · scripts/
• prng_toolkit.py · scripts/
• rsa_ctf_toolkit.py · scripts/
• xor_toolkit.py · scripts/

SKILL.md (first lines)

# CTF Cryptography

## Purpose

Use this skill when the user wants to solve, train for, or build knowledge around **CTF cryptography challenges**. This is different from production crypto guidance: CTF crypto is about recognizing intentionally broken assumptions, deriving an attack, scripting it quickly, and recovering a flag.

The goal is to make Hermes strong at:
- recognizing challenge families from source/output/artifacts
- choosing the likely attack path fast
- writing Python/Sage/Z3 scripts to recover plaintext/key/flag
- explaining the vulnerability in a writeup-quality way
- preserving newly learned tricks back into this skill

## First Response Workflow for Any CTF Crypto Challenge

1. **Inventory artifacts**
   - source code? parameters? ciphertext? public key? oracle endpoint? samples? multiple messages?
   - exact challenge category: classical, encoding, XOR, block cipher, hash/MAC, RSA, ECC, lattice, PRNG, protocol, side-channel.
2. **Extract mathematical objects**
   - integers: `n, e, c, p, q, phi, d`
   - curves: `p, a, b, G, Q, order`
   - block data: mode, IV/nonce, tag, padding, repeated blocks
   - hashes/MACs: construction, secret-prefix/suffix, digest size, salt
   - PRNG: seed source, state size, output truncation
3. **List obvious smells**
   - small exponent, reused nonce, repeated XOR key, known plaintext, deterministic encryption, textbook RSA, missing padding, ECB, CBC bit flipping, CTR nonce reuse, bad RNG, custom hash, custom curve, small subgroup.
4. **Try low-cost checks first**
   - decode layers, factor small `n`, gcd across moduli, repeated blocks, XOR frequency, Fermat close primes, small roots, Wiener/Boneh-Durfee hints, invalid curve/singular curve, MT19937 state recovery.
5. **Script reproducibly**
   - keep all constants in one file
   - assert intermediate equations
   - print candidate plaintexts and score them
   - for oracle challenges, implement a cached, retrying oracle wrapper before the exploit loop
   - for PRNG challenges, identify exact generator, output width, truncation, and whether outputs are consecutive
6. **Produce final writeup**
   - bug → attack idea → math derivation → exploit script → flag

## Core Attack Taxonomy

### Classical and encoding
- Caesar/Vigenere/Affine/substitution/transposition
- Bacon, Morse, Polybius, rail fence
- base encodings, hex/base64/base32/ascii85, URL, JWT, PEM, ASN.1
- frequency analysis, crib dragging, known plaintext

### XOR and stream ciphers
- single-byte XOR by frequency score
- repeating-key XOR by normalized Hamming distance
- many-time pad / CTR nonce reuse via pairwise XOR and crib dragging
- LFSR / Berlekamp-Massey
- RC4 bias or key scheduling mistakes

### Block cipher modes
- ECB repeated-block detection and cut-and-paste
- CBC padding oracle
- CBC bit flipping when IV/ciphertext malleable
- CTR/GCM nonce reuse recovering keystream or breaking authentication assumptions
- weak/custom padding

### Hashes and MACs
- length extension: MD5/SHA1/SHA256 secret-prefix MAC
- weak compare/timing leaks
- hash collision puzzle, truncated digest brute force
- custom Merkle-Damgard misuse
- HMAC vs `hash(secret || msg)` confusion

### RSA
- textbook RSA no padding
- small public exponent / Hastad broadcast
- common modulus
- shared prime across moduli via gcd
- Fermat factorization for close primes
- Wiener attack for small `d`
- partial key exposure / Coppersmith small roots
- low-entropy messages / stereotyped plaintext
- parity/LSB oracle and Bleichenbacher-style padding oracle
- CRT faults leaking factor via `gcd(s^e - m, n)`
### RSA
- textbook RSA no padding
- small public exponent / Hastad broadcast
- common modulus
- shared prime across moduli via gcd
- Fermat factorization for close primes
- Wiener attack for small `d`
- partial key exposure / Coppersmith small roots
- low-entropy messages / stereotyped plaintext
- parity/LSB oracle and Bleichenbacher-style padding oracle
- CRT faults leaking factor via `gcd(s^e - m, n)`
- XOR exponent fault (d XOR random row): when n is NOT given and a "bundle" encodes a helper value (base) via subset sums, first try the direct dual-LLL base recovery documented in `references/easyfault-solved-workflow.md`: build `L1 = {u : u·vals1 = 0 mod mod1}`, LLL it, then compute `base = -(u·vals0)/(u·bias0) mod mod0`. This solved the EasyFAULT instance in seconds and avoids 2^192 search. If direct recovery does not apply, fall back to the older oracle notes in `references/rsa-fault-xor-missing-modulus.md`. ⚠️ Pitfall: single-set/CRT zero-vector counts can be tautological as discriminators; verify any candidate by reconstructing rows and completing the fault attack.
- **q = p²+1 with hidden modulus (N·s output)** : when `q = p**2 + 1` (composite, always even) and output gives N multiplied by another random prime s (hiding N), the flag can be decrypted using only p·(p²+1) as modulus — r is irrelevant if the flag is small enough (< 1536 bits). The challenge reduces to finding p³+p as a divisor of the obfuscated K = N·s. See `references/rsa-psq-plus-one-hidden-modulus.md`.\n- **N · getPrime(k) — multi-instance GCD attack**: when a challenge outputs `K = N * getPrime(k)` (N hidden behind a random k-bit factor), and the CTF platform allows re-generating instances (re-download, press Start, or the API returns new values each call), collect **two or more K values**. Since s₁ ≠ s₂ are independent primes, `gcd(K₁, K₂) = N`. This is often the INTENDED solution — the extra factor is a red herring that collapses with multiple instances. **Check the Network tab (F12)** for API endpoints returning fresh challenge outputs. Single-instance ECM/Coppersmith on K is a trap; if you're stuck after 30+ minutes, re-read the challenge page for instance regeneration hints. See `references/rsa-psq-plus-one-hidden-modulus.md`.

### ECC
- invalid curve attack
- small subgroup / missing point validation
- nonce reuse in ECDSA/Schnorr
- biased/partial nonce lattice attacks
- anomalous curves, singular curves
- Pohlig-Hellman when group order is smooth
- wrong curve parameters or reused `k`

### Lattices and algebra
- LLL/Coppersmith for small roots
- Hidden Number Problem for biased nonces
- approximate common divisor
- subset sum/knapsack low density
- **subset sum basis recovery**: when a secret (e.g. `base`) is encoded as subset sums of unknown coefficients across multiple sets sharing the same underlying rows, statistical tests (GCD of differences, convex hull vertex count, pairwise ratio analysis, magnitude bounds) are WORTHLESS — the encoded values are indistinguishable from random for any candidate. Only lattice reduction (LLL/BKZ) can recover the coefficients and the secret. SageMath or fpylll is mandatory.
  - **count_zero_st oracle**: for the RSA-fault bundle pattern (see `references/rsa-fault-xor-missing-modulus.md`), build the lattice L = L_0 ∩ L_1, embed basis vectors as (w, s, t) in Z^74, LLL, and count vectors with s=t=0. Random bases give 1-3; correct base gives ~38-42. This oracle enables iterative search for the secret base. A reusable implementation is at `scripts/bundle_oracle.py` — takes a base hex string and an output.txt path, prints the oracle score.
- LWE-style packed payloads: infer serialization/layout and source constants before launching generic CVP/LLL
- **FHE/KSK key recovery from evaluation keys**: when a TFHE-like challenge provides BSK/KSK (evaluation keys) but not the secret key, recover lvl0 from KSK j=2 samples reduced modulo 2^40 — the message term `s_i*2^40` vanishes mod 2^40, giving clean LWE with known messages. Alternatively, combine j=1 and j=2 KSK samples via `y' = b1 - b2*2^12` to eliminate the unknown `s_i` entirely, yielding LWE with noise ~2^31 mod 2^64 (ratio 2^-33). Once lvl0 is recovered, lvl1 follows trivially from KSK j=1 entries (signal 2^52 vs noise 2^19). See `references/fhe-ksk-key-recovery.md`.
  - ⚠️ **Noise amplification pitfall**: Gaussian elimination mod composite modulus (2^k) or mod a prime near q DESTROYS the signal for binary-secret LWE — the matrix inverse amplifies noise to uniform random. Real-valued least-squares with RDF only works for entries ≤40 bits. LLL/BKZ lattice reduction is REQUIRED for this problem class; Gaussian elimination and plain real-valued solves are traps.

### PRNG and randomness
- time-seeded RNG brute force
- Python `random` / MT19937 state recovery
- LCG parameter/state recovery
- modulo bias and insufficient entropy
- nonce/key generation from predictable values

### Protocol/oracle challenges

From Wang200935/security-agent-skills, MIT.

More from Wang200935/security-agent-skills