Insecure Randomness for CTF: Predicting PRNGs and the Mersenne Twister

The short answer: that guessing game is not a guess

You connect to a challenge. It says "guess the number I am thinking of" and insists the number is random. If that number came from Python's random module, it is not random in any sense that matters to an attacker. It is the deterministic output of a Mersenne Twister, and if you can observe enough of its earlier outputs you can reconstruct the generator's entire internal state and predict every future value exactly.

The whole playbook, in one paragraph: collect 624 consecutive 32-bit outputs, feed them to the randcrack library, and it clones the generator. If the server seeded with time() or a small integer, you skip the 624 outputs and brute the seed directly. If the generator is a Linear Congruential Generator (LCG) instead, a handful of outputs and some modular arithmetic recover its parameters. The only generators that resist this are the cryptographic ones: secrets and os.urandom. Everything below is the detail behind that paragraph.

from randcrack import RandCrack
rc = RandCrack()
for _ in range(624):
    rc.submit(get_one_32bit_output())   # observe 624 consecutive outputs
predicted = rc.predict_getrandbits(32)  # the very next output, exactly

Why is a PRNG not random, and when does that break security?

A Pseudo-Random Number Generator (PRNG) is a deterministic function. It holds an internal state, and each call mixes that state with a fixed algorithm to produce an output and a new state. Same starting state, same sequence of outputs, every single time. The "random" in the name means the output passes statistical tests for uniformity and lack of obvious correlation. It does not mean unpredictable.

Statistical randomness and cryptographic unpredictability are different properties. A generator can have one without the other.

The Mersenne Twister behind Python's random, Ruby's rand, PHP's mt_rand, and countless others is a textbook example. It passes nearly every statistical test for randomness, which is exactly why it is the default in so many languages. But it was never designed to be unpredictable, and its designers said so. The security boundary breaks the moment a program uses a statistical PRNG for something that needs to be secret or unguessable:

• A "guess my number" game where the prize is the flag.
• A session token, password-reset token, or nonce generated with random.
• A one-time key or pad derived from a seeded generator.
• Shuffling a deck, picking a CAPTCHA, or sampling a secret index.

In each case the value is supposed to be unguessable, but the generator is deterministic and its state is recoverable from its output. That gap is the whole vulnerability class.

How do you predict Python's random module?

Python's random module is the Mersenne Twister MT19937. Its internal state is an array of 624 unsigned 32-bit words plus an index. Every output word is produced by passing one state word through a fixed, invertible scrambling step called tempering. Because tempering is invertible, each 32-bit output reveals exactly one 32-bit word of internal state. Observe 624 consecutive outputs and you have recovered all 624 state words, which is the complete state.

With the full state in hand you can run the generator forward and reproduce every future output, or run the tempering inverse and reconstruct the past. There is no key, no work factor, no brute force. It is linear algebra over GF(2). The reference algorithm is documented by its authors at the Mersenne Twister home page; the recovery is a direct consequence of every step being reversible.

624 outputs in, and the generator has no secrets left. Tempering is a bijection, so each output hands you exactly one word of state.

Two practical wrinkles decide whether the recovery is clean:

• You need full 32-bit words. getrandbits(32) gives you exactly one untempered state word per call, which is the easiest case. If the challenge only exposes random() (a 53-bit float built from a 32-bit and a 27-bit draw) or a randint over a small range, you are seeing partial words and need either more samples or a solver that models the bit slicing.
• The 624 outputs must be consecutive. If the server consumes draws you do not see (logging, jitter, an unrelated call), your window has gaps and the naive state reconstruction fails. Count every call the server makes.

How do you use the randcrack library?

randcrack is the standard tool for this. You submit 624 consecutive 32-bit outputs, and it reconstructs the MT19937 state and then predicts. Install it and the API is three methods: submit, predict_getrandbits, and the convenience predictors that mirror the random module.

$ pip install randcrack

Here is the canonical solve against a service that leaks getrandbits(32) values and then asks you to predict the next one:

from randcrack import RandCrack
from pwn import remote      # or use any socket wrapper
io = remote('challenge.example', 1337)
rc = RandCrack()
# Phase 1: feed the cracker 624 consecutive 32-bit outputs.
for _ in range(624):
    line = io.recvline().strip()
    rc.submit(int(line))         # each value must be a full 32-bit draw
