Cloning a Mersenne Twister Random Number Generator from its output

As was said in my last post, I’m doing cryptopals. Just last night I finished Challenge 23. I was able to successfully clone a 32-bit Mersenne Twister pseudorandom number generator (PRNG) from its output. You can see how I did this by checking out my solution in my github repo.

If you’re like me when first looking at this, you probably are overwhelmed. So, I thought I would take a moment to try to explain how and why this works. I can’t do this, though, without acknowledging this blog post and its author. It was incredibly helpful in understanding how to reverse the tempering function of the mersenne twister.

Also, I want to address the question posed in the original problem:

How would you modify MT19937 to make this attack hard? What would happen if you subjected each tempered output to a cryptographic hash?

Let’s get going…

Preface

What’s interesting about the mersenne twister is that the PRNG retains an array within that manages the generator’s state. It has to do this in order to ensure that it doesn’t start repeating numbers. The period of a PRNG is how long it takes before the generator starts repeating numbers, and the primary perk to this particular PRNG is that it has a super long period: 2^19937-1 . (That’s a huge number.)

When the PRNG gives you a “random number,” it pulls a number out of its state array and subjects that number to “tempering.” What that means is that the number is subjected to several bitwise mathematical operations, and is then returned. Here’s what that looks like in the version of the twister that I implemented. (The capital letters are constants … Pay attention to the two private functions.)

    /**
     * temper a value
     * @param untempered the value to be tempered
     * @return the tempered value
     */
    int temper(int untempered) {
        int y = temperRightShift(untempered, U, D);
        y = temperLeftShift(y, S, B);
        y = temperLeftShift(y, T, C);
        y = temperRightShift(y, L, FULL_MASK);
        return y;
    }

    private int temperRightShift(final int y, final int shift, final int mask) {
        return y ^ ((y >>> shift) & mask);
    }

    private int temperLeftShift(final int y, final int shift, final int mask) {
        return y ^ ((y << shift) & mask);
    }

There are two “versions,” so to speak, of transformation: a left shift operation and a right shift operation. In both cases, the original value is subjected to a bit shift, then and’d against a mask, and then xor’d against the original.

What’s not obvious

If you haven’t yet, you really should go check out this article. If you have, I’m going to try to do this in a way that is perhaps a bit clearer than he put it. I’m going to use the number -252645136, which when written out in binary, looks like this.

1111 0000 1111 0000 1111 0000 1111 0000

Nice and easy to see what’s going on when the number pattern is super obvious. Let’s perform and then undo the third transformation using this number: y := y xor ((y << s) and b), where y is our number, s is the shifting constant 7, and b is the bitmask 0x9D2C5680.

Let’s start with the first operation: Shift our number 7 digits to the left and AND it against b. Let’s call the result y’. An asterisk is an original part of the number, and a – is something that came in as a result of a shift.

                                
  **** **** **** **** **** **** *--- ----     
  0111 1000 0111 1000 0111 1000 0000 0000  <-- 7-bit shift left
& 1001 1101 0010 1100 0101 0110 1000 0000  <-- 0x9D2C5680
-----------------------------------------
  0001 1000 0010 1000 0101 0000 0000 0000  <-- y'

Gonna pause there before i do the next operation. Look at the last 7 bits of y’. It’s all 0s. If you’ve ever done XOR before, you know that XOR-ing something against 0 will leave you with what you started with. It’s the same as AND-ing something against a 1. No change. And, the reason that those figures are 0 is because of the shift. (If the original number ended in all 1’s, the last 7 bits of the shifted number would still all be 0. For this reason, I said 7 bits and not 12.)

This means a piece of the original number is going to remain in our final result. That is important, but it’s not super obvious!

Let’s do the next operation: XOR the result against the unmodified original. Let’s call the result z, like bloglien does.

  1111 0000 1111 0000 1111 0000 1111 0000  <-- y
X 0001 1000 0010 1000 0101 0000 0000 0000  <-- y' 
-----------------------------------------
  1110 1000 1101 1000 1010 0000 1111 0000  <-- z

Now, to undo this. If you didn’t know this, I should say that XOR is reversible. q XOR r = t and t XOR r = q. This means that all we have to do recover the original is recover y’.

But how can we do that? y’ is gone once the operation is done. Is it recoverable?

Yes. yes it is, but only because you retain a piece of the original y in z. That’s what’s not obvious in this at first glance.

Recovering y’ and y

In order to recover the original y, y’ is needed. How does this work? Bloglien calls it “waterfalling.” I call it “redoing the original operation 7 bits at a time.” As I do this, I’m going to leave out what I call “extraneous bits,” (which after masking is always 0). If they’re not of immediate concern, I’m just not going to write them. I will, however, keep them vertically aligned with the other figures. If you want to pull a piece of paper out and fill out every bit, feel free.

Step one: Mask the portion of z that contains the unaltered portion of y.

  1110 1000 1101 1000 1010 0000 1111 0000 <-- z
& 0000 0000 0000 0000 0000 0000 0111 1111 <-- mask the lowest 7 bits
-----------------------------------------
                                 111 0000 <-- what we are left with

