# Attack an stream cypher using 2 XORed LFSRs

We know that the Key were generated by 2 16Bit LFSRs (output of both is XORed together -> key)

I already extracted a 64 Bit key sequence, but how can I calculate the polynom of the LFSRs (and the initialisation vector)? Since we have 2 LFSRs XORed together which means its non-lineary I can't use a Matrix to calculate the coefficients, or am I wrong?

I hope somebody understands my problem and can give me some hint.

the known keystream: 1010 1110 0000 0011 1111 0010 1011 1001 0001 0100 1101 0111 1001 0011 1110 1101

-
do you know anything about the generator besides the size of the seed/state and that they are LFSRs? Number of non-zero coefficients? How bits are produced? Anything? I imagine that there are a good number of pairs of polynomials and seeds that could produce this result, but the state space is only around $2^{64}$. – Thomas M. DuBuisson Dec 30 '14 at 3:25
unfortunately not. I just know that both LFSRs are 16 Bit and produce the keystream I wrote in my first post – kristian Schurz Dec 30 '14 at 14:58

The fundamental property that you will use is that the output of an $A$-bit LSFR (using the $A$-bit feedback polynomial $P$) xored with the output of a $B$-bit LSFR (using the $B$-bit polynomial $Q$) is the same as the $A+B$ bit LSFR with the feedback polynomial $P \cdot Q$. And, don't forget, when you multiply the feedback polynomials, you use polynomial multiplication modulo 2.

Hence, we know your output can be generated by a 32-bit LSFR; the obvious thing to do is use the Berlekamp–Massey algorithm to find the LSFR, and once you have the feedback polynomial, factor it.

If you get a 32 bit LFSR with two 16 bit prime factors, that immediately gives you your answer.

If it factors into smaller factors, well, you need to search for a way to combine the smaller factors to two 16 bit polynomials. Here, you use the fundamental property in the other direction; for example, if the polynomials you find are 3, 7, 9, and 13 bits; then the obvious way to combine them are the 3 and 13 bit polynomials (which multiplied make up a 16 bit LSFR), and the 7 and 9 bit polynomials (which multiplied make up another 16 bit LSFR)

If BM finds a LSFR which is smaller than 32 bits, well, there are a couple ways for that to happen (after all, the fundamental property says that there exists a 32 bit LSFR that generates the output; it doesn't say that it's the smallest possible LSFR). One possible reason for this is that a factor LSFR might be initialized to zero; in that case, that LSFR won't contribute anything. Another reason would be that the two polynomials might share a factor. In any case, what that means is that you likely won't be able to come up with a unique answer as to the original polynomials.

-
Thank you for the detailed answer, this realy helped me a lot! – kristian Schurz Jan 5 at 11:19