CTF Crypto Challenges skill for Codex

A crypto challenge hides one broken assumption. The work is identifying the scheme, spotting which parameter the author weakened, and writing a clean solve script. Done well means the script runs from the given files to the flag, and you can name the property that broke.

First, identify

- [ ] 1. Read the handout source: it tells you the exact scheme and parameters
- [ ] 2. Classify: classical, symmetric (block/stream), RSA, ECC/DLP, hash, PRNG, or custom
- [ ] 3. Find what is unusual: a small exponent, a reused nonce, a chosen-plaintext oracle
- [ ] 4. Match to the known attack; write the solve script; verify on sample data if given

Fingerprints:

You see	Scheme	Intended weakness
Letters only, frequency skew	Classical (Caesar/Vigenere/substitution)	Frequency analysis; known-plaintext
n, e, c with huge integers	RSA	small e + no padding, shared/common modulus, close primes, partial key, Hastad
Ciphertext length a multiple of 16, repeats	AES-ECB	identical blocks; byte-at-a-time with an oracle
IV + CBC and a server that reveals padding validity	CBC padding oracle	decrypt/forge without the key
Stream cipher / CTR with a fixed nonce across messages	Keystream reuse	XOR messages, crib-drag
random.seed(...) with time or small range, or MT19937 outputs	Weak PRNG	brute the seed, or recover MT19937 state from 624 outputs
`MAC = H(secret		message)`, you can append
p, g, y and “find x”	Discrete log	small/smooth p (Pohlig-Hellman), small x

Toolbox

from Crypto.Util.number import long_to_bytes, bytes_to_long, inverse, GCD, isPrime
# PyCryptodome: install `pip install pycryptodome` (needs network; ask in the sandbox)

• PyCryptodome for byte/number conversions, AES, RSA objects.
• SageMath for lattices, elliptic curves, factoring helpers, discrete_log, Zmod — the default for anything number-theoretic. (sage is a heavy install; a challenge often needs it.)
• SymPy as a lighter stand-in for gcd, factorint (small factors), nextprime.
• Check whether the modulus is already factored on a public factor database before trying to factor a large n yourself (classic for reused CTF primes).

Worked patterns

RSA, common cases

# Small e (e=3), message short so m^3 < n: plaintext is an exact cube root
from sympy import integer_nthroot
m, exact = integer_nthroot(c, e)
assert exact; print(long_to_bytes(m))

# You recovered p and q (factored n, or primes too close via Fermat):
phi = (p - 1) * (q - 1)
d = inverse(e, phi)
print(long_to_bytes(pow(c, d, n)))

# Shared modulus, two exponents e1,e2 with gcd 1, two ciphertexts of one message:
g, a, b = egcd(e1, e2)          # extended gcd
m = (pow(c1, a, n) * pow(c2, b, n)) % n    # handle negative exponents with inverse()

Fermat factoring works only when p and q are close; do not grind it on random primes. For close primes, a = isqrt(n)+1, test a*a - n for a perfect square.

Keystream / nonce reuse

Two ciphertexts under the same keystream: c1 ^ c2 == m1 ^ m2. Crib-drag a guessed word (” the ”, “flag{”) across the XOR to recover both plaintexts. Script the slide and eyeball printable output.

CBC bit-flipping / padding oracle

If a server reveals whether padding is valid, recover plaintext a byte at a time per block; to forge a chosen plaintext, XOR the target difference into the previous ciphertext block. Write it against the given oracle endpoint, one block at a time, and verify each block before moving on.

Gotchas

• Byte order and encoding: confirm big-endian vs little-endian and whether the flag is hex, base64, or raw before concluding your math is wrong.
• Off-by-one in block indexing and PKCS#7 padding removal cause “almost right” plaintext.
• pow(a, -1, m) needs Python 3.8+; otherwise use inverse from PyCryptodome.
• Timing/padding oracles over the network are slow; cache responses and parallelise only within the challenge’s rate limits.
• Reinventing a textbook attack is slower than naming it. Search the exact scheme and the weakness; CTF crypto reuses a known catalogue.

Verification

• Run the solve script end to end from only the provided files; it prints a flag matching the event’s format (flag{...}, CTF{...}).
• If sample input/output is given, your script reproduces the sample before you trust it on the real data.
• State the broken assumption in one line (for example “e=3 with no padding on a short message”), so the solve is understood, not just lucky.

Work only on the challenge’s own files and endpoints; crypto solves stay inside the lab.