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

  • $\begingroup$ 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}$. $\endgroup$ Dec 30 '14 at 3:25
  • $\begingroup$ unfortunately not. I just know that both LFSRs are 16 Bit and produce the keystream I wrote in my first post $\endgroup$
    – Nils Q.
    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.

  • $\begingroup$ Thank you for the detailed answer, this realy helped me a lot! $\endgroup$
    – Nils Q.
    Jan 5 '15 at 11:19

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.