Cryptographic security of PHP mt_rand() function using Mersenne Twister algo

Question

At StackOverflow, this question has been asked. It uses additional random entropy and a hash method (among others) to try and create a cryptographically secure pseudo-random number generator for PHP. PHP seems to use a Mersenne Twister algorithm with a large internal state and high period, but Wikipedia assures me that Mersenne Twister is not cryptographically secure.

1. Could somebody please indicate what vulnerabilities there are using the PHP Mersenne Twister implementation as if it was cryptographically secure?

2. It would be very nice if somebody could go over to StackOverflow to see if the solution of H M is any better than using the default method and if it can be improved. Of course, the only really good way is to hold it against BSI and NIST test suites, but any improvement on the default implementation may be useful.

The source code in the stackoverflow question should be pretty easy to read, even for persons that are more mathematically inclined. Just as reference, I've included the source of the current methods within Zend PHP (which indeed seems to lack any kind of cryptographical algorithms).

The code is a partial copy of the Zend source for cryptographic analysis only. The ZEND source is protected by the PHP 3.01 license.

PS the initialization of the algorithm is just 32 or 64-bit, which is why I proposed at least to reseed it thoroughly on StackOverflow, but I wonder if that would be enough, as I've unfortunately proposed on StackOverflow (mostly because creating self-defined cryptographic algorithms by users is frowned upon).

---

basic_functions.h

#define MT_N (624)

php_uint32   state[MT_N+1];  /* state vector + 1 extra to not violate ANSI C */
php_uint32   *next;       /* next random value is computed from here */
int      left;        /* can *next++ this many times before reloading */
zend_bool mt_rand_is_seeded; /* Whether mt_rand() has been seeded */

---

rand.c

#define N             MT_N                 /* length of state vector */
#define M             (397)                /* a period parameter */
#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))

/* {{{ php_mt_reload
 */
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;
}
/* }}} */

/* {{{ php_mt_srand
 */
PHPAPI void php_mt_srand(php_uint32 seed TSRMLS_DC)
{
    /* Seed the generator with a simple uint32 */
    php_mt_initialize(seed, BG(state));
    php_mt_reload(TSRMLS_C);

    /* Seed only once */
    BG(mt_rand_is_seeded) = 1;
}
/* }}} */

/* {{{ php_mt_rand
 */
PHPAPI php_uint32 php_mt_rand(TSRMLS_D)
{
    /* Pull a 32-bit integer from the generator state
       Every other access function simply transforms the numbers extracted here */
    
    register php_uint32 s1;

    if (BG(left) == 0) {
        php_mt_reload(TSRMLS_C);
    }
    --BG(left);
        
    s1 = *BG(next)++;
    s1 ^= (s1 >> 11);
    s1 ^= (s1 <<  7) & 0x9d2c5680U;
    s1 ^= (s1 << 15) & 0xefc60000U;
    return ( s1 ^ (s1 >> 18) );
}
/* }}} */

Answer 1

Well, the chief vulnerability is that if an attacker is given a large enough sample of Mersenne Twister output, he can then predict future (and past) outputs. This is a gross violation of the properties that a cryptographically secure random number generator is supposed to have (where you're supposed to not even be able to tell if the random bit string could have been produced by the RNG in question).

As for how this weakness may be exploited, well, consider if you use the output of the MT as a keystream for a stream cipher (that is, you exclusive-or it with the plaintext to form the ciphertext). Then, if the user sees an encrypted message, and correctly guesses a part of the plaintext which is 2496 characters long, he can then immediately recover the internal MT state (and decrypt the entire message). Even worse, if the user has a section of ciphertext 19968 characters long for which he knows that the corresponding plaintext had all MSBits clear (say, he knows that section was standard ASCII), then he can then use that to decrypt the entire message (even though he initially had no idea beyond that what the contents of that section were).

The first weakness (2496 bytes of consecutive outputs allows the attacker to recover the MT state) is fairly straightforward to explain; we examine the last four operations of the MT immediately before the output:

s1 ^= (s1 >> 11);
s1 ^= (s1 << 7) & 0x9d2c5680U;
s1 ^= (s1 << 15) & 0xefc60000U;
return ( s1 ^ (s1 >> 18) );

If we look closely, we see that these operations are all invertible; that is, if we were given a 4 byte output of the MT, we can compute the value s1 had before these operations took place.

Now, what MT does is update its state, and then output its entire state (disguised by the above transformation). Now, an attacker can invert this transformation, and so directly observe the MT state. All he needs is 624 words of output (or 2496 bytes), and he has learned the entire state; he can advance the MT forwards (or backwards; the update function is invertible), and generate as much output as he wants.

Now, one possible nit is for this straight-forward approach to work, these 2496 bytes must correspond to one MT reload cycle; that is, start at a multiple of 2496 bytes from the start of the stream). While this would be easy to work around (if we're given 4991 consecutive bytes of output, then there will be a 2496 byte section that lives entirely within a reload cycle), it turns out that we needn't bother, because it's broken even worse than that.

The second weakness is that, if we can get just about any sample of 19968 bits of output, we can also recover the MT state, and it doesn't matter of all those bits are from the same MT reload cycle, or spread across multiple. As for how this works, well, when we examine the MT update and disguise functions, we see that they're all linear in GF(2); this means that all outputs are linear functions of the 19968 initial state bits. Hence, if we get 19968 output bits, we can form 19968 linear equations on the initial state bits, and solve that set of linear equations. That gives us the initial state, and from that, we can compute everything. Now, some sets of 19968 linear equations might not turn out to be linearly independent; in practice, all that means is that we might need a couple extra known bits, or just deal us having a couple of different possibilities for initial state; neither of these are significant difficulties for an attacker.

Hence, the bottom line is that Wikipedia is right, Mersenne Twister is not even slightly cryptographically secure, and should not used as if it were.