3
$\begingroup$

I have some trouble understanding what happens when a LFSR is clocked. I have tried many examples but I do not get the correct result. Can anyone point out my errors?

I have the following polynomial:

$$f(x)=1+x+x^5+x^6+x^8$$

I am working on this as a part of a known plaintext attack and I have the following keystream:

01010101000110101100

So, the first 8 bits of the keystream must be the IV for the LFSR, and the LFSR should do XOR on third ($x^2$), fourth ($x^3$), fifth ($x^4$) and seventh ($x^7$). In the next line the leftmost bit should go out and the rightmost the value from the XOR operation, the rest should be shifted one place from the line above, hence the structure:

$1 \times x^2 \cdots x^3 \cdots x^4 \cdots x^7$

0 1 0 1 0 1 0 1     
1 0 1 0 1 0 1 0  
0 1 0 1 0 1 0 0  
1 0 1 0 1 0 0 0  
0 1 0 1 0 0 0 0  

So, the rightmost bits in each line should be the continuing of the keystream after the 8th first bits, this seems to add up for the first three zeros, but after that it's not giving the keystream.

What am I doing wrong?

$\endgroup$
  • $\begingroup$ $z$ which is the feedback bit made up of xor of positions 1,5,6,8 is fed in at the next shift, so if your setup is correct you should have: $$ 1~2 ~3 ~4~ 5~ 6~ 7 ~8~~~z\\ 0~ 1~ 0~ 1~ 0~ 1~ 0~ 1~~~0 \\ 1~ 0 ~1~ 0~ 1~ 0~ 1~ 0~~~0 \\ 0~ 1~ 0~ 1~ 0 ~1~ 0~ 0~~~1 \\ 1~ 0~ 1~ 0~ 1~ 0~ 0~ 1~~~1\\ 0~ 1~ 0~ 1~ 0~ 0~ 1~ 1~~~1\\ $$ $\endgroup$ – kodlu Oct 13 '15 at 23:52
  • $\begingroup$ @kodlu There is no discernible relation between the the $z$ you obtain and the keystream in the question. $\endgroup$ – fgrieu Oct 14 '15 at 11:09
2
$\begingroup$

The keystream 01010101000110101100 can be deduced from its first 8 bits and the polynomial $f(x)=1+x+x^5+x^6+x^8$, as follows.

Start with $b_0=0$, $b_1=1$, $b_2=0$, $b_3=1$, $b_4=0$, $b_5=1$, $b_6=0$, $b_7=1$ (according to the first 8 bits of the keystream in reading order). And for $i$ increasing from $0$ apply the recurrence $b_{i+0}\oplus b_{i+1}\oplus b_{i+5}\oplus b_{i+6}\to b_{i+8}$, where the integers following $_+$ are the orders of the non-zero coefficients in the polynomial. That is:

  • $b_8\gets b_0\oplus b_1\oplus b_5\oplus b_6=0$
  • $b_9\gets b_1\oplus b_2\oplus b_6\oplus b_7=0$
  • $b_{10}\gets b_2\oplus b_3\oplus b_7\oplus b_8=0$
  • $b_{11}\gets b_3\oplus b_4\oplus b_8\oplus b_9=1$
  • $b_{12}\gets b_4\oplus b_5\oplus b_9\oplus b_{10}=1$
  • $b_{13}\gets b_5\oplus b_6\oplus b_{10}\oplus b_{11}=0$

This is using a Fibonnaci implementation of the LFSR, which is convenient since it is such that the first bits output are also the initial state of the LFSR. According to the convention used to define Fibonnaci and Galois implementations, we might be using the fact that the polynomial for a Fibonnaci implementation is the reflection of the polynomial for a Galois implementation (that is, the coefficient for the terms of order $j$ and $d-j$ are swapped, where $d$ is the degree of the polynomial).

If we wanted to apply a Galois implementation, we'd have to deal with the fact that the initial state of the LFSR is not the first bits of output, and thus not immediately known in the context of the question: by common conventions, the first bits of the given keystream simply are NOT the initial state of a Galois LFSR with polynomial $f(x)=1+x+x^5+x^6+x^8$ producing the rest of the sequence immediately afterwards.

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