# Inverting the Mersenne Twister's Temper

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
mask := 0x7f
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)
mask := 0x7f
for i := 0; i < 4; i ++ {
b := _B & uint32(mask<<uint32(7*(uint32(i)+1)))
y = y ^ ((y << _S) & b)
}
for i := 0; i < 3; i ++ {
y = y ^ (y >> _U)
}
```