# Cracking Random Number Generators - Part 3

In Part 1 and Part 2 of this series we focussed on one of the simplest PRNG's, the linear congruential PRNG. We looked at detail into Java's implementation, and then wrote algorithms to crack the seed, and to calculate previous seeds from the current seed.

Not many other languages use a linear congruential PRNG. Originally, the C and C++ implementations of `rand()` were very simple linear congruential PRNGs, but these days they use more complex algorithms to generate higher quality random numbers. PHPs `rand()` function delegates to the platforms `rand()` function, so depending on the platform, it may be a linear congruential PRNG.

A much more popular PRNG algorithm is the Mersenne Twister. This is used by Ruby's `rand()` function, Pythons `random` module, and PHP's `mt_rand()` function.

The Mersenne Twister was invented in 1997. The most common implementation of it uses an internal state of 624 32 bit words (integers). These integers are handed out sequentially, applying a transform algorithm to each one before handing them out. Once all 624 integers have been handed out, an algorithm is applied to the state, to get the next 624 integers.

## Generating the next state

The algorithm for generating the next state is simple, it heavily uses bitwise operations such as shifts, masks and xors. The algorithm is as follows:

```
int[] state;
// Iterate through the state
for (i = 0; i < 624; i++) {
// y is the first bit of the current number,
// and the last 31 bits of the next number
int y = (state[i] & 0x80000000) + (state[(i + 1) % 624] & 0x7fffffff);
// first bitshift y by 1 to the right
int next = y >>> 1;
// xor it with the 397th next number
next ^= state[(i + 397) % 624];
// if y is odd, xor with magic number
if ((y & 1L) == 1L) {
next ^= 0x9908b0df;
}
// now we have the result
state[i] = next;
}
```

## Obtaining the next number

Before handing the next integer out, a transform is applied to each integer. This transform has 4 steps, each step involves xoring the number with a bit shifted and bit masked version of itself. The algorithm is as follows:

```
currentIndex++;
int tmp = state[currentIndex];
tmp ^= (tmp >>> 11);
tmp ^= (tmp << 7) & 0x9d2c5680;
tmp ^= (tmp << 15) & 0xefc60000;
tmp ^= (tmp >>> 18);
return tmp;
```

## Cracking the Mersenne Twister

Since the Mersenne Twister contains 624 integers of internal state that it hands out sequentially, obtaining 624 consecutive integers from the generator is the first step in cracking it. In a common webapp, this might be done by issuing 624 requests, and recording the token. If we can then undo the transform applied to these integers, we will then have the complete internal state. Having calculated that, we can predict every subsequent number.

In order to undo the transform, we will take it one step at a time, in reverse order. The step of the transform we need to understand first is therefore:

```
tmp ^= (tmp >>> 18);
```

Let's look at what this looks like in binary:

10110111010111100111111001110010tmp00000000000000000010110111010111100111111001110010tmp >>> 1810110111010111100101001110100101tmp ^ (tmp >>> 18)

As is clear from the bold bits above, we can easily work out what the first 18 bits of the previous number was, they are the same as the result. Taking those 18 bits, we can bitshift them across 18 bits, and xor them with the value, this will give us the entire number. A generalised algorithm can be written to do this for any arbitrary number of bits, and we can reuse this to reverse the first step as well:

```
int unBitshiftRightXor(int value, int shift) {
// we part of the value we are up to (with a width of shift bits)
int i = 0;
// we accumulate the result here
int result = 0;
// iterate until we've done the full 32 bits
while (i * shift < 32) {
// create a mask for this part
int partMask = (-1 << (32 - shift)) >>> (shift * i);
// obtain the part
int part = value & partMask;
// unapply the xor from the next part of the integer
value ^= part >>> shift;
// add the part to the result
result |= part;
i++;
}
return result;
}
```

This method can be used to reverse the two right bitshift operations. The left bitshift operations also include masking the bitshifted number with a magic number, so when we unapply `part` as above, we have to apply the mask to it, as follows:

```
int unBitshiftLeftXor(int value, int shift, int mask) {
// we part of the value we are up to (with a width of shift bits)
int i = 0;
// we accumulate the result here
int result = 0;
// iterate until we've done the full 32 bits
while (i * shift < 32) {
// create a mask for this part
int partMask = (-1 >>> (32 - shift)) << (shift * i);
// obtain the part
int part = value & partMask;
// unapply the xor from the next part of the integer
value ^= (part << shift) & mask;
// add the part to the result
result |= part;
i++;
}
return result;
}
```

Using these two functions, we can unapply the transformation applied to the numbers coming out of the PRNG:

```
int value = output;
value = unBitshiftRightXor(value, 18);
value = unBitshiftLeftXor(value, 15, 0xefc60000);
value = unBitshiftLeftXor(value, 7, 0x9d2c5680);
value = unBitshiftRightXor(value, 11);
```

Having applied the above algorithm to 624 consecutive numbers from the PRNG, we now have the complete state of the Mersenne Twister, and can easily determine every subsequent value. In Part 4 of the series, we'll investigate how to find previous values generated by the Mersenne Twister, and also discuss how to deal with being unable to get consecutive numbers out of the PRNG.