Attack insecure random number generators - predict outputs from seeds, crack LCGs, and untwist Mersenne Twister.

PRNG Attacks

Pseudo-Random Number Generator (PRNG) attacks target applications that use predictable or observable randomness. In CTF challenges, you typically receive PRNG output and must predict future values or recover the seed.

Beginner's Quick Guide

Goal: observe some outputs, identify the PRNG, and try predictable seeds or state-recovery.
Start simple: check whether the app seeds with the current time. If yes, try a small timestamp window.
If it's Python's random or PHP's mt_rand, aim to collect 624 consecutive 32-bit outputs and use a state-recovery (cloning) method.
If outputs look like a linear congruential generator (LCG) or Java Random, small algebraic attacks recover parameters quickly.

Keep examples below minimal and written in pure Python so you can run them locally.

Time-Based Seeds

The simplest PRNG vulnerability: using the current timestamp as the seed.

Explanation: try nearby timestamps to find which one reproduces the observed output.

import random, time

# Vulnerable server code:
random.seed(int(time.time()))
token = random.getrandbits(32)

Attack: Try all timestamps within a reasonable window:

import random, time

target_token = 0xdeadbeef  # token received from server
now = int(time.time())

for t in range(now - 3600, now + 1):   # try last hour
    random.seed(t)
    candidate = random.getrandbits(32)
    if candidate == target_token:
        print(f"Seed found: {t}")
        random.seed(t)
        print(f"Next token: {hex(random.getrandbits(32))}")
        break

Python `random` Module - MT19937 Internals

Python's random module uses Mersenne Twister (MT19937), a well-analyzed PRNG.

Key properties (in plain words):

If you can collect 624 full 32-bit outputs from random.getrandbits(32), you can reconstruct the generator's internal state.
After reconstruction, you can predict every future value exactly.

Cloning MT19937 State

If you can observe 624 consecutive 32-bit outputs:

Explanation: below is a compact, pure-Python approach that reverses MT19937 tempering and builds a predictor. It's written for learners; production code would use an existing tested library.

# Collect 624 observed 32-bit outputs (from the target)
# For each observed value 'y' call predictor.submit(y)

MASK_32 = 0xFFFFFFFF

def _unbitshift_right_xor(value, shift):
    res = 0
    for i in range(32):
        part = (value ^ (res >> shift)) & (1 << i)
        res |= part
    return res & MASK_32

def _unbitshift_left_xor_mask(value, shift, mask):
    res = 0
    for i in range(32):
        part = (value ^ ((res << shift) & mask)) & (1 << i)
        res |= part
    return res & MASK_32

def untemper(y):
    y = _unbitshift_right_xor(y, 18)
    y = _unbitshift_left_xor_mask(y, 15, 0xEFC60000)
    y = _unbitshift_left_xor_mask(y, 7, 0x9D2C5680)
    y = _unbitshift_right_xor(y, 11)
    return y

class SimpleMTPredictor:
    def __init__(self):
        self.state = []

    def submit(self, y32):
        self.state.append(untemper(y32))

    def ready(self):
        return len(self.state) >= 624

    def predict(self):
        if not self.ready():
            raise ValueError('need 624 values')
        import random
        mt = random.Random()
        # Python expects a state tuple: (version, (state...), index)
        state_tuple = tuple(self.state + [624])
        mt.setstate((3, state_tuple, None))
        return mt.getrandbits(32)

# Usage:
# p = SimpleMTPredictor()
# for _ in range(624):
#     p.submit(observed_value)
# next_value = p.predict()

Linear Congruential Generator (LCG)

LCGs are simple and completely breakable: X_{n+1} = (a * X_n + c) % m

Recover parameters (beginner version)

Explanation: given three consecutive outputs you can solve simple modular equations for a and c and then predict the next value.

def crack_lcg(x0, x1, x2, m):
    """Given three consecutive outputs, recover a and c."""
    from math import gcd

    # x1 = a*x0 + c (mod m)
    # x2 = a*x1 + c (mod m)
    # x2 - x1 = a*(x1 - x0) (mod m)

    # If modulus m is known:
    a = (x2 - x1) * pow(x1 - x0, -1, m) % m
    c = (x1 - a * x0) % m
    return a, c

# Example
m  = 2**32
x0, x1, x2 = 0x12345678, 0x9abcdef0, 0x1357924a   # from oracle
a, c = crack_lcg(x0, x1, x2, m)
print(f"a={hex(a)}, c={hex(c)}")

# Predict next:
x3 = (a * x2 + c) % m
print(hex(x3))

If you don't know the modulus m, gather many outputs and use the GCD trick shown below to recover m (advanced but often works):

def recover_lcg_modulus(outputs):
    from math import gcd
    from functools import reduce
    diffs = [outputs[i+1] - outputs[i] for i in range(len(outputs)-1)]
    t = [diffs[i+1]*diffs[i-1] - diffs[i]**2 for i in range(1, len(diffs)-1)]
    return abs(reduce(gcd, t))

Java `Random` (LCG)

Java's java.util.Random is an LCG with known parameters:

a = 0x5DEECE66DL
c = 0xBL
m = 2**48

Two consecutive nextInt() calls reveal the internal state:

def crack_java_random(r1, r2):
    a = 0x5DEECE66D
    c = 0xB
    m = 2**48

    # nextInt() uses top 32 bits of 48-bit state
    # brute-force the lower 16 bits
    for low in range(2**16):
        seed = (r1 << 16) | low
        next_seed = (a * seed + c) % m
        if (next_seed >> 16) == r2:
            print(f"Seed found: {seed}")
            return seed
    return None

# Predict next int from recovered seed
def java_next(seed):
    a = 0x5DEECE66D
    c = 0xB
    m = 2**48
    return (a * seed + c) % m

PHP `rand()` / `mt_rand()`

PHP's mt_rand() is MT19937-based. php_mt_seed can brute-force the seed:

# Install php_mt_seed
git clone https://github.com/openwall/php_mt_seed
cd php_mt_seed && make

# Given a known mt_rand output, find all possible seeds
./php_mt_seed 42   # find seeds that produce 42 as first mt_rand()

# Range example
./php_mt_seed 42 42 0 2147483647   # value range: 0 to RAND_MAX

Last updated on Aug 1, 2025

PRNG Attacks

On this page