A Problem with RNGs

Python's random module uses MT19937 to generate its numbers. How MT19937 works is that it is essentially a huge xor machine. In other words, the RNG has an internal state that contains $19968$ bits, and it generates it's numbers by a sequence of XOR of it's state. This means that given enough numbers that it generates, it is possible to solve for the internal state. The internal state can then be used to "clone" the RNG simply from the knowing the numbers it produces!

XOR of 2 bits is essentially an addition done mod 2. This means that the generated numbers of an MT19937 can be described with a matrix $M$ where the generated numbers $G$ are $G = MI$ where $I$ is the internal state of the MT19937. This enables us to simply solve for $I$ via Gaussian Elimination.

However, the internal state that we clone from original.png and original_enc.png has been forwarded $889$ times, the number of bytes in flag.png , since the source code encrypted flag.png first. This means, we have to reverse the RNG state $889$ times. Since MT19937 is a huge xor machine, we can use Gaussian Elimination reverse the RNG the desired number of times.

My code for the above steps are in the Github Repo MT19937-Symbolic-Execution-and-Solver and below is my code to solve this problem, and the decrypted image.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

import random

# https://github.com/JuliaPoo/MT19937-Symbolic-Execution-and-Solver
from MT19937 import MT19937, MT19937_symbolic

# Load images into memory
pt = open("original.png", "rb").read()
ct = open("original_enc.png", "rb").read()
enc = open("flag_enc.png", "rb").read()

# Get xor key
key = [x^y for x,y in zip(pt,ct)]

# Cloning MT19937 from data
rng_clone = MT19937(state_from_data = (key, 8))

# At this stage rng_clone is forwarded by len(enc), so we need to reverse it's state by len(enc)
# There is currently a bug where it sometimes doesn't work, so I
# forward rng_clone a random number of steps and reversing would work
shift = len(enc)
offset = 3544 # this offset works
print('Offset used:', offset)

# Forward rng_clone by offset
for _ in range(offset):
    rng_clone()

# Reverse rng_clone to before it started encrypting flag.png
rng_clone.reverse_states(shift + offset)

# Perform decryption of flag
dec = [(rng_clone() >> 24) ^ b for b in enc]

# Write decrypted flag
open("flag_dec.png", "wb").write(bytes(dec))