# 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:**

- [2025 强网杯——Crypto 题解](<https://dexterjie.github.io/2025/10/20/2025强网杯/>)
- `gf2bv` library: [https://github.com/maple3142/gf2bv](<https://github.com/maple3142/gf2bv>)

## 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]
```