CTF Cryptography

Quick reference for crypto challenges. For detailed techniques, see supporting files.

Additional Resources

• prng.md - PRNG attacks (Mersenne Twister, LCG, time-based seeds, password cracking)

• historical.md - Historical ciphers (Lorenz SZ40/42)

• advanced-math.md - Advanced mathematical attacks (isogenies, Pohlig-Hellman, LLL, Coppersmith)

ZKP Attacks

• Look for information leakage in proofs

• If proving IMPOSSIBLE problem (e.g., 3-coloring K4), you must cheat

• Find hash collisions to commit to one value but reveal another

• PRNG state recovery: salts generated from seeded PRNG can be predicted

• Small domain brute force: if you know commit(i) = sha256(salt(i), color(i)) and have salt, brute all colors

Graph 3-Coloring

import networkx as nx nx.coloring.greedy_color(G, strategy='saturation_largest_first')

CBC-MAC vs OFB-MAC Vulnerability

• OFB mode creates a keystream that can be XORed for signature forgery

• If you have signature for known plaintext P1, forge for P2: new_sig = known_sig XOR block2_of_P1 XOR block2_of_P2

• Don't forget PKCS#7 padding in calculations!

• Small bruteforce space? Just try all combinations (e.g., 100 for 2 unknown digits)

Weak Hash Functions

• Linear permutations (only XOR, rotations) are algebraically attackable

• Build transformation matrix and solve over GF(2)

GF(2) Gaussian Elimination

import numpy as np

def solve_gf2(A, b): """Solve Ax = b over GF(2).""" m, n = A.shape Aug = np.hstack([A, b.reshape(-1, 1)]) % 2 pivot_cols, row = [], 0 for col in range(n): pivot = next((r for r in range(row, m) if Aug[r, col]), None) if pivot is None: continue Aug[[row, pivot]] = Aug[[pivot, row]] for r in range(m): if r != row and Aug[r, col]: Aug[r] = (Aug[r] + Aug[row]) % 2 pivot_cols.append((row, col)); row += 1 if any(Aug[r, -1] for r in range(row, m)): return None x = np.zeros(n, dtype=np.uint8) for r, c in reversed(pivot_cols): x[c] = Aug[r, -1] ^ sum(Aug[r, c2] * x[c2] for c2 in range(c+1, n)) % 2 return x

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 attack: same message, multiple e=3 encryptions

RSA with Consecutive Primes

Pattern (Loopy Primes): q = next_prime(p), making p ≈ q ≈ sqrt(N).

Factorization: Find first prime below sqrt(N):

from sympy import nextprime, prevprime, isqrt

root = isqrt(n) p = prevprime(root + 1) while n % p != 0: p = prevprime(p) q = n // p

Multi-layer variant: 1024 nested RSA encryptions, each with consecutive primes of increasing bit size. Decrypt in reverse order.

Multi-Prime RSA

When N is product of many small primes (not just p*q):

Factor N (easier when many primes)

from sympy import factorint factors = factorint(n) # Returns {p1: e1, p2: e2, ...}

Compute phi using all factors

phi = 1 for p, e in factors.items(): phi *= (p - 1) * (p ** (e - 1))

d = pow(e, -1, phi) plaintext = pow(ciphertext, d, n)

AES Attacks

• ECB mode: block shuffling, byte-at-a-time oracle

• CBC bit flipping: modify ciphertext to change plaintext

• Padding oracle: decrypt without key

AES-CFB-8 Static IV State Forging

Pattern (Cleverly Forging Breaks): AES-CFB with 8-bit feedback and reused IV allows state reconstruction.

Key insight: After encrypting 16 known bytes, the AES internal shift register state is fully determined by those ciphertext bytes. Forge new ciphertexts by continuing encryption from known state.

Classic Ciphers

• Caesar: frequency analysis or brute force 26 keys

• Vigenere: Kasiski examination, index of coincidence

• Substitution: frequency analysis, known plaintext

Vigenère Cipher

Known Plaintext Attack (most common in CTFs):

def vigenere_decrypt(ciphertext, key): result = [] key_index = 0 for c in ciphertext: if c.isalpha(): shift = ord(key[key_index % len(key)].upper()) - ord('A') base = ord('A') if c.isupper() else ord('a') result.append(chr((ord(c) - base - shift) % 26 + base)) key_index += 1 else: result.append(c) return ''.join(result)

def derive_key(ciphertext, plaintext): """Derive key from known plaintext (e.g., flag format CCOI26{)""" key = [] for c, p in zip(ciphertext, plaintext): if c.isalpha() and p.isalpha(): c_val = ord(c.upper()) - ord('A') p_val = ord(p.upper()) - ord('A') key.append(chr((c_val - p_val) % 26 + ord('A'))) return ''.join(key)

When standard keys don't work:

• Key may not repeat - could be as long as message

• Key derived from challenge theme (character names, phrases)

• Key may have "padding" - repeated letters (IICCHHAA instead of ICHA)

• Try guessing plaintext words from theme, derive full key

Elliptic Curve Attacks (General)

Small subgroup attacks:

• Check curve order for small factors

• Pohlig-Hellman: solve DLP in small subgroups, combine with CRT

Invalid curve attacks:

• If point validation missing, send points on weaker curves

• Craft points with small-order subgroups

Singular curves:

