/ctf-crypto

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.

Table of Contents

• Mersenne Twister Seed Recovery from Subset Sum (Tokyo Westerns 2017)
• MT19937 State Recovery via Constraint Propagation (HITCON 2017)
• Rule 86 Cellular Automaton PRNG Reversal via Z3 (Insomni'hack 2018)
• Java LCG Seed Meet-in-the-Middle via Partial Modulo (P.W.N. CTF 2018)
• LCG Backward Stepping via Multiplicative Inverse (P.W.N. CTF 2018)
• LFSR Bit-Fold Recovery from ASCII Parity (X-MAS CTF 2018)
• Z3 Solve-Time Timing Oracle on PRNG (X-MAS CTF 2018)
• randcrack-Fed DSA k Prediction (CSAW CTF 2018)
• Time-Seeded PRNG Offset via Format-String Global Write (FireShell 2019)
• 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:

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.

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:

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:

# 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:

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.

# 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.

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.

# 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.

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.

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.

# 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.

# 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