I would highly recommend working through the challenges at http://cryptopals.com. The challenges give insight and practice into real attacks on weak cryptosystems.
Personally, I'm onto set 4, but I skipped the Mersenne Twister (MT) RNG to get there. Today I went back to those challenges and in this blog post I present my solution to challenge 23.
The Mersenne Twister generates Pseudo Random Numbers. It would be nice as an attacker to be able to predict future numbers by looking only at the earlier output of the MT Random Number Generator.
Firstly, an earlier challenge is to simply get an MT RNG working. I stole the code from https://github.com/james727/MTP. Is it bad that I copied the code? No. You will see there is much work needed to be done to break the MT RNG.
The key insight to the MT1997 RNG is that the complete internal state consists of 624 32-bit integers. If you can clone these integers, you can predict any future number generated by the RNG.
Another key insight is that each of these internal integers directly corresponds one-to-one to each one of the RNG outputs in sequential order. That is, given an array of 624 integers representing the state, state_1 corresponds random number 1, state_2 corresponds to random number 2 and so forth. After 624 numbers, the entire state gets 'twisted' and the process starts again.
The final insight into breaking the MT1997 RNG, is that the correspondence of each integer in the state to the random number output is a reversible function. That is, given an output from the RNG, you can reverse this output and reveal the associated integer in the state.
To put this all together, if you reverse the 624 integers that make up the state, you simply copy the state into your own MT1997 RNG and you have a working clone that can predict any future "random" number.
Like all things, the devil is in the details.
Remember the correspondence between the state and the RNG output. I will present to you the temper function in MT1997 which is the function that takes the integer state and produces an RNG output.
def temper(state):
y = state
y = y ^ (y >> 11)
y = y ^ ((y << 7) & 0x9D2C5680))
y = y ^ ((y << 15) & 0xEFC60000))
y = y ^ (y >> 18)
return y
This temper function takes in an integer from the state, and transforms it into the RNG output. However, remember our insight - this is a reversible function.
But how do we reverse it? Is there an analytical solution? Yes there is. But it is not immediately obvious to me in how to derive this. I will go for a simpler solution.
I will use an SMT solver (python-z3) to reverse this temper function.
from z3 import *
def untemper(out):
y1 = BitVec('y1', 32)
y2 = BitVec('y2', 32)
y3 = BitVec('y3', 32)
y4 = BitVec('y4', 32)
y = BitVecVal(out, 32)
s = Solver()
equations = [
y2 == y1 ^ (LShR(y1, 11)),
y3 == y2 ^ ((y2 << 7) & 0x9D2C5680),
y4 == y3 ^ ((y3 << 15) & 0xEFC60000),
y == y4 ^ (LShR(y4, 18))
]
s.add(equations)
s.check()
return s.model()[y1].as_long()
This function reverses the temper function and we can now recover the state from the RNG output.
Let's put this all together and demonstrate a complete attack. The following code will generate 1000 "random" numbers. I will use the first 624 numbers to reverse the complete state of the RNG. I clone the state and can now predict the remaining numbers.
Thanks for reading. Hopefully you and I can use the skills developed from completing the cryptopals challenges into attacking real-world but weak crypto implementations.
#!/usr/bin/python
from z3 import *
def untemper(out):
# y = state
# y = y ^ (y >> 11)
# y = y ^ ((y << 7) & 0x9D2C5680))
# y = y ^ ((y << 15) & 0xEFC60000))
# y = y ^ (y >> 18)
# return y
y1 = BitVec('y1', 32)
y2 = BitVec('y2', 32)
y3 = BitVec('y3', 32)
y4 = BitVec('y4', 32)
y = BitVecVal(out, 32)
s = Solver()
equations = [
y2 == y1 ^ (LShR(y1, 11)),
y3 == y2 ^ ((y2 << 7) & 0x9D2C5680),
y4 == y3 ^ ((y3 << 15) & 0xEFC60000),
y == y4 ^ (LShR(y4, 18))
]
s.add(equations)
s.check()
return s.model()[y1].as_long()
class mersenne_rng_cracker(object):
def __init__(self, state):
self.state = state
self.f = 1812433253
self.m = 397
self.u = 11
self.s = 7
self.b = 0x9D2C5680
self.t = 15
self.c = 0xEFC60000
self.l = 18
self.index = 624
self.lower_mask = (1<<31 def="" for="" i="" in="" range="" self.upper_mask="1<<31" self="" temp="self.int_32((self.state[i]&self.upper_mask)+(self.state[(i+1)%624]&self.lower_mask))" temp_shift="temp" twist="">>1
if temp%2 != 0:
temp_shift = temp_shift^0x9908b0df
self.state[i] = self.state[(i+self.m)%624]^temp_shift
self.index = 0
def get_random_number(self):
if self.index >= 624:
self.twist()
y = self.state[self.index]
y = y^(y>>self.u)
y = y^((y<>self.l)
self.index+=1
return self.int_32(y)
def int_32(self, number):
return int(0xFFFFFFFF & number)
class mersenne_rng(object):
def __init__(self, seed = 5489):
self.state = [0]*624
self.f = 1812433253
self.m = 397
self.u = 11
self.s = 7
self.b = 0x9D2C5680
self.t = 15
self.c = 0xEFC60000
self.l = 18
self.index = 624
self.lower_mask = (1<<31 for="" i-1="" i="" in="" range="" seed="" self.f="" self.int_32="" self.state="" self.upper_mask="1<<31" state="" update="">>30)) + i)
def twist(self):
for i in range(624):
temp = self.int_32((self.state[i]&self.upper_mask)+(self.state[(i+1)%624]&self.lower_mask))
temp_shift = temp>>1
if temp%2 != 0:
temp_shift = temp_shift^0x9908b0df
self.state[i] = self.state[(i+self.m)%624]^temp_shift
self.index = 0
def get_random_number(self):
if self.index >= 624:
self.twist()
y = self.state[self.index]
y = y^(y>>self.u)
y = y^((y<>self.l)
self.index+=1
return self.int_32(y)
def int_32(self, number):
return int(0xFFFFFFFF & number)
def crack_mt(numbers):
state = []
for n in numbers[0:624]:
state.append(untemper(n))
rng = mersenne_rng_cracker(state)
for n in numbers[624:]:
p = rng.get_random_number()
if p != n:
print("FAILED")
return
print(n, p)
print("SUCCESS!")
if __name__ == "__main__":
numbers = []
seed = 3521569528
rng = mersenne_rng(seed)
for i in range(1000):
n = rng.get_random_number()
numbers.append(n)
crack_mt(numbers)
