Letting Go Of The Mersenne Twister

Recently I was interviewed by a crypto team from an international company, and at the end of the interview I was asked what my favouriate…

Letting Go Of The Mersenne Twister?

Recently I was interviewed by a crypto team from an international company, and at the end of the interview I was asked what my favouriate prime number was, and I said, that the ones I use for testing are 97, 997, 2¹⁹-1 and 2²⁵⁵-19. The first two are very simple ones I use for quick testing with simple numbers, the last one is used for complex method that require a 256-bit prime number (and is used in Curve 25519), and the other one is a Mersenne prime, and which is easy for me to remember, as in Python it is:

>>> 2**19–1
524287

So, for me, I just remember 19, and I have my two larger prime numbers, that I can test with. With 2¹⁹-1 only has 19 bits, it is often large enough to test. But, if I really wanted to find a large prime number, I would remember the vaue of 19,937, as 2¹⁹⁹³⁷−1 is a prime with 19,937 bits! It is likely though that this prime number would be too large for most of the applications I would use, and so I’m comfortable with 2²⁵⁵-19:

>>> 2**255–19
57896044618658097711785492504343953926634992332820282019728792003956564819949L

And a fast elliptic curve name FourQ uses a prime of 2¹²⁷-1:

FourQ: A Story of Elliptic Curves Microsoft Research and Cloudflare
Building a Fast Futuremedium.com

And so these Mersenne primes are used in public key encryption and in the generation of random numbers, but I recent paper identified a possible problem in using prime numbers for random number generators [here]:

The paper is fairly readable, and tries to engage the reader with a coverage of some core principles.

And so we increasingly exist in a world where random numbers are generated for our transactions, our network connections, and in our on-line accesses. If there was any weaknesses in the generation of these, we could leave large holes in the Internet. We might even be able to predict the weekly lottery, as here. In many cases we create our random numbers by generating a seed value, and which then generates a sequence of states. There should then be enough states that they do not end up repeating in a short interval, and where we cannot guess the next state knowing the current state.

It is a bold statement that we should dump the method, as it is by far the most popular method of creating random numbers, and is used extensively within many libraries including within mt_rand() in PHP and random.random() in Python.

The Twist

One of the most popular pseudorandom number generators (PRNGs) is the Mersenne Twister. It was created by Makoto Matsumoto and Takuji Nishimur in 1997 and it derives its name from its period length — which the number of values before the sequence repeats — and which is a Mersenne prime.

