# Cracking Random Number Generators - Part 4

In Part 3 of this series, we investigated the Mersenne Twister, and saw how with 624 consecutive integers obtained from it, we can predict every subsequent integer it will produce. In this part, we will look at how to calculate previous integers that it has produced. We will also discuss how we might go about determining the internal state of the Mersenne Twister if we are unable to get 624 consecutive integers.

## Breaking it down

Before we go on, let's look again at the algorithm for generating the next value for `state[i]`:

```
int y = (state[i] & 0x80000000) + (state[(i + 1) % 624] & 0x7fffffff);
int next = y >>> 1;
if ((y & 1L) == 1L) {
next ^= 0x9908b0df;
}
next ^= state[(i + 397) % 624];
```

We can see that there are 3 numbers from the previous state that are involved here, the old `state[i]`, `state[(i + 1) % mod 624]`, and `state[(i + 397) % mod 624]`. So, taking these 3 numbers, let's have a look at what this looks like in binary:

1. 11100110110101000100101111000001 // state[i] 2. 10101110111101011001001001011111 // state[i + 1] 3. 11101010010001001010000001001001 // state[i + 397] // y = state[i] & 0x80000000 | state[i + 1] & 0x7fffffff 4. 10101110111101011001001001011111 // y 5. 01010111011110101100100100101111 // next = y >>> 1 6. 11001110011100100111100111110000 // next ^= 0x9908b0df 7. 00100100001101101101100110111001 // next ^= state[i + 397]

If we work backwards from `i = 623`, then the pieces of information from the above equation is the end result (7), `state[i + 1]` and `state[i + 397]`. Starting from the result, the easiest step to unapply is the last one, undoing an xor is as simple as applying that same xor again. So we can get from 7 to 6 by xoring with `state[i + 397]`.

To get from 6 to 5 depends on whether `y` was odd, if it wasn't, then no operation was applied. But we can also see from the bitshift to the right applied from 4 to 5, that the first bit at 5 will always be `0`. Additionally, the first bit of the magic number xored at 6 is `1`. So, if the first bit of the number at 6 is `1`, then the magic number must have been applied, otherwise it hasn't. Hence, we can conditionally unapply step 5.

At this point, we have the first bit of the old `state[i]` calculated, in addition to the middle 30 bits of `state[i + 1]` calculated. We can also infer the last bit of `state[i + 1]`, it is the same as the last bit of `y`, and if `y` was odd, then the magic number was applied at step 6, otherwise it wasn't. We've already worked out whether the magic number was applied at step 6, so if it was, the last bit of `state[i + 1]` was `1`, or `0` otherwise.

However, as we work backwards through the state, we will already have calculated `state[i + 1]`, so determining its last 31 bits is not useful to us. What we really want is to determine the last 31 bits of `state[i]`. To do this we can apply the same transformations listed above to `state[i - 1]`. This will give us the last 31 bits of `state[i]`.

Putting it all together, our algorithm looks like this:

```
for (int i = 623; i >= 0; i--) {
int result = 0;
// first we calculate the first bit
int tmp = state[i];
tmp ^= state[(i + 397) % 624];
// if the first bit is odd, unapply magic
if ((tmp & 0x80000000) == 0x80000000) {
tmp ^= 0x9908b0df;
}
// the second bit of tmp is the first bit of the result
result = (tmp << 1) & 0x80000000;
// work out the remaining 31 bits
tmp = state[(i - 1 + 624) % 624];
tmp ^= state[(i + 396) % 624];
if ((tmp & 0x80000000) == 0x80000000) {
tmp ^= 0x9908b0df;
// since it was odd, the last bit must have been 1
result |= 1;
}
// extract the final 30 bits
result |= (tmp << 1) & 0x7fffffff;
state[i] = result;
}
```

## Dealing with non consecutive numbers

What happens, if when collecting 624 numbers from the application, that some other web request comes in at the same time and obtains a number. Our 624 numbers won't be consecutive. Can we detect that, and what can we do about it?. Detecting it is simple, having collected 624, we can predict the 625th, if it doesn't match the next number, then we know we've missed some.

Finding out how many numbers we've missed is the next task. Let's say we only missed the 624th number. This is fairly straight forward to detect, we would find that our `state[623]` is equal to what we were expecting to be the new `state[0]`. We would then know that we've missed one number, and by continuing to extract numbers from the application, and comparing that with the results we were expecting, we can narrow down which one.

A generalised algorithm for doing this is beyond the scope of these blog posts. But it should be clear from the reverse engineering of the steps that if most of the values are correct, but only a few are missing, determining what they were will be a fairly simple process.

We now know how to determine the internal state and how to go backwards as well as forwards in two of the most popular PRNG algorithms. In Part 5, we will look at what developers can do to ensure that their applications are safe against PRNG attacks.