Reverse engineering Mersenne Tornado with Linear Algebra

The Mersenne Tornado (MT) is a random quantity generator with good statistical properties however dangerous cryptographic properties. In buzzwords, it’s a PRNG however not a CSPRNG.

This publish will present how the interior state of a MT generator will be recovered from its output. We’ll do that utilizing linear algebra. The bit twiddling strategy is extra widespread and extra environment friendly, however the linear algebra strategy is conceptually easier.

How MT works

There are quite a few variations on the Mersenne Tornado. We’ll deal with the unique model that had inside state consists of vector x of size 640 full of 32-bit numbers. The concepts on this publish would apply equally to all MT variations.

The primary name to MT returns a “tempered” model of x[0]. The following name returned a tempered model of x[1], and so forth. After each 640 calls, the state is scrambled. This scrambling is the place the “twist” within the identify Mersenne Tornado comes from. (The Mersenne half comes from the truth that the interval of an MT generator is a Mersenne prime.)

Tempering

Right here is Python code for performing the tempering step.

def mood(y):
    y ^= (y >> 11) 
    y ^= (y <<  7) & 0x9d2c5680 
    y ^= (y << 15) & 0xefc60000 
    y ^= (y >> 18)  
    return y

Every step is reversible, and so the mood perform is reversible.

As a result of the tempering step is reversible, the primary output can be utilized to deduce the primary ingredient of the interior state, the second output to deduce the second ingredient, and so forth. After 640 calls one can know your entire inside state and predict the remainder of the generator’s output from then on.

Linear algebra

The bitwise operations above all correspond to linear operations over GF(2), the sphere with simply two components, 0 and 1. Addition on this area is XOR and multiplication is AND.

Every step corresponds to multiplying a vector of 32 bits on the left by a 32 × 32 matrix with entries which can be 0’s and 1’s, with the understanding that the sum of two bits is their XOR and the product of two bits is their AND. Equivalently, arithmetic is carried out mod 2. So you may compute the matrix-vector product as abnormal integers should you then cut back each integer mod 2.

We are going to discover the matrix M that corresponds to the mood operation and show that it’s invertible by discovering its inverse. This proves that tempering is invertible, and one may compute the inverse of tempering by multiplying by M⁻¹, although it might be extra environment friendly to undo temporing by bit twiddling.

One approach to get well a matrix is to multiplying by unit vectors e_i the place the ith part of e_i is 1 and the remainder of the elements are zero. Then

M e_i

is the ith column of M.

So we will discover the nth column of M by tempering 1 << n = 2ⁿ.

M = np.zeros((32, 32), dtype=int)
for i in vary(32):
    t = mood(1 << (31-i))
    s = f"{t:032b}"
    for j in vary(32):
        M[j, i] = int(s[j])

Let’s generate a random quantity and compute its tempered kind two methods: instantly and matrix multiplication.

x = random.getrandbits(32)
y = mood(x)
print(f"{y:032b}")

vx = np.array([int(b) for b in f"{x:032b}"]) # vector type of x
vy = M @ vx % 2 # vector type of y
print("".be a part of(str(b) for b in vy))

Each produce the identical bits:

10100101100101101100110101000110
10100101100101101100110101000110

We are able to discover the matrix illustration of the untemper perform by inverting the matrix M. Nonetheless, we have to invert it over the sphere GF(2), not over the integers or reals.

import galois
GF2 = galois.GF(2)
Minv = np.linalg.inv(GF2(M))

Listed here are visualizations of M and its inverse utilizing a black sq. for a 1 and a white sq. for a 0.

M:

M⁻¹:

The subsequent publish will again up and take a look at the linear algebra of the elements that comprise the Mersenne Tornado.