PRNG State Prediction — recovering the internal state of a non-cryptographic generator

Non-cryptographic PRNGs (LCG, Mersenne Twister, language-standard random) leak their internal state through their raw outputs; once you recover that state (or the seed that produced it), you predict every past and future output deterministically — no brute force of the "guess the number" kind required.

The signal that betrays it

Tokens, keys, nonces, or "random" challenge values come out of random, rand(), an LCG, or a generator seeded from something narrow (timestamp, PID, a small integer). Concrete tells: - The challenge literally frames itself as "guess the next number" or "predict the next roll" after showing you several previous ones. - Session tokens, shuffle orders, or CTF "randomized" values are suspiciously reproducible or short. - The seed is derived from something guessable and low-entropy: time(), a PID, a small brute-forceable range.

The critical triage step is distinguishing this from a CSPRNG. os.urandom, secrets, /dev/urandom, or anything explicitly built for cryptographic use is not predictable this way — if the challenge uses one of those, this technique is a dead end and you're looking at the wrong weakness. Non-cryptographic PRNGs are predictable *by design*: they optimize for statistical distribution and speed, never for output-to-state unrecoverability.

LCG (`x_{n+1} = a·x_n + c mod m`)

with as few as 4-5 consecutive raw outputs you can solve for all three unknowns a, c, m with no prior knowledge of any of them. The trick is taking successive differences to cancel out the unknowns one at a time: first differences eliminate the additive constant c, a further combination isolates the modulus m via a gcd over several candidate values (the true m is a common factor of all of them), and once m is known a falls out of a modular inverse. Field-tested reference: ``python from math import gcd def crack_lcg(xs): # xs: >=4 consecutive outputs diffs = [b - a for a, b in zip(xs, xs[1:])] zs = [c*a - b*b for a, b, c in zip(diffs, diffs[1:], diffs[2:])] m = 0 for z in zs: m = gcd(m, abs(z)) a = (xs[2]-xs[1]) * pow(xs[1]-xs[0], -1, m) % m c = (xs[1] - a*xs[0]) % m return a, c, m ` Once (a, c, m)` are known, the LCG is just a closed-form recurrence — walk it forward or backward from any known state to predict any output, past or future.

Mersenne Twister (Python's `random`, and MT19937 generally)

the state is 624 32-bit words, and each output word is a bijective "tempering" transform of one state word — so the transform is invertible ("untempering"). Observe 624 consecutive raw 32-bit outputs, untemper each one back to its state word, and you have cloned the entire internal state; from there the generator is fully deterministic in both directions. Don't hand-roll the untempering bit-shuffle under time pressure — reach for a maintained tool first: ``python from randcrack import RandCrack rc = RandCrack() for _ in range(624): rc.submit(get_output()) # 32-bit ints, in order rc.predict_getrandbits(32) ` Operational details that matter in practice: the 624 outputs must be consecutive and in the order the generator produced them — interleaving with other calls to the same random instance (e.g. an unrelated random.random() in the same challenge) desynchronizes the state and the clone silently predicts garbage. If the challenge exposes derived outputs (random.randint, random.choice, random.shuffle) rather than raw 32-bit words, you generally need to recover the raw getrandbits(32)` stream first, or use a tool build that models the specific derived call.

Small/guessable seed

if the generator was (re-)seeded from something narrow — a Unix timestamp within a known window, a small integer, a PID — skip state recovery entirely and just brute-force candidate seeds, replaying the generator for each candidate and matching against one known output. This is often faster than any algebraic recovery and is the first thing worth trying before reaching for the LCG or Mersenne Twister machinery above.

Truncated or modular-reduced outputs

if you only see part of each output (top bits only, or output taken mod some small value) rather than the full raw word, the clean algebraic/untempering approaches above don't directly apply — that's a bounded-error recovery problem, not an exact one, and routes to Hidden Number Problem — recovering a secret from many small-bounded-error samples instead.

What does NOT work

- Treating this as statistical randomness testing. PRNG prediction is not about detecting *that* a source is non-random (chi-squared tests, NIST test suites); it's about algebraically or combinatorially recovering the deterministic state. A generator can pass every statistical randomness test and still be trivially predictable once you have consecutive outputs — statistical quality and predictability are orthogonal properties, and Mersenne Twister is the textbook example of a generator with excellent statistical properties that's still "completely unsuitable for cryptographic purposes." - Trying LCG-style difference algebra on Mersenne Twister output, or vice versa. The two techniques are not interchangeable: LCG recovery exploits the *linear* recurrence directly; MT recovery exploits the *invertibility of the tempering transform* over a much larger, non-trivially-linear state. Misidentifying which generator you're facing (check the language/library defaults — Python, PHP, many "custom RNG" challenge scaffolds default to MT19937; hand-rolled or embedded/game-engine PRNGs are more often LCGs) wastes the attempt. - Assuming CSPRNGs are in scope at all. If the source is os.urandom/secrets/a hardware RNG, no amount of consecutive-output analysis recovers the state — that's the entire design point of a CSPRNG. Spend the triage effort up front confirming which family you're actually looking at before investing in either attack. - Requiring perfectly clean, uninterleaved output when it isn't given. With Mersenne Twister especially, if the observed outputs skip calls or come from a mix of random(), randint(), and shuffle() on the *same* underlying instance, naively feeding them as 624 raw words to a clone tool produces a state that looks plausible but predicts wrong values — the desync failure is silent, not an error, so always validate the cloned state against one more known output before trusting predictions from it.

Related

Berlekamp-Massey Algorithm — recover the minimal LFSR from raw keystream LFSR State Recovery — when the keystream itself hands you the seed Hidden Number Problem — recovering a secret from many small-bounded-error samples Hash Collisions and Weak Preimages — truncated tags and broken functions that fall to brute force or known tooling