# Misery Straightener

## Overview

We are given a stream generators

* It has a list of $13$ states $[S_{0}, S_{1}, \dots, S_{12}]$ and a constant $C$
* Everytime, it computes new states $S$ using the strange function next() and updates the list to be $[S, S_{0}, S_{1}, \dots, S_{11}]$. After that, it outputs $S_{12}$.

The process performs fastforward and then XOR the flag by OTP generated by the generator.

## Exploit

Look at the function name: next() and forward(), I think that the generator is, in fact, LFSR. As it's well-known of LFSR can be interpreted by matrix over $GF(2)$. So it seems we are able to find states after fastforward! Let's go deeper to the next() function.

### Analysis of next() function

res = self.pool[-1];
a = self.pool[12];
b = self.pool[6];
c = a ^ b;
c = c ^ (a >> 10);
c = c ^ ((b % (1 << 20)) << (self.bits - 20));
d = ((1 << self.bits) - 1) - c;
e = d;
if(self.pool[8] & 8):
	e ^= self.randomConstant;

self.pool.pop();
self.pool.insert(0,e);
return res;

First of all, notice that the calculation includes bits shift of states. Hence, it would be better to consider bits of states as varaibles.

**Notation.** Let $s_{i,j}, c_{j}$ be the $j$-th significant bit of $S_{i}$ and $C$, respectively.

Now, we're going to construct the matrix step-by-step.

### Line 4

Remember that XOR is a bit-wise operation, so we have $s_{0,j}^{'} = s_{6, j} \oplus s_{12, j}$. In terns of matrix, it is simply

$$
\begin{bmatrix}
s_{0, 0}^{'} \\ \vdots \\ s_{0,42}^{'}
\end{bmatrix}
= \begin{bmatrix}
0 & 0 & 0 & 0 & 0 & 0 & I & 0 & 0 & 0 & 0 & 0 & I
\end{bmatrix}
\begin{bmatrix}
s_{0, 0} \\ \vdots \\ s_{12,42}
\end{bmatrix}
$$

Here $0, I$ are zero matrix and identity matrix of size $42$.

### Line 5, Line 6

Next, we XOR the current $c$ by

(a >> 10), ((b % (1 << 20)) << (self.bits - 20))

This means $s_{0, j}^{'} = s_{0, j}^{'} \oplus s_{12, j+10} \oplus s_{6, j-22}$. Therefore, the equation can be updated to

$$
\begin{bmatrix}
s_{0, 0}^{'} \\ \vdots \\ s_{0,42}^{'}
\end{bmatrix}
= \begin{bmatrix}
0 & 0 & 0 & 0 & 0 & 0 & I + B & 0 & 0 & 0 & 0 & 0 & I + A
\end{bmatrix}
\begin{bmatrix}
s_{0, 0} \\ \vdots \\ s_{12,42}
\end{bmatrix}
$$

where $A, B$ are given by

$$
A =
\begin{bmatrix}
0_{10, 32} &, 0_{10, 10} \\ I_{32, 32} &, 0_{32,10}
\end{bmatrix}, \quad
B =
\begin{bmatrix}
0_{20, 22} &, I_{20, 20} \\ 0_{22, 22} &, 0_{22,20}
\end{bmatrix}
$$

### Line 7

Notice that substraction is equivalent to addtion over $GF(2)$, thus the operation is just $s_{0, j}^{'} = s_{0, j}^{'} \oplus 1$. Currently, we don't have $1$ in the vector, let's append a constant $1$ in the end!

$$
\begin{bmatrix}
s_{0, 0}^{'} \\ \vdots \\ s_{0,42}^{'}
\end{bmatrix}
= \begin{bmatrix}
0 & 0 & 0 & 0 & 0 & 0 & I + B & 0 & 0 & 0 & 0 & 0 & I + A & 1_{42,1}
\end{bmatrix}
\begin{bmatrix}
s_{0, 0} \\ \vdots \\ s_{12,42} \\ 1
\end{bmatrix}
$$

Here, $1_{42,1}$ is the column vector of size $42$ and all the element is $1$.

### Line 9, 10

Rephrase the if condition: $s_{0, j}^{'} = s_{0, j}^{'} \oplus c_{j}$ when $s_{8, j} = 1$. This can be further simplified as $s_{0, j}^{'} = s_{0, j}^{'} \oplus s_{8,j}$ when $c_{j}=1$. Assume $c$ is the column vector $[c_{0}, \dots, c_{42}]^{T}$, we form the matrix

$$
C =
\begin{bmatrix}
0_{42, 38} & c & 0_{42, 3}
\end{bmatrix}
$$

and obtain the matrix equation

$$
\begin{bmatrix}
s_{0, 0}^{'} \\ \vdots \\ s_{0,42}^{'}
\end{bmatrix}
= \begin{bmatrix}
0 & 0 & 0 & 0 & 0 & 0 & I + B & 0 & C & 0 & 0 & 0 & I + A & 1_{42,1}
\end{bmatrix}
\begin{bmatrix}
s_{0, 0} \\ \vdots \\ s_{12,42} \\ 1
\end{bmatrix}
$$

Finally, we only need to take $S_{1}^{'}, \dots, S_{12}^{'} = S_{0}, \dots, S_{11}$ into consideration. To make it simple, let $M$ be the matrix

$$
M = \begin{bmatrix}
0 & 0 & 0 & 0 & 0 & 0 & I + B & 0 & C & 0 & 0 & 0 & I + A & 1_{42,1}
\end{bmatrix}
$$

We have the following transition equation

$$
\begin{bmatrix}
s_{0, 0}^{'} \\ \vdots \\ s_{12,42}^{'} \\ 1
\end{bmatrix}
= \begin{bmatrix}
M & \\ I_{12*42} & 0_{42, 12*42+1} \\ 0_{1, 13*42} & 1
\end{bmatrix}
\begin{bmatrix}
s_{0, 0} \\ \vdots \\ s_{12,42} \\ 1
\end{bmatrix}
$$

Here the python code for matrix construction

N = 13*42
M = Matrix(Zmod(2), N+1, N+1)
M[42:N, :N-42] = Matrix.identity(N-42) 
M[-1, -1] = 1
randomConstant_bits = [0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1]
for i in range(42):
    M[i, i+12*42] = 1
    M[i, i+6*42] = 1
    if i >= 10:
        M[i, i+12*42 - 10] = 1
    if i < 20:
        M[i, i+6*42 + 22] = 1
    M[i, -1] = 1
    M[i, 9*42-4] = randomConstant_bits[i]

It's easy to find the OTP now :)