# Phase 2: the state is now fully reconstructed. Predict at will.
guess = rc.predict_getrandbits(32)
io.sendline(str(guess).encode())
print(io.recvline())             # flag, if the prediction matched

The same object can mirror higher-level calls so your prediction matches whatever method the server uses next. If the server's next move is random.randint(a, b) or random.random(), predict with the matching method so the draw counts line up exactly:

rc.predict_randint(0, 100)     # matches server's random.randint(0, 100)
rc.predict_random()            # matches server's random.random()
rc.predict_getrandbits(64)     # consumes two 32-bit draws internally
rc.predict_randrange(1, 1000)  # matches server's random.randrange(1, 1000)

If you cannot pull a clean stream of 32-bit words, randcrack is the wrong tool and you want a more general MT19937 symbolic solver that accepts partial-bit constraints. But for the common case, a service handing you whole getrandbits(32) values, this is a five-minute solve.

What if you cannot see 624 outputs? Brute the seed.

The 624-output attack needs a long observation window. Many challenges do not give you one. They seed the generator once, draw a single secret, and ask you to match it. You cannot reconstruct the state from one output. But you do not have to, because the seed itself is often guessable.

The classic mistake is random.seed(time.time()) or srand(time(NULL)). The seed is a timestamp, and you know roughly when the program ran. A timestamp is a small search space: if you know the run happened within a window of a few minutes, that is only a few hundred integer seeds to try. For each candidate seed, reseed a local generator, draw the same way the server did, and check whether the output matches.

import random, time
# Suppose the server did: random.seed(int(time.time())); secret = random.getrandbits(32)
# and you observed `secret`. Brute the timestamp around 'now'.
observed = 0x5f3a91c2          # the value the server revealed
now = int(time.time())
for seed in range(now - 600, now + 1):   # a 10-minute window backwards
    r = random.Random()
    r.seed(seed)
    if r.getrandbits(32) == observed:
        print('recovered seed:', seed)
        # now r is a perfect clone; draw the NEXT secret
        print('next value:', r.getrandbits(32))
        break

The same logic crushes any "small seed" design. If the challenge seeds with a PID, a loop counter, a four-digit number, or anything else with a bounded range, you enumerate the entire space. Even a 32-bit seed is brute-forceable offline in minutes if you only need to match one output and have a fast inner loop.

How do you recover a Linear Congruential Generator?

The other generator you will meet constantly is the Linear Congruential Generator. It is the engine behind C's rand(), Java's java.util.Random, and most hand-rolled "custom PRNGs" in challenges. The whole thing is one recurrence:

X_{n+1} = (a * X_n + c) mod m
a = multiplier
c = increment
m = modulus
X_0 = seed

If the challenge hands you raw consecutive outputs and you know a, c, and m, predicting the next output is one line of arithmetic. The interesting case is when the parameters are secret. You can recover all three from a short run of outputs using nothing but the greatest common divisor and modular inverses. The trick: differences between consecutive outputs are multiples of the modulus, so the GCD of several products of differences reveals m, after which a and c fall out of two linear equations.

from math import gcd
from functools import reduce
# outputs: a list of consecutive raw LCG states you observed (at least 6 or 7)
def recover_lcg(outputs):
    # Step 1: recover the modulus m from products of differences.
    diffs = [b - a for a, b in zip(outputs, outputs[1:])]
    zeroes = [t2 * t0 - t1 * t1
              for t0, t1, t2 in zip(diffs, diffs[1:], diffs[2:])]
    m = reduce(gcd, zeroes)        # m (or a small multiple of it)
    # Step 2: recover the multiplier a.
    #   X2 - X1 = a * (X1 - X0) mod m  ->  a = (X2 - X1) * inv(X1 - X0) mod m
    a = (outputs[2] - outputs[1]) * pow(outputs[1] - outputs[0], -1, m) % m
    # Step 3: recover the increment c.
    c = (outputs[1] - a * outputs[0]) % m
    return a, c, m
