# Attack on stream cipher that XOR's the output of two LFSRs

There are two LFSRs of different lengths: LFSR-17 and LFSR-25. LFSR-17 Initially contains a two byte seed, with a 1 injected into the fourth bit, for a total of 17 bits. LFSR-25 operates in the same way.

Of the 40-bit key, 2 bytes is seeded into the first LFSR and 3 bytes into the other. If the outputs of each LFSR were simply XORd to produce the keystream, how could we launch a known plaintext to retrieve the key?

• Hint: assume you know the first (say, 8) octets of the plaintext (and the corresponding ciphertext). Further, temporarily assume that you know the first 2 bytes of the key. How do you find the 3 others without guesswork? Now, if these first 2 bytes of the key are only a guess, how do you check that guess?
– fgrieu
Sep 28, 2018 at 9:08
• @fgrieu's hint is divide and conquer. Sep 28, 2018 at 9:14
• Alternate idea: could it be that you can use Berlekamp-Massey?
– fgrieu
Sep 28, 2018 at 9:22

## 1 Answer

There is another method named algebraic attack.

• Name each of the keys initial keys by $$l_{1i}$$ and $$l_{2i}$$.
• Since the LFSRs are linear and the combining function, x-or, is also linear compute algebraic equations
• Solve them. They construct a linear system of solutions.

Since only 38 bits are keys, you will only need 38-bit output if the if the equations are linearly independent.

if you use the Gaussian elimination method it will have $$40^3$$ operations.