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. Java's java.util.Random, Microsoft's C runtime rand(), PHP's old rand(), and most hand-rolled generators in challenge source are LCGs. Glibc's rand() is the notable exception and is covered below. 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 the top 32 bits of it. 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.

Glibc's rand() is not an LCG

This one is worth knowing because the obvious approach fails silently. The C standard does not mandate an algorithm, and plenty of runtimes do use an LCG - but glibc's default generator, the one behind rand() on essentially every Linux box, is an additive feedback generator over a 31-word state. Solving for a and c from three outputs will produce numbers, and they will not predict anything.

The recurrence is addition rather than multiplication, which makes it easier rather than harder. The state advances as s[i] = (s[i-3] + s[i-31]) mod 2^32, and rand() returns s[i] >> 1. Dropping that low bit is the only complication: on the values you actually see, the relation holds up to a carry you cannot observe.

# glibc rand(): out[i] = (out[i-3] + out[i-31] + carry) mod 2**31
# with carry in {0, 1}, because rand() returned s[i] >> 1 and threw the
# low bit away. Thirty-one consecutive outputs are enough to continue it.
def next_candidates(outs):
    base = (outs[-3] + outs[-31]) % 2**31
    return base, (base + 1) % 2**31   # the true value is one of these

# Ignoring the carry is right about three times in four, which is exactly
# often enough to look correct in testing and fail on the flag. If you need
# certainty, keep both branches and prune with the next observed value.

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

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.