anneouyang / mt19937

Implementing and breaking the MT19937 Mersenne Twister pseudorandom number generator

MT19937

Implementing and breaking the MT19937 Mersenne Twister pseudorandom number generator; based on the challenges #21 to #23 of cryptopals

• Part I: Implement the MT19937 Mersenne Twister RNG
• Part II: Crack an MT19937 seed
• Part III: Clone an MT19937 RNG from its output

Overview

The Mersenne Twister is a pseudorandom number generator using a Mersenne prime (a prime number one less than a power of two: ) as its period length. MT19937 uses the Mersenne prime .

C++11 provides an implementation of std::mt19937 designed to replace rand() for several reasons:

1. MT19937 provides better pseudorandomness.
2. MT19937 has a longer period, which is .
3. MT19937 is able to generate random numbers from a larger range.

Part I: Implement the MT19937 Mersenne Twister RNG

A Simplified Explanation of the Algorithm

High Level Overview

A state of a Mersenne Twister is an array of n values of w bits each.

The array is initialized with a w-bit seed value to obtain state_0. Note that state_0 does not produce any outputs.

State transitions are achieved by a twist function. At each state, an output (a random number) can be obtained by . A state allows you to output n numbers before transitioning to the next state.

In the 32-bit MT19937, w = 32 and n = 624.

Initialization

The initialization function takes in a seed and generates the first state. Let

• f be a constant parameter; f = 1812433253
• X be the state array

= seed

= lowest w bits of () for

Twist Function

The twist function is called every n numbers to achieve the state transition. Let

• m be an offset where 1 <= m < n; m = 397
• r be the number of bits of the lower bitmask where 0 <= r <= w - 1; r = 31
• a be the coefficients of the rational normal form twist matrix; a = 0x9908B0DF
• A be the twist transformation in the rational normal form

The series is defined by the recurrence relation

where

Note because A is in the rational normal form, the multiplication can be efficiently expressed as where Is the lowest order bit of x

Temper Function

The tempering function returns a random number from a state and calls the twist function every n numbers. Let

• y be a temporary intermediate value
• x be the next value from the series
• z be the value returned from the algorithm
• d, b, c be TGFSR(R) tempering bitmasks; d = 0xFFFFFFFF, b = 0x9D2C5680, c = 0xEFC60000
• u, s, t, l be TGFSR(R) tempering bit shifts; u = 11, s = 7, t = 15, l = 18

The tempering operations are defined as

y = x ((x >> u) & d)

y = y ((y << s) & b)

y = y ((y << t) & c)

z = y (y >> l)

Implementation

The code can be found here.

Part II: Crack an MT19937 seed

The Setup

• Wait a random number of seconds between min_sleep_time and max_sleep_time.
• Seeds the RNG with the current Unix timestamp.
• Waits a random number of seconds again.
• Returns the first 32 bit output of the RNG.

Guess the seed from the output of the RNG.

Idea

Try all the possible seed values from (current time - max time) to (current time - min time). If the seed produces an RNG that generates the same output as the given RNG, it's likely that the seed has been recovered.

This example illustrates a vulnerability from using an imprecise clock as the seed, and it has an easy fix by seeding with a more precise clock. In C++, for example, the use ofstd::chrono::system_clock::now().time_since_epoch().count() is preferable to time(NULL) as the seed of an RNG.

Implementation

See code here for an implementation of the set up and a comparison of the two seeds (actual & guessed).

Part III: Clone an MT19937 RNG from its output

Idea

After observing n numbers, it is possible to predict all future iterations by reconstructing the internal state of the RNG, since the tempering function used to produce outputs is bijective and invertible. (However, this wouldn't work for the cryptographically secure variant CryptMT)

Inverting the temper transform involves applying the inverse of each operation of the tempering function in reverse order. Examine the code segment from the tempering function:

y = y ^ ((y >> MT19937.u) & MT19937.d)
y = y ^ ((y << MT19937.s) & MT19937.b)
y = y ^ ((y << MT19937.t) & MT19937.c)
y = y ^ (y >> MT19937.l)

Note that there are essentially two types of operations:

• Shift left + bitwise and
• Shift right + bitwise and

Inverting the (shift left + bitwise and) operation

For an operation rewrite the forward operation in terms of individual bits .

There are two cases:

• Case 1, if i + a >= w:
• Case 2, if i + a < w:

The inverses for the two cases are then:

• Case 1:
• Case 2:

Inverse the operation bit by bit starting from the trivial bits in Case 1.

Inverting the (shift right + bitwise and) operation

The inverse of the right shift operation is symmetrical:

• Case 1, if i < a:
• Case 2, if i >= a:

Implementation

See an efficient implementation that uses the symmetry and operations on bits here.

References

• https://en.wikipedia.org/wiki/Mersenne_Twister
• http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/ARTICLES/mt.pdf