a, c, m = recover_lcg(observed_outputs)
nxt = (a * observed_outputs[-1] + c) % m   # predict the next output
print('a,c,m =', a, c, m, ' next =', nxt)

Two caveats make real LCG challenges harder than the textbook version. First, many generators only output the high bits of the state (Java returns bits 47 down to 16, not the full word), so you see a truncated state and need a lattice or a small brute force over the missing low bits. Second, if m is a known power of two, you can skip the GCD step entirely and solve the recurrence directly modulo that constant.

What is the difference between random, secrets, and os.urandom?

Everything above works because random is not a cryptographic generator. The fix, and the thing you cannot attack this way, is a Cryptographically Secure Pseudo-Random Number Generator (CSPRNG). Python ships two front doors to one: os.urandom and the secrets module that wraps it. Both pull from the operating system's entropy pool, which is reseeded from hardware noise and designed so that observing past output tells you nothing about future output.

The Python documentation is blunt about which to use. The random module docs carry an explicit warning that it should not be used for security purposes, and the secrets module docs exist precisely to be the secure alternative for tokens, keys, and anything an attacker should not predict.

Worked example: recovering future outputs end to end

Tie it together with a self-contained example. Below is a vulnerable "guessing game" server modeled on the common pattern, and the full attack that beats it. The server leaks 624 outputs (a typical "warm up" phase or a verbose log) and then challenges you to predict the next number for the flag.

# ---- vulnerable server (what the challenge runs) ----
import random
def serve():
    # 624 'practice' rounds where the server shows its draws
    for _ in range(624):
        print(random.getrandbits(32))
    # the real round: you must predict this to win
    secret = random.getrandbits(32)
    guess = int(input('your guess: '))
    print('FLAG' if guess == secret else 'wrong')

# ---- the attack (what you run) ----
from randcrack import RandCrack
from pwn import remote
io = remote('challenge.example', 1337)
rc = RandCrack()
# 1. Replay the 624 leaked outputs into the cracker.
for _ in range(624):
    rc.submit(int(io.recvline().strip()))
# 2. State is reconstructed. Predict the very next getrandbits(32).
secret = rc.predict_getrandbits(32)
# 3. Send the prediction back.
io.recvuntil(b'your guess: ')
io.sendline(str(secret).encode())
print(io.recvline().decode())   # -> FLAG

The attack has zero guessing in it. After the 624th submit, the RandCrack object is a bit-for-bit clone of the server's generator. Its next getrandbits(32) is identical to the server's next draw because both generators are now in the same state and run the same deterministic step. You did not break randomness; you observed that there was never any randomness to break.

The exploit is not a lucky guess with a 1-in-4-billion chance. It is a clone with a 100 percent hit rate.

picoCTF challenges that hinge on insecure randomness

Several picoCTF challenges are built directly on the ideas above. Work them in this order to climb from seed-bruteforce to full state recovery:

• picoCTF 2019 seed-spring is the cleanest introduction to seed prediction: the program seeds a generator from a known-ish value and you reproduce its output locally.
• picoCTF 2020 Guessing Game 1 and Guessing Game 2 are the canonical "predict the PRNG" pair. They push you from guessing a single value toward reconstructing the generator that produced it.
• picoCTF 2025 Guess My Cheese (Part 1) and Part 2 extend the guessing-game format with a crypto wrapper, so the randomness prediction is one stage of a longer chain.

For the surrounding crypto skills these challenges lean on, the RSA Attacks for CTF post covers the number-theory toolkit (modular inverses, GCD tricks) that the LCG recovery above reuses almost verbatim.

Quick reference

from randcrack import RandCrack
rc = RandCrack()
for v in outputs_624: rc.submit(v)   # 624 consecutive 32-bit draws
rc.predict_getrandbits(32)            # next getrandbits(32)
rc.predict_randint(a, b)              # next randint(a, b)
rc.predict_random()                   # next random() float
rc.predict_randrange(start, stop)     # next randrange(start, stop)

The mental model is the whole skill: a non-cryptographic generator has no secrets, only a state you have not reconstructed yet. Read the import line, count the outputs you can see, and pick the recovery that fits. The number was never random; it was just waiting for you to do the arithmetic.