Attack on LFSR key stream generator Alright this is a question I found on one of my books:


  Given is a stream cipher which uses a single LFSR as key stream
  generator. The LFSR has a degree of 256.



How many plaintext/ciphertext bit pairs are needed to launch a successful attack?
Describe all steps of the attack in detail and develop the formulae that need to be solved.


What I don't understand is how the author came with the answers.

First it seems that one would need 512 consecutive pairs of plaintext/ciphertext to launch an attack, which consists of creating a system of 256 linear equations and solving them, that much I understand. 

My question is: why do we need 512 consecutive plaintext/ciphertext pairs if we are going to construct a system of only 256 equations? Shouldn't it be 256 pairs?
The number of consecutive plaintext-ciphertext pairs $(x_i,y_i)$ of bits necessary is 256 if we know the LFSR taps (equivalently: the reduction polynomial) in advance, for the reason explained in the question. 512 is when we do not, because it creates more unknowns: the coefficients of the polynomial, in addition to the initial state.

If we know the LFSR taps, the initial state is all that's unknown, and is directly given by the vector of the first 256 values of $x_i\oplus y_i$ for an LFSR in Fibonnaci form (within a reflection, depending on notation). In Galois form, one option to find the initial state is to solve a system of equations.

If the LFSR taps are unknown, a standard algorithm is Berlekamp-Massey, which reconstructs the shortest LFSR state and feedback polynomial matching a given sequence of $x_i\oplus y_i$ (without taking the degree as input).



PS: I found the solution floating online, and adapted my notation to that. It is assumed that the feedback polynomial is initially unknown (or equivalently part of the key), hence the 512 pairs. The resolution is not explicitly per Berlekamp-Massey. Rather


With the LFSR in Fibonnaci form, the first 256 $x_i\oplus y_i$ give the initial internal state. The only remaining unknowns are the 256 coefficients $p_i$ of the feedback polynomial.
These 256 remaining unknowns are found by solving a system of 256 equations with 256 unknowns, built using the 512 $x_i\oplus y_i$. That system states that the internal state evolves from the first 256 $x_i\oplus y_i$ to the next 256 $x_i\oplus y_i$ after 256 steps with the reduction polynomial defined by the $p_i$.