1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Could you say what the $X_i$, $C_i$, $M_i$ and $Y_i$'s represent here? That would probably make it easier to answer your question. $\endgroup$ – Guut Boy Nov 2 '17 at 14:33
  • $\begingroup$ M - plain text, Y - encrypted text $\endgroup$ – Rokas.ma Nov 2 '17 at 14:34
  • $\begingroup$ If $Y_n$ is the ciphertext, then what is $C_n$? If it’s also ciphertext, you might want to edit your question and settle for using $C_n$ everywhere as that will avoid confusion. At first, I expected $Y_n$ to be the key and $X_n$ the ciphertext – which is obviously wrong when looking at your comment. $\endgroup$ – e-sushi Nov 2 '17 at 16:09
  • $\begingroup$ seems like a homework - so - what have you tried , what are you block with? If we see some effort, you will provide you a hint as well :) are you assuming that the 8 bit LFSR is the stream cipher? $\endgroup$ – gusto2 Nov 3 '17 at 9:30
1
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.