owned this note
owned this note
Published
Linked with GitHub
# 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
```python=
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
```python=
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 :)