Predicting the random: LCGs, Mersenne Twister, and seeded PRNGs

A surprising share of CTF crypto is not cryptography at all. It is a password-reset token, a session id, a shuffle, or a nonce produced by a generator that was designed to be *statistically* random and was never designed to be *unpredictable*. Those are different properties, and the gap between them is where these challenges live.

The distinction is worth stating precisely. A statistical PRNG passes randomness tests: its outputs are uniform, uncorrelated, and pass the usual batteries. A cryptographic PRNG additionally guarantees that seeing any number of outputs tells you nothing about the next one. random.random(), Math.random(), rand() and java.util.Random are the first kind. secrets, os.urandom, crypto.randomBytes and SecureRandom are the second. If a challenge uses one of the first list for anything security-relevant, that is the bug.

Linear congruential generators

An LCG is the simplest useful generator and the easiest to break: s[n+1] = (a * s[n] + c) mod m. C's rand(), Java's java.util.Random, and countless hand-rolled generators in challenge source are LCGs. The whole state *is* the last output (possibly truncated), so recovering the parameters recovers everything, forwards and backwards.

When you know the modulus

Two consecutive outputs give one equation, three give two, and two equations in two unknowns solve for a and c directly:

def solve_ac(s0, s1, s2, m):
    # s1 = a*s0 + c,  s2 = a*s1 + c  ->  s2 - s1 = a*(s1 - s0)
    a = (s2 - s1) * pow(s1 - s0, -1, m) % m
    c = (s1 - a * s0) % m
    return a, c

a, c = solve_ac(out[0], out[1], out[2], m)
nxt = (a * out[-1] + c) % m

When you do not know the modulus either

Recover m first, from differences. Build t[i] = s[i+1] - s[i]; then t[i+1] - a*t[i] = 0 mod m, so any determinant of the form t[i+2]*t[i] - t[i+1]^2 is a multiple of m. Take several and their GCD is m (or a small multiple of it) with high probability.

from math import gcd
from functools import reduce

def recover_m(s):
    t = [b - a for a, b in zip(s, s[1:])]
    z = [t[i + 2] * t[i] - t[i + 1] ** 2 for i in range(len(t) - 2)]
    return abs(reduce(gcd, z))

m = recover_m(outputs)          # six outputs is usually plenty
a, c = solve_ac(outputs[0], outputs[1], outputs[2], m)

The real-world nuisance is truncation. Most LCG APIs return only the high bits of the state - java.util.Random keeps a 48-bit state and hands you 32 bits, rand() on glibc masks to 31. With the low bits missing, the algebra above no longer closes and you move to lattice reduction: express the unknown low bits as a short vector in a lattice built from the recurrence, and let LLL find it. That is the same machinery as the biased-nonce attacks on ECDSA, and in practice you reach for a solver rather than writing it.

MT19937: 624 outputs and you own it

The Mersenne Twister is what random in Python, mt_rand in PHP, and Ruby's Random all use. Its state is 624 32-bit words. Each output is one state word passed through an invertible scrambling function called the *temper*. Invertible is the operative word: untemper 624 consecutive outputs and you have reconstructed the entire internal state, after which you can produce every future output exactly and, with a bit more work, every past one.

The temper is four steps of shift-and-XOR, and each is undone by iterating the same shape:

def unshift_right(x, shift):
    res = x
    for _ in range(32 // shift + 1):
        res = x ^ (res >> shift)
    return res & 0xFFFFFFFF

def unshift_left(x, shift, mask):
    res = x
    for _ in range(32 // shift + 1):
        res = x ^ ((res << shift) & mask)
    return res & 0xFFFFFFFF

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

import random
state = tuple(untemper(v) for v in observed_624)
clone = random.Random()
clone.setstate((3, state + (624,), None))   # index 624 forces a twist first
assert clone.getrandbits(32) == next_real_output

Two practical wrinkles. First, you need outputs that are genuinely consecutive 32-bit draws. getrandbits(32) gives you one per call; random() consumes *two* words to make a 53-bit float; randint may consume one or more depending on range. Work out how many words each call burns and index accordingly. Second, if the challenge only gives you the low bits of each output - randint(0, 255), say - you do not have full words, and you move to a bitwise linear-algebra solve over GF(2), because MT's transition is linear. That needs a few thousand samples rather than 624, and it still works.

Seeded with the clock

The other half of these challenges never needs state recovery at all, because the seed is guessable. random.seed(int(time.time())) has 86,400 possible values for a given day, and if you know the response timestamp to within a minute it has 60. srand(time(NULL)) is the same bug in C. Brute force the seed, regenerate the sequence, compare against an output you have already seen, and you are done.

import random, time

def find_seed(known_token, around=None, window=3600):
    t = int(around or time.time())
    for s in range(t - window, t + 1):
        random.seed(s)
        if token_from(random) == known_token:
            return s
    return None

Other guessable seeds worth trying before anything clever: a process id (32,768 values on Linux by default), a small counter, a username or email hashed to an int, the row id of the record, and 0. Challenge sources that call seed() at all are almost always seeding with something you can enumerate - a generator seeded properly would not need the call.

Recognising the generator from its output alone

That last row is the one to take seriously. If you have collected a thousand outputs and nothing correlates, stop. The generator is not the challenge, and the time is better spent on how the token is *used* - whether it is compared with == under a timing side channel, whether it is reflected somewhere, or whether the design has a boundary you can step around without predicting anything.

The method, condensed

1. Identify the generator from the source, or from the range and shape of the outputs.
2. If it is a CSPRNG, stop and attack something else.
3. Check the seed before the state. A guessable seed is a 60-iteration loop and needs no algebra.
4. For an LCG: recover m from GCDs of differences, then a and c from three outputs. Handle truncation with a lattice.
5. For MT19937: count how many 32-bit words each call consumes, collect 624 consecutive words, untemper, rebuild, predict.
6. For partial outputs of either: solve the recurrence over GF(2) with a few thousand samples instead.
7. Verify against an output you already hold before you spend your one submission on the prediction.

That last step is not optional. Every one of these attacks either works exactly or produces garbage, with nothing in between - so there is always a cheap check available, and using it costs one comparison against a value you already have.