Cryptopals Challenge 23: Clone an MT19937 RNG from its output

I've recently gotten the cryptography bug.

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)




Comments

  1. If you feel like asking from others “Can someone do my assignment” due to a lack subject knowledge. Then our assignment help Sydney helpers can easily prepare a highly informative assignment for you. With their help, you can also clear out all your concepts. So, without thinking much hire us now!

    ReplyDelete
  2. Very informative and well written post! Quite interesting and nice topic chosen for the post. My Assignment Help Au has been a pioneer within the Best Assignment Help online services and within the Australia and different countries ceaselessly for over Seven years. Make an order now for professional work, delivered on time and pure.

    ReplyDelete
  3. 'I'm highly impressed by the piece of thoughts you have shared on this portal. all the best
    connect us on Assignment Help can shed your burden of assignments with a return of qualitative assignments.
    Online Assignment Help
    Programming Assignment Help
    Management Assignment Help
    assignment experts
    Networking Assignment Help

    ReplyDelete
  4. Get that assignment writing service, which students look for these days, from us. Unlike other websites, My Assignment Help is relatively easier and user friendly, when it comes to ordering your assignments. All you have to do is simply fill out the form and sit relax.

    ReplyDelete
  5. This blog was a priceless gift for me, especially. It gives such authentic information which will be very helpful for me and other readers as well. Thanks for writing up this. You are amazing in writing blogs; we readers need more real-life articles from you in the future as well. It was really readable, and I am looking towards more articles like that. fairyseason coupon code

    ReplyDelete
  6. Thanks for sharing this blog. It is very useful for us. I really like this post very much. I am curious about some of them. I hope you will give more information on this topic in your next article. This is such a great resource that you are providing and you give it away for free. efficenter login

    ReplyDelete
  7. Emily Wickersham is one of the most popular personalities in the film industry. She is filled with beauty and talent. She became famous from the police television series NCIS, in which she played the role of Eleanor Bishop, a special agent. There are a lot of her followers, and many people like her hour-glass figure that makes her look more attractive.
    emily wickersham nude

    ReplyDelete
  8. It is my first visit to your blog, and I am very impressed with the articles that you serve. Give adequate knowledge for me. Thank you for sharing the useful material. I will be back for the more great post. Thanks for the blog loaded with so much information. Stopping by your blog helped me to get what I was looking for. wii u usb helper

    ReplyDelete

Post a comment

Popular posts from this blog

Heap Exploitation in Chrome's PartitionAlloc - part 1