Skip to content

ljagiello/ctf-skills / ctf-crypto

ctf-crypto

Verified

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.

FileKindSize
SKILL.mdskill md41.1 KB
advanced-math.mdmarkdown40.4 KB
classic-ciphers.mdmarkdown28.5 KB
dh-attacks.mdmarkdown6.3 KB
ecc-attacks.mdmarkdown40.9 KB
exotic-crypto-2.mdmarkdown19.6 KB
exotic-crypto.mdmarkdown36.8 KB
historical.mdmarkdown4.5 KB
lattice-and-lwe.mdmarkdown33.1 KB
modern-ciphers-2.mdmarkdown29.2 KB
modern-ciphers-3.mdmarkdown27.2 KB
modern-ciphers-4.mdmarkdown24.2 KB
modern-ciphers.mdmarkdown35.5 KB
post-quantum.mdmarkdown4.2 KB
prng-attacks.mdmarkdown12.2 KB
prng.mdmarkdown42.5 KB
rsa-attacks-2.mdmarkdown46.1 KB
rsa-attacks.mdmarkdown57.3 KB
stream-ciphers.mdmarkdown33.2 KB
zkp-and-advanced.mdmarkdown20.7 KB

prng-attacks.md

View on GitHub
# CTF Crypto - PRNG Attacks (CTF-Era Techniques)

Advanced CTF-specific PRNG attacks from 2017 onward. For foundational PRNG recovery (MT19937, LCG parameter recovery, ChaCha20, V8 XorShift128+, password cracking), see [prng.md](prng.md).

