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 :)