2
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – fgrieu ♦
    Commented Sep 28, 2018 at 9:08
  • 1
    $\begingroup$ @fgrieu's hint is divide and conquer. $\endgroup$
    – kelalaka
    Commented Sep 28, 2018 at 9:14
  • 1
    $\begingroup$ Alternate idea: could it be that you can use Berlekamp-Massey? $\endgroup$
    – fgrieu ♦
    Commented Sep 28, 2018 at 9:22

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.