Inverting the Mersenne Twister's Temper
Sun Feb 17, 2019 · 1252 words

The Cryptopals challenge can be tricky based on how you approach it. Wanting to get to the details of particular tasks can be a daunting task.

Challenge 23 is one of those challenges. It seems easy to implement at first, but when you get to actual details, it’s not so easy. Especially for those of us who aren’t used to bitwise operations on a regular basis.

The challenge is to write an “untemper” function that takes an MT19937 output and transforms it back into the corresponding element of the MT19937 state array.

This is the “temper” code which we need to reverse:

``````	y := m.data[m.index]
y1 := y ^ ((y >> _U) & _D)
y2 := y1 ^ ((y1 << _S) & _B)
y3 := y2 ^ ((y2 << _T) & _C)
o := y3 ^ (y3 >> _L)``````

So given `o` we should be able to obtain y while propagating through intermediary states `(y1, y2, y3)`.

Lets take this one step at a time and break it down to obtaining each of those intermediary states.

## y3

`o` is obtained from `y3` and `_L (18)` as follows.

``o := y3 ^ (y3 >> _L)``

Easier to follow visually as shown below

We can see that the first `_L` bits of Y can be obtained by just taking the first `_L` bits of `o`. The `32 - _L` bits of `y3` can be obtained by doing an XOR of `o >> _L` with `o`. This is because `A ^ B = C` implies `A = B ^ C`.

So we’ve got a way to obtain `y3` from `o` and `_L`.

``y3 := o ^ (o >> _L)``

## y2

Now that we have `y3` we can move forward and obtain `y2` from `_T (15)` and `_C (0xEFC60000)`. Given the equation:

``y3 := y2 ^ ((y2 << _T) & _C)``

Which looks like

The last `_T` bits of `y3` are the same as `y2`. This is because `A & 0 = 0` and `A ^ 0 = A`. Which is visible from the diagram.

But this isn’t as simple as the previous step, is it? Yes and No.

No because you may have noticed that we only have `15 bits` of untangled data (The last 15). So left shifting it with `15` would only give us the next 15 bits. Which is totally 30 bits out of 32 bits.

But Yes because, if you noticed `_C`, its first two bits are `11`, which means that they don’t contribute to the output. We can think of this more clearly with the help of a diagram:

Notice:

• The first 2 bits only depend on `y2`
• The next 15 bits depend on `y2, _C`
• The last 15 bits are `y2` itself This is now totally similar to the previous problem, we can now easily derive `y2` from `y3` by doing
``y2 := y3 ^ ((y3 << _T) & _C)``

## y1

We’ve obtained `y3, y2` now lets retrieve `y1` from `y2` given `_S (7)` and `_B (0x9D2C5680)`.

``y2 := y1 ^ ((y1 << _S) & _B)``

Again, visualizing

This is similar to the previous block, but there’s one big problem, we only have 7 bits of actual data. Going by the previous block this means that using this 7 bits we can generate only the next 7 bits of data.

Since we’re only generating 7 bits, we’d have to mask `_B_` so as to only use the parts of `_B` which actually effect in the calculation of the next 7 bits.

Let me explain visually:

Therefore doing:

``````mask := 0x7f
b := _B & uint(mask << 7)
tmp1 := y2 ^ ((y2 << _S) & b)``````

would give us the following result, wherein the last 14 bits are of the original `y1`.

Now if you see the pattern, we can use this as the intermediate value and again do:

``````b := _B & uint(mask << 14)
tmp2 := tmp1 ^ ((tmp1 << _S) & b)``````

Which would now give us the next 7 bits as shown below:

Doing this two more times, we arrive with the final value:

Therefore the final result is just a loop with 4 iterations where we mask `_B` and do the same as the previous step. So the code for obtaining `y1` from `y2` is as follows.

``````y1 := y2
for i := 0; i < 4; i++ {
b := _B & uint32(mask << uint32(7 * (uint32(i) + 1)))
y1 := y1 ^ ((y1 << _S) & b)
}``````

## y

This is the final value we need to obtain, with `y1, y2, y3` in hand and `_U (11)` and `_D (0xFFFFFFFF)`. Lets look at the equation to derive `y1` from `y`. Which we need to reverse.

``y1 := y ^ ((y >> _U) & _D)``

Seems similar to the previous step, but anyone with a quick eye can see that `_D` is all `1s` so potentially we can ignore it and shorten the equation to

``y1 := y ^ (y >> _U)``

Now lets visualize this

This is pretty similar to how we solved `o <-> y3` but the only problem is that `_U < 32 - _U`. So we can use the same idea from the previous block. i.e. loop till we get the answer, since `(_U * 3) > 32`. We’d need 3 loops.

Therefore, the solution is:

``````y := y1
for i := 0; i < 3; i++ {
y1 := y1 ^ (y1 >> _U)
}``````

# Final Solution

Putting all of this together we can derive `y` from `o` as follows:

``````	y := o ^ (o >> _L)
y = y ^ ((y << _T) & _C)