Attack on stream cipher

Question

I am trying to decrypt a message, which was encrypted using a stream cipher and 8 bit LFSR.

First two letters of plain text are given: K and A.

To find $X_n$ I used following formula:

$$X_n = M_n \oplus Y_n$$

I found $X_1 = 81$ and $X_2 = 65$.

Assuming the next step would be to find $C_1,C_2,\dots,C_n$ then how can I find them?

Answer 1

Assuming as you specified that $X_1$ is $81$ and $X_2$ is $65$.
$X_1 || \ldots || X_n$ is your key stream in bits.

So you need to convert 81 and 65 into bits.

• $81 = \texttt{01010001}$
• $65 = \texttt{01100101}$

Thus your key stream is : $\texttt{01010001 01100101}$

You are attacking a 8 bit LFSR and we will assume Galois mode (because it is easier in this case).

The diagram of such LFSR is:

+-------------+-----------+-----------+-----------+------------+-----------+-----------+------------+
|             |           |           |           |            |           |           |            |
|            *a          *b          *c          *d           *e          *f          *g            |
|             |           |           |           |            |           |           |            |
|    +-----+  |  +-----+  |  +-----+  |  +-----+  |  +-----+   |  +-----+  |  +-----+  |  +-----+   |
|    |     |  |  |     |  |  |     |  |  |     |  |  |     |   |  |     |  |  |     |  |  |     |   |
+--->+  x0 +---->|  x1 +---->|  x2 +---->|  x3 +---->|  x4 +----->   x5 +---->|  x6 +---->|  x7 +-------> ...
     |     |     |     |     |     |     |     |     |     |      |     |     |     |     |     |
     +-----+     +-----+     +-----+     +-----+     +-----+      +-----+     +-----+     +-----+

where a b c d e f g are constants set to 0 or 1 to determine whether a bit influence the next result.

You must notice that the output is actually decided 8 rounds before being seen.

Thus you can see the LFSR as following parallel formulas:

$out \leftarrow x_7$
$x_7 \leftarrow x_6$
$x_6 \leftarrow x_5$
$x_5 \leftarrow x_4$
$x_4 \leftarrow x_3$
$x_3 \leftarrow x_2$
$x_2 \leftarrow x_1$
$x_1 \leftarrow x_0$
$x_0 \leftarrow f(x_0,x_1,x_2,x_3,x_4,x_5,x_6,x_7)$

where $$f(x_0,x_1,x_2,x_3,x_4,x_5,x_6,x_7) = \\ (x_0 \land a) \oplus (x_1 \land b) \oplus (x_2 \land c) \oplus (x_3 \land d) \oplus (x_4 \land e) \oplus (x_5 \land f) \oplus (x_6 \land g) \oplus x_7$$

From this you can deduce:

$f(1,0,0,0,1,0,1,0) = 0$ and the LFSR returned $0$
$f(0,1,0,0,0,1,0,1) = 1$ and the LFSR returned $1$
$f(1,0,1,0,0,0,1,0) = 1$ and the LFSR returned $0$
$\ldots$
and finally:
$f(0,1,0,0,1,1,0,1) = 1$ and the LFSR returned $1$

Notice that the first column is the second part of the stream : $\texttt{011}\ldots \texttt{1}$ and the second column (LFSR returned) is your first part of the stream: $\texttt{010}\ldots \texttt{1}$

Intermediates steps not provided as it is your homework.

Thus this gives you 8 equations to solve with 7 variables ($a,b,c,d,e,f,g$).

Equations not provided (nor solved) as it is your homework.

From this you have will have recovered the complete state and will know the formula to compute the next outputs bit, giving you full prediction on the stream to attack $C_1, \ldots, C_n$.