Step two: Just like we did to the original y, shift 7 bits to the left and AND that against b (the masking constant), and poof! We have 7 bits of y’.

                        11 1000 0         <-- lowest 7 bits shifted left 7 bits
                      & 01 0110 1         <-- 7 bits of b in these positions
                      -----------
                        01 0000 0         <-- 7 bits of recovered y'

Step three: XOR the recovered y’ against z to recover 7 more bits of y.

                        10 0000 1         <-- 7 bits of z
                    XOR 01 0000 0         <-- 7 bits of recovered y'
                    -------------
                        11 0000 1         <-- 7 more bits of y

Step four: REPEAT! You have 7 more bits of y. Mask them, shift them, AND against b to recover 7 more bits of y’, and then XOR against z to recover 7 more bits of y.

               1 1000 01                  <-- masked and shifted
             & 0 1100 01                  <-- b
            ------------
               0 1000 01                  <-- recovered y'
           XOR 1 1000 10                  <-- z
           -------------
               1 0000 11                  <-- y

       1000 011                           <-- y, masked and shifted
     & 1101 001                           <-- b
     ----------
       1000 001                           <-- recovered y'
   XOR 1000 110                           <-- z
   ------------
       0000 111                           <-- recovered y

  0111                                    <-- y, masked and shifted (we lose 3 bits)
& 1001                                    <-- b
------ 
  0001                                    <-- recovered y'
X 1110                                    <-- z
------ 
  1111                                    <-- recovered y

Now, take all the bits of recovered y and concatenate them, and you get:

 1111 0000 1111 0000 1111 0000 1111 0000  <-- the original y

That’s the algorithm. Mask, shift, AND, XOR, Repeat. I could redo this for a right shift to show you how it works in the opposite direction, but it’s the same except that you retain the most significant bits of a number instead of the least significant bits. Also, the right shift is less difficult than the left because the shifting constants are larger, meaning you run out of room more quickly. (With the fourth transformation, you don’t even need to repeat. It’s one and done.)

In code

So how does “untempering” look when you put it in code? Well, pretty close to tempering, but with a few gotchas.

The first line in each unTemper function calls on a method to convert an integer into a bitmask. In other words, 7 becomes 0000 0000 0000 0000 0000 0000 0111 1111 in convertIntToRightEndMask. The definition for this can be found here.

From there, the mask is moved horizontally by shift bits, starting with 0 (since blockMaskShift starts at 0). Then we AND it against z, which allows us to get the original bits that stayed from the previous transformation all by themselves. Then we shift those bits, mask them against the constant, and XOR it against z, and repeat. It works for left or right shifts the exact same. Plug in the right inputs (which come from the MT spec), and you can undo tempering.

    int unTemper(final int tempered) {
        int y = unTemperRightShift(tempered, L, FULL_MASK);
        y = unTemperLeftShift(y, T, C);
        y = unTemperLeftShift(y, S, B);
        y = unTemperRightShift(y, U, D);
        return y;
    }

    private int unTemperRightShift(final int z, final int shift, final int maskConst) {
        final int blockMask = convertIntToLeftEndMask(shift);
        int zp = z;
        for (int blockMaskShift = 0; blockMaskShift < (W - shift); blockMaskShift += shift) {
            zp = zp ^ (((zp & (blockMask >>> blockMaskShift)) >>> shift) & maskConst);
        }
        return zp;
    }

    private int unTemperLeftShift(final int z, final int shift, final int maskConst) {
        final int blockMask = convertIntToRightEndMask(shift);
        int zp = z;
        for (int blockMaskShift = 0; blockMaskShift < (W - shift); blockMaskShift += shift) {
            zp = zp ^ (((zp & (blockMask << blockMaskShift)) << shift) & maskConst);
        }
        return zp;
    }

Clone the twister

Once you’ve got past the hard part of undoing the twister, all you need is a sample of 624 outputs from a Mersenne Twister PRNG to clone it. You just “untemper” those outputs, overwrite the PRNG’s internal state array with the untempered values, and boom. You’re done. See here.

Addressing their question

So, to go back to the authors’ original question about this…

How would you modify MT19937 to make this attack hard? What would happen if you subjected each tempered output to a cryptographic hash?

Good question.

If you subject the state value to a cryptographic hash at any point during tempering, you wipe out the original bits tied to the state value, which makes it super difficult to recover inasmuch as the cryptographic hash is super difficult to crack (which they generally are). At that point, you’d basically be left with brute force, trying at most 2^32-1 different permutations to see if an untempered value matches the cryptographic hash. This would effectively make the PRNG far more secure since you wouldn’t be able to easily undo it.

In sum, if you get rid of the original bits from the untempered inputs, then you make it super hard to recover the untempered value tied to the PRNG’s state array.

This is cool

At first, this sort of blew my mind, but as I worked through it a few times in code and on paper, it ended up being one of the most fun challenges to complete in cryptopals. That’s the reason behind this lengthy write-up: I really got excited about this problem. I hope that others are just as fun to crack in the future.

Peace! -LH