## Table of Contents
- [Mersenne Twister Seed Recovery from Subset Sum (Tokyo Westerns 2017)](#mersenne-twister-seed-recovery-from-subset-sum-tokyo-westerns-2017)
- [MT19937 State Recovery via Constraint Propagation (HITCON 2017)](#mt19937-state-recovery-via-constraint-propagation-hitcon-2017)
- [Rule 86 Cellular Automaton PRNG Reversal via Z3 (Insomni'hack 2018)](#rule-86-cellular-automaton-prng-reversal-via-z3-insomnihack-2018)
- [Java LCG Seed Meet-in-the-Middle via Partial Modulo (P.W.N. CTF 2018)](#java-lcg-seed-meet-in-the-middle-via-partial-modulo-pwn-ctf-2018)
- [LCG Backward Stepping via Multiplicative Inverse (P.W.N. CTF 2018)](#lcg-backward-stepping-via-multiplicative-inverse-pwn-ctf-2018)
- [LFSR Bit-Fold Recovery from ASCII Parity (X-MAS CTF 2018)](#lfsr-bit-fold-recovery-from-ascii-parity-x-mas-ctf-2018)
- [Z3 Solve-Time Timing Oracle on PRNG (X-MAS CTF 2018)](#z3-solve-time-timing-oracle-on-prng-x-mas-ctf-2018)
- [randcrack-Fed DSA k Prediction (CSAW CTF 2018)](#randcrack-fed-dsa-k-prediction-csaw-ctf-2018)
- [Time-Seeded PRNG Offset via Format-String Global Write (FireShell 2019)](#time-seeded-prng-offset-via-format-string-global-write-fireshell-2019)
- [NTP-Poisoned PRNG State Leak via UUID XOR (RuCTFe 2018)](#ntp-poisoned-prng-state-leak-via-uuid-xor-ructfe-2018)

---

## Mersenne Twister Seed Recovery from Subset Sum (Tokyo Westerns 2017)

**Pattern:** MT19937 seeded with a 32-bit value generates subset-sum problems (e.g., "which elements from this set sum to target?"). Solving small subset-sum problems leaks specific MT output values. Two recovered outputs at indices 0 and 227 are sufficient to invert the MT seeding process.

**MT twist function relationship:**
```text
mt[i] = mt[i-624] XOR twist(mt[i-624], mt[i-623])
```
At the wrap-around: `mt[624]` depends on `mt[0]` (new cycle) and `mt[397]` (old cycle). Recovering `mt[0]` and `mt[227]` (which is related to `mt[624-227] = mt[397]`) via subset-sum solutions reveals enough to invert the twist recurrence.

```python
import random

def crack_seed_from_two_outputs(mt0_val, mt227_val):
    """Try all 2^32 seeds until MT outputs match recovered values."""
    for seed in range(2**32):
        r = random.Random()
        r.seed(seed)
        # Generate enough to reach indices 0 and 227
        outputs = [r.getrandbits(32) for _ in range(228)]
        if outputs[0] == mt0_val and outputs[227] == mt227_val:
            return seed
    return None

# After recovering seed, all future (and past) outputs are predictable
r = random.Random()
r.seed(recovered_seed)
```

**Key insight:** MT19937 seeds recoverable from as few as two state values (indices 0 and 227) via the twist function's wrap-around relationship. Any challenge that exposes MT state values through solvable mathematical puzzles is vulnerable to full seed recovery.

**References:** Tokyo Westerns CTF 2017

---

## MT19937 State Recovery via Constraint Propagation (HITCON 2017)

**Pattern:** Server generates problems that leak 24-120 bits of PRNG output per round (e.g., partial bit-patterns, subset sums, modular reductions). Rather than collecting 624 full 32-bit outputs, model the MT state as an array of per-cell candidate sets and propagate constraints bidirectionally through the MT recurrence.

**MT recurrence dependencies:**
```text
state[i] = state[i-624] XOR twist(state[i-624], state[i-623])
```
This means `state[x]` depends on `state[x-624]`, `state[x-623]`, and `state[x-227]` (via the generate step). Partial knowledge at any index propagates in both directions.

**Constraint propagation approach:**
```python
# Model: each state word starts as a set of 2^32 candidates
# Partial observation: narrow candidates for observed indices
# Propagate: for each constrained cell, narrow related cells

def propagate_forward(state_candidates, idx):
    """MT: state[idx+624] = f(state[idx], state[idx+1])"""
    for s0 in state_candidates[idx]:
        for s1 in state_candidates[idx + 1]:
            new_val = mt_twist(s0, s1)
            state_candidates[idx + 624].add(new_val)

def propagate_backward(state_candidates, idx):
    """Invert MT twist to constrain earlier states from later ones."""
    for val in state_candidates[idx]:
        # Recover state[idx-624] given state[idx] and state[idx-623]
        for s1 in state_candidates[idx - 623]:
            s0 = mt_untwist(val, s1)
            state_candidates[idx - 624].add(s0)

# After ~20 partial observations across different positions:
# Most cells converge to single candidates → full state determined
```

**Key insight:** MT19937's recurrence dependencies allow bidirectional constraint propagation — partial knowledge at multiple positions narrows candidates until the full 624-word state is determined. The number of partial observations needed scales inversely with bits leaked per observation: ~20 observations of 24+ bits each typically suffice.

**References:** HITCON CTF 2017

---

## Rule 86 Cellular Automaton PRNG Reversal via Z3 (Insomni'hack 2018)

**Pattern:** Wolfram elementary cellular automaton Rule 86 used as PRNG. Reverse through 128 rounds using Z3 Bool arrays:

```python
from z3 import *

def RULE86(x, y, z):
    return Or(And(Not(x), Not(y), z), And(Not(x), y, Not(z)),
              And(x, Not(y), Not(z)), And(x, y, Not(z)))

s = Solver()
state = [Bool(f'b{i}') for i in range(256)]
# Forward-compute 128 rounds symbolically
for round in range(128):
    new_state = [RULE86(state[(i-1)%256], state[i], state[(i+1)%256]) for i in range(256)]
    state = new_state
# Constrain final state to known output
for i, bit in enumerate(known_output):
    s.add(state[i] == (bit == 1))
s.check()
model = s.model()
```

**Key insight:** Elementary cellular automata are NOT injective -- multiple preimages may exist. But Z3 handles the search efficiently by treating each cell as a boolean variable and each rule application as a CNF clause. For Rule 86 specifically, the DNF has 4 terms (bits 1,2,4,6 of rule number 86 = 01010110). Use `s.push()`/`s.pop()` to iteratively backtrack through rounds. This approach generalizes to any elementary CA rule used as a PRNG: encode the rule's truth table as a boolean formula, compose symbolically for N rounds, and constrain to the known output.

**References:** Insomni'hack CTF 2018

---

## Java LCG Seed Meet-in-the-Middle via Partial Modulo (P.W.N. CTF 2018)

**Pattern:** Java `Random` outputs are only visible mod 62 (e.g., characters in a password). Full 48-bit seed search is infeasible, but partial output still leaks the LSB (`output mod 2`) and the high bits can be recovered independently because Java's LCG takes `(seed*a + c) >> 16`. Split into `2^18` low-bit search and `2^30` high-bit search.

```python
# Phase 1: enumerate 2^18 low-18-bit candidates whose nextInt(62) parities match known chars
for low in range(1 << 18):
    if simulate(low)[: K] == known_prefix: candidates.append(low)

# Phase 2: extend each candidate to 48 bits, matching next outputs
for low in candidates:
    for high in range(1 << 30):
        seed = (high << 18) | low
        if simulate(seed) == full_known: return seed
```

**Key insight:** Java's LCG discards the lowest 16 bits, so the low 18 bits only affect the LSB of each `nextInt()`. Split the seed at that boundary to turn an infeasible `2^48` search into two `2^18 + 2^30` passes.

**References:** P.W.N. CTF 2018 — PW API, writeup 12065

---

## LCG Backward Stepping via Multiplicative Inverse (P.W.N. CTF 2018)

**Pattern:** After recovering a forward seed, step backward with the modular inverse of the multiplier: `prev = a^-1 * (state - c) mod m`. For Java: `a^-1 = -35320271006875` mod `2^48`.

```python
M = 1 << 48
a_inv = pow(25214903917, -1, M)  # Java multiplier inverse
prev_state = (a_inv * (state - 11)) % M
```

**Key insight:** Every power-of-two-modulus LCG is invertible; once you have any state, you can walk the chain both directions without re-simulating from seed.

**References:** P.W.N. CTF 2018 — PW API, writeup 12065

---

## LFSR Bit-Fold Recovery from ASCII Parity (X-MAS CTF 2018)

**Pattern:** Custom PRNG XORs shifts of a 32-bit state into an 8-bit output byte. Observed bytes are ASCII (`top bit = 0`), so each observed byte leaks one parity bit of the internal state. Combine enough parity constraints via Gaussian elimination over GF(2) to recover state without brute force.

```python
# Collect parity constraints: each observed ASCII byte gives top_bit == 0
# Each bit of each byte is a linear combination of state bits
# Stack rows, solve in GF(2)
import numpy as np
A = np.array(constraint_rows, dtype=np.uint8)
b = np.array(known_bits,      dtype=np.uint8)
state = gf2_solve(A, b)
```

**Key insight:** Output byte folding does not hide the state; each output bit is still linear in the state. Use the ASCII constraint to turn output bytes into free parity equations.

**References:** X-MAS CTF 2018 — Probably Really Nice Goodies from Santa, writeup 12686

---

## Z3 Solve-Time Timing Oracle on PRNG (X-MAS CTF 2018)

**Pattern:** Cannot directly check a PRNG guess, but `Solver.check()` takes measurably longer for correct inputs because the constraint graph becomes UNSAT-hard instead of trivially SAT. Brute-force each character by timing Z3 with a tight timeout.

```python
from z3 import Solver, sat
for c in string.printable:
    s = Solver()
    s.set('timeout', 500)
    s.add(prng_constraints(flag + c, ciphertext))
    t = time.time()
    if s.check() == sat and (time.time() - t) > 0.4:
        flag += c
        break
```

**Key insight:** Many oracles run the solver internally; wrong guesses return fast because the SAT instance is already obviously satisfiable. Set a tight timeout and promote slow-solve candidates.

**References:** X-MAS CTF 2018 — Probably Really Nice Goodies from Santa, writeup 12686

---

## randcrack-Fed DSA k Prediction (CSAW CTF 2018)

**Pattern:** DSA signing uses `random.randrange()` to pick `k`. If the server also exposes a "forgot password" endpoint that leaks Python `random` outputs, feed 624 × 32-bit samples to `randcrack`, predict the next `k`, and solve `x = (s*k - h) * r^-1 mod q` for the private key.

```python
from randcrack import RandCrack
rc = RandCrack()
for _ in range(624 // 2):
    v = getrand64()
    rc.submit(v & 0xffffffff); rc.submit(v >> 32)
k = rc.predict_randrange(2, q)
x = ((s*k - h) * pow(r, -1, q)) % q
```

**Key insight:** Python's `random` is shared across all calls. Any endpoint that leaks `random` output poisons every other RNG consumer including DSA signing.

**References:** CSAW CTF 2018 — Disastrous Security Apparatus, writeup 12495

---

## Time-Seeded PRNG Offset via Format-String Global Write (FireShell 2019)

**Pattern:** Server seeds `srand((time(0)/10) + bet)` where `bet` is a writable global. Use a format string primitive to set `bet`, then predict all subsequent `rand()` outputs offline with matching libc.

```python
# 1. Format-string: %Xc%Y$n  writes desired bet value at &bet (0x602020)
# 2. Locally: predict rand() with C stdlib
from ctypes import CDLL
libc = CDLL('libc.so.6')
libc.srand((int(time.time())//10) + bet_value)
predicted = [libc.rand() for _ in range(n)]
```

**Key insight:** Shifting a known seed by a writable constant turns a time-of-day RNG into a deterministic RNG because the attacker now controls the whole seed.

**References:** FireShell CTF 2019 — casino, writeup 12916

---

## NTP-Poisoned PRNG State Leak via UUID XOR (RuCTFe 2018)

**Pattern:** Server derives UUIDs as `uuid = time ^ hash_state`. Register a user with a custom NTP endpoint returning `0x00`; the returned UUID now equals `hash_state` directly. Future UUIDs are predictable: `target_uuid ^ hash_state = required_timestamp`.

```python
# 1. Point the server at attacker-controlled NTP that returns 0
# 2. Register; received UUID == internal state
# 3. For desired uuid, compute needed timestamp = uuid ^ state
# 4. Send the crafted timestamp and read the message
```

**Key insight:** Any randomness mixed via XOR with a user-controlled value is the same as giving the attacker the state directly. Check all time sources for user control.

**References:** RuCTFe 2018 — vch, writeup 12146
slack-gif-creatoranthropics/skillsKnowledge and utilities for creating animated GIFs optimized for Slack. Provides constraints, validation tools, and animation concepts. Use when users request animated GIFs for Slack like "make me a GIF of X doing Y for Slack."Stars: 198kUpdated Claude CodeCodexVerifiedInstall
ponytailDietrichGebert/ponytailLazy senior dev mode for any coding task: the smallest change that fully solves it, and a reply a busy human understands in one read.Stars: 194kUpdated Claude CodeCodexVerifiedInstall
ponytail-debtDietrichGebert/ponytailHarvest every shortcut: comment into one debt ledger, so deferrals get tracked instead of forgotten. One-shot report.Stars: 194kUpdated Claude CodeCodexVerifiedInstall
ponytail-debtDietrichGebert/ponytailList every `shortcut:` comment (and older `ponytail:` ones) as a debt ledger. One-shot report, changes nothing. Use for "ponytail debt", "what did ponytail defer", "list the shortcuts", /ponytail-debt.Stars: 194kUpdated Claude CodeCodexVerifiedInstall