One of the most commonly used version of the Mersenne Twister algorithm is MT19937 and generates a 32-bit word length (using the Mersenne prime of 2¹⁹⁹³⁷−1. The method is named after Marin Mersenne and who was a 17th Century French Minim friar. His main contribution included his investigations of prime numbers, along with being seen as the father of acoustics

A Mersenne prime is defined as a prime number that is one less than a power of two. The general form is M_n=2^n−1 where n is an integer. The discovery of 2¹¹²¹³-1 was even given its own post mark:

The largest found is 2^{77232917}-1, and which was discovered by Jonathan Paceon on Boxing Day in 2017 (and it only the 50th Mersenne prime to be ever found). Since 1997, the Great Internet Mersenne Prime Search (GIMPS) distributed system has been used to find new Mersenne primes.

To determine the Mersenne primes, we can try prime numbers (2,3,5,7,11…) :

From Wikipedia, here are the first 20:

The Mersenne sequence becomes:

2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937, 21701, 23209, 44497, 86243, 110503, 132049, 216091, 756839, 859433, 1257787, 1398269, 2976221, 3021377, 6972593, 13466917, 20996011, 24036583, 25964951, 30402457, 32582657, 37156667, ..., 77232917 ...

A typical value used is 19,937 (2¹⁹⁹³⁷-1). Overall, PRNGs are deterministic and periodic, but the core strength of the Twister method is the pseudo sequence is unlikely to repeat with 2²¹⁹⁹³⁷-1 random numbers:

Overall the method uses sequential states, and where it should not be reasonably possible to know the next state from the current state. But some researchers have shown that “sparse” states can exist, and where there are very few ones or very few zeros, that the next state will also be sparse.

The method has been crititized for using up so many bits (19,937) for the states, and that for security a state value of 256 bits would still be enough, but have a strong effect on the overall performance of the method. A pseudo sequence repeating in 2²⁵⁶ can still be seen as being secure.

At the core of the paper is the failing of the method against two tests: Marsaglia’s binary-rank and the linear-complexity. The original authors of the method acknowledge these problems, but have outlined that it was always known that they would fail these tests.

For the method, the basic parameters are:

w: word size (in number of bits)
n: degree of recurrence
m: middle word, an offset used in the recurrence relation defining the series x, 1 ≤ m < n
r: separation point of one word, or the number of bits of the lower bitmask, 0 ≤ r ≤ w — 1
a: coefficients of the rational normal form twist matrix
b, c: TGFSR(R) tempering bitmasks
s, t: TGFSR(R) tempering bit shifts
u, d, l: additional Mersenne Twister tempering bit shifts/masks

and where 2^{nw−r−1} is a Mersenne prime. The details of the maths behind the method is [here]. The coefficients for MT19937 are:

(w, n, m, r) = (32, 624, 397, 31)
a = 9908B0DF16
(u, d) = (11, FFFFFFFF16)
(s, b) = (7, 9D2C568016)
(t, c) = (15, EFC6000016)
l = 18

The following code is taken from [here]:

class mersenne_rng(object):
    def __init__(self, seed = 5489):
        self.state = [0]*624
        self.f = 1812433253
        self.m = 397
        self.u = 11
        self.s = 7
        self.b = 0x9D2C5680
        self.t = 15
        self.c = 0xEFC60000
        self.l = 18
        self.index = 624
        self.lower_mask = (1<<31)-1
        self.upper_mask = 1<<31

        # update state
        self.state[0] = seed
        for i in range(1,624):
            self.state[i] = self.int_32(self.f*(self.state[i-1]^(self.state[i-1]>>30)) + i)

    def twist(self):
        for i in range(624):
            temp = self.int_32((self.state[i]&self.upper_mask)+(self.state[(i+1)%624]&self.lower_mask))
            temp_shift = temp>>1
            if temp%2 != 0:
                temp_shift = temp_shift^0x9908b0df
            self.state[i] = self.state[(i+self.m)%624]^temp_shift
        self.index = 0

    def get_random_number(self):
        if self.index >= 624:
            self.twist()
        y = self.state[self.index]
        y = y^(y>>self.u)
        y = y^((y<<self.s)&self.b)
        y = y^((y<<self.t)&self.c)
        y = y^(y>>self.l)
        self.index+=1
        return self.int_32(y)

    def int_32(self, number):
        return int(0xFFFFFFFF & number)

rng = mersenne_rng(seed=123)
for i in range(10):
   print rng.get_random_number()

Here is a sample run with a seed value of 123:

If you want to try this, click [here].

Conclusions

PRNGs are deterministic and periodic. With the periodic nature, we repeat the random sequence for the length of all the possible outputs. So if you are watching a slot machine, you might guest that the sequence for the output will eventually repeat. With the Mersenne Twister the period is a massive 2¹⁹⁹³⁷-1, which means that it is unlikely to repeat in a reasonable time frame. An important element is thus the seed value, as, if this can be guessed, it may be possible to replicate the whole sequence.

Another possible attack is on the state machine for generating the sequence, as a PRNG is deterministic. If some of these values are discovered, it may be possible to recreate others from it.

A Cryptographically Secure PRNG (CSPNG) should never repeat its sequence (non-periodic), and uses randomness based on random events (such as the time between system interrupts). Examples of CSPNG include /dev/urandom and CryptGenRandom. A CSPNG should also be non-deterministic.