• If discriminant Δ = 0, curve is singular

• DLP becomes easy (maps to additive/multiplicative group)

Smart's attack:

• For anomalous curves (order = field size p)

• Lifts to p-adics, solves DLP in O(1)

SageMath ECC basics

E = EllipticCurve(GF(p), [a, b]) G = E.gens()[0] # generator order = E.order()

ECC Fault Injection

Pattern (Faulty Curves): Bit flip during ECC computation reveals private key bits.

Attack: Compare correct vs faulty ciphertext, recover key bit-by-bit:

For each key bit position:

If fault at bit i changes output → key bit i affects computation

Binary distinguisher: faulty_output == correct_output → bit is 0

Useful Tools

Python setup

pip install pycryptodome z3-solver sympy gmpy2

SageMath for advanced math (required for ECC)

sage -python script.py

Common Patterns

from Crypto.Util.number import *

RSA basics

n = p * q phi = (p-1) * (q-1) d = inverse(e, phi) m = pow(c, d, n)

XOR

from pwn import xor xor(ct, key)

Z3 SMT Solver

Z3 solves constraint satisfaction - useful when crypto reduces to finding values satisfying conditions.

Basic usage:

from z3 import *

Boolean variables (for bit-level problems)

bits = [Bool(f'b{i}') for i in range(64)]

Integer/bitvector variables

x = BitVec('x', 32) # 32-bit bitvector y = Int('y') # arbitrary precision int

solver = Solver() solver.add(x ^ 0xdeadbeef == 0x12345678) solver.add(y > 100, y < 200)

if solver.check() == sat: model = solver.model() print(model.eval(x))

BPF/SECCOMP filter solving:

When challenges use BPF bytecode for flag validation (e.g., custom syscall handlers):

from z3 import *

Model flag as array of 4-byte chunks (how BPF sees it)

flag = [BitVec(f'f{i}', 32) for i in range(14)] s = Solver()

Constraint: printable ASCII

for f in flag: for byte in range(4): b = (f >> (byte * 8)) & 0xff s.add(b >= 0x20, b < 0x7f)

Extract constraints from BPF dump (seccomp-tools dump ./binary)

mem = [BitVec(f'm{i}', 32) for i in range(16)]

Example BPF constraint reconstruction

s.add(mem[0] == flag[0]) s.add(mem[1] == mem[0] ^ flag[1]) s.add(mem[4] == mem[0] + mem[1] + mem[2] + mem[3]) s.add(mem[8] == 4127179254) # From BPF if statement

if s.check() == sat: m = s.model() flag_bytes = b'' for f in flag: val = m[f].as_long() flag_bytes += val.to_bytes(4, 'little') print(flag_bytes.decode())

Converting bits to flag:

from Crypto.Util.number import long_to_bytes

if solver.check() == sat: model = solver.model() flag_bits = ''.join('1' if model.eval(b) else '0' for b in bits) print(long_to_bytes(int(flag_bits, 2)))

When to use Z3:

• Type system constraints (OCaml GADTs, Haskell types)

• Custom hash/cipher with algebraic structure

• Equation systems over finite fields

• Boolean satisfiability encoded in challenge

• Constraint propagation puzzles

Cascade XOR (First-Byte Brute Force)

Pattern (Shifty XOR): Each byte XORed with previous ciphertext byte.

c[i] = p[i] ^ c[i-1] (or similar cascade)

Brute force first byte, rest follows deterministically

for first_byte in range(256): flag = [first_byte] for i in range(1, len(ct)): flag.append(ct[i] ^ flag[i-1]) if all(32 <= b < 127 for b in flag): print(bytes(flag))

ECB Pattern Leakage on Images

Pattern (Electronic Christmas Book): AES-ECB on BMP/image data preserves visual patterns.

Exploitation: Identical plaintext blocks produce identical ciphertext blocks, revealing image structure even when encrypted. Rearrange or identify patterns visually.

Padding Oracle Attack

Pattern (The Seer): Server reveals whether decrypted padding is valid.

Byte-by-byte decryption:

def decrypt_byte(block, prev_block, position, oracle): for guess in range(256): modified = bytearray(prev_block) # Set known bytes to produce valid padding pad_value = 16 - position for j in range(position + 1, 16): modified[j] = known[j] ^ pad_value modified[position] = guess if oracle(bytes(modified) + block): return guess ^ pad_value

Atbash Cipher

Simple substitution: A↔Z, B↔Y, C↔X, etc.

def atbash(text): return ''.join( chr(ord('Z') - (ord(c.upper()) - ord('A'))) if c.isalpha() else c for c in text )

Identification: Challenge name hints ("Abashed" ≈ Atbash), preserves spaces/punctuation, 1-to-1 substitution.

Substitution Cipher with Rotating Wheel

Pattern (Wheel of Mystery): Physical cipher wheel with inner/outer alphabets.

Brute force all rotations:

outer = "ABCDEFGHIJKLMNOPQRSTUVWXYZ{}" inner = "QNFUVWLEZYXPTKMR}ABJICOSDHG{" # Given

for rotation in range(len(outer)): rotated = inner[rotation:] + inner[:rotation] mapping = {outer[i]: rotated[i] for i in range(len(outer))} decrypted = ''.join(mapping.get(c, c) for c in ciphertext) if decrypted.startswith("METACTF{"): print(decrypted)