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. It’s not anymore a new thing among the Australian students to seek help from the online amway swot analysis if they are stuck with any. But if you are one of those students who trust the agencies blindly, it’s very likely for you to grow it as a bad habit. Know what are the pros of cons of hiring case study assignment help services here-
    Pros:
    • You will get plagiarism free assignment. Yes, due to limited knowledge of plagiarism, students often add content that is not original, leading them to accidental plagiarism. Many also do it intentionally. However, by seeking help from the online kia motors case study writing service, students will be able to get plagiarism-free assignments, any time they want. Professional assignment writers conduct thorough research of topics to ensure providing quality content so that students earn their desired grades.
    • As we have said earlier, best grades guarantee is always there if students choose the case study assignment sample to help them. Flawless and to-the-point answers always help the pupils get the perfect A with ease.

    ReplyDelete
  2. I suggest everyone to choose My Assignment Help Australia for getting the best guidance in their academia. The proficient experts assist as per the requirements and learning styles desired by the university.

    ReplyDelete
  3. To finish your project efficaciously, you must go for Help assignment. services. How will you complete your assignment when you have no one to ask for help? Tough situation to deal with! This situation usually arises when students choose other countries to pursue their higher education especially the U.S.A. Getting the exact solution to your assignment related problem would not issue anymore. Browse our online portal and avail the best assignment assistance services as per your subject requirements.
    assignment help service
    assignment help company
    Help with assignment
    Help with assignment writing

    ReplyDelete
  4. Nice Post..
    While printing any kind of important document, your HP printer is showing up some kinds of warning message like offline status. When you try to work on your printing device, you may receive the message like why does my printer keeps going offline issue. This offline status can put a halt on your printing device, so you should take the help from trained printer experts. Our techies are very experienced to bring your printer from offline to online mode successfully. Thus, you can work on your HP printer properly without facing any technical issues.

    ReplyDelete
  5. I am not doing anything out of the standard of importing data, and running a few queries. It works find for a little while, but then it decides to give this message. (Cannot open database ''. It may not be a database your application recognizes, or the file may be corrupt.) I am not doing anything but importing a text file, trying to export a text file from a query or table, trying to append data from one table to another etc. Once this error happens the database being use becomes useless and no amount of compacting and microsoft access cannot open database seems to help.

    ReplyDelete
  6. You shared a great post about cryptopals challenge. Here, people can get important information and share their ideas about this topic. In my views, we should share our ideas with each other because through this strategy, we can improve our knowledge and transfer our knowledge to new ones. Thanks for this work. Buy Dissertation Online.

    ReplyDelete
  7. Do you know how hard it is to find good SEO in this area? “I started an SEO business in this area to solve that problem.”
    Tech Markets News

    ReplyDelete
  8. We are providing a lot of good services. With the search engine, you will benefit from using our services. and much more benefit from my company..Thanks
    f95zone

    ReplyDelete

Post a Comment

Popular posts from this blog

Linux Heap TCache Poisoning