CTF Cryptography

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:

1. Key may not repeat - could be as long as message
2. Key derived from challenge theme (character names, phrases)
3. Key may have "padding" - repeated letters (IICCHHAA instead of ICHA)
4. 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)