ctf-writeups

Python Random Number Generator (MT19937) Attacks

This document provides techniques for attacking Python’s Mersenne Twister (MT19937) random number generator when partial output is leaked. Python’s random module uses MT19937, which is vulnerable to state recovery attacks when enough output bits are observed.

References:

Table of contents:

Known 32-bit Outputs (getrandbits(32))

When we observe full 32-bit outputs from random.getrandbits(32), we can recover the MT19937 state with 624 outputs (623 outputs give 2 possible solutions).

Attack principle: MT19937 has 624 32-bit words of internal state. Each output is a linear transformation of the state. With 624 equations (outputs), we can solve for the initial state.

Implementation:

# pip3 install git+https://github.com/maple3142/gf2bv
from gf2bv import LinearSystem
from gf2bv.crypto.mt import MT19937
import random

# assume we got some random numbers from the remote
all_nums = [random.getrandbits(32) for i in range(1000)]
# at least 623 numbers are required (but with 2 solutions)
# 624 numbers correspond to only one solution
known = all_nums[:624]

# create equations
ls = LinearSystem([32] * 624)
gen = ls.gens()
rng = MT19937(gen)
zeros = [gen[0] ^ int(0x80000000)]
for value in known:
    zeros.append(rng.getrandbits(32) ^ value)

# found solutions
for sol in ls.solve_all(zeros):
    print("Solved")

    # recreate random number generator
    RNG = MT19937(sol).to_python_random()
    for i in range(1000):
        assert RNG.getrandbits(32) == all_nums[i]

Known getrandbits(1)

Recover random number generator from 20258 (19937 is required for only one solution) 1-bit numbers generated by random.getrandbits(1):

# https://dexterjie.github.io/2025/10/20/2025%E5%BC%BA%E7%BD%91%E6%9D%AF/#Blurred%E2%80%94%E2%80%94%E5%A4%8D%E7%8E%B0
# pip3 install git+https://github.com/maple3142/gf2bv
from gf2bv import LinearSystem
from gf2bv.crypto.mt import MT19937
import random

# assume we got some random numbers from the remote
known = [random.getrandbits(1) for i in range(20258)]
all_nums = [random.getrandbits(32) for i in range(1000)]

# create equations
ls = LinearSystem([32] * 624)
gen = ls.gens()
rng = MT19937(gen)
zeros = [gen[0] ^ int(0x80000000)]
for value in known:
    zeros.append(rng.getrandbits(1) ^ value)

# found solutions
for sol in ls.solve_all(zeros):
    print("Solved")

    # recreate random number generator
    RNG = MT19937(sol).to_python_random()
    for i in range(20258):
        assert RNG.getrandbits(1) == known[i]

    for i in range(1000):
        assert RNG.getrandbits(32) == all_nums[i]

Known partial bits of getrandbits(16)

Recover random number generator from 3108 (3115 is required for only one solution) 16-bit (only higher 8 bits are known) numbers generated by random.getrandbits(16):

# https://dexterjie.github.io/2025/10/20/2025%E5%BC%BA%E7%BD%91%E6%9D%AF/#ezran
# pip3 install git+https://github.com/maple3142/gf2bv
from gf2bv import LinearSystem
from gf2bv.crypto.mt import MT19937
import random

# assume we got some random numbers from the remote
known = []
for i in range(3108):
    r1 = random.getrandbits(8)
    r2 = random.getrandbits(16)
    x = (pow(r1, 2 * i, 257) & 0xFF) ^ r2
    known.append(x)
all_nums = [random.getrandbits(32) for i in range(1000)]

# create equations
ls = LinearSystem([32] * 624)
gen = ls.gens()
rng = MT19937(gen)
zeros = [gen[0] ^ int(0x80000000)]
for value in known:
    rng.getrandbits(8)
    # the higher 8 bits of x equals to the higher 8 bits of r2
    zeros.append((rng.getrandbits(16) >> 8) ^ (value >> 8))

# found solutions
for sol in ls.solve_all(zeros):
    # recreate random number generator
    RNG = MT19937(sol).to_python_random()
    good = True
    for i in range(3108):
        r1 = RNG.getrandbits(8)
        r2 = RNG.getrandbits(16)
        x = (pow(r1, 2 * i, 257) & 0xFF) ^ r2
        if x != known[i]:
            # some solutions are wrong
            good = False

    if good:
        print("Solved")
        for i in range(1000):
            assert RNG.getrandbits(32) == all_nums[i]