# How to crack LFSR with known plain text attack?

I'm learning stream ciphers and I'm at LFSR cipher, and I've been trying to solve the question that states if given a 5th degree lfsr with the cipher text 101101011110010 and its corresponding plain text 011001111111000, show how you can compromise the entire cipher.

I tried XORing the plain text and the cipher text, but it got me nowhere. There's also the finding the coefficients using linear equations, but I couldn't construct any equation.

So, how can I crack the LFSR with known plain text?

• You have $x^5 + x^3 + 1$ by on-line Berlakamp-Massey. For rest this may help you. – kelalaka Mar 24 '19 at 13:54

## 1 Answer

First of all, the length of string as a plain text you provided is 15. It should be the length of $$2^n$$. Second, if we summarize the question and the thing that we are looking for: you have an LFSR with seed and we have series of 0 and 1's which produced by this LFSR. We are interested to know what the equation of this LFSR is. We accept the given plain text with one 0 at end as the LFSR entry 0110011111110000 (seed) and the produced key-stream is 101101011110010. Now we can deduct in this way: each state of LFSR may or not may xor-ed till the first result (0) is produced. It is our first equation:

\$S16 xor S15 xor ... xor S1 = 0 (first bit of key-stream)


and besides we know that S16 until S1 has the values 0110011111110000.

For the next equation, We have the same equation except the result is (1), because it is the second bit of key-stream.

S16 xor S15 xor ... xor S1 = 1 (second bit of key-stream)


and again note that the value of S16 up-to S1 is is changed, because the LFSR has clocked one bit. So S16 ti to S1 is: 0011001111111000 As you can see we are getting new Equations. We gather as many as these equations until we can deduce that which of the S1 up-to S16 can attend in each one of the equations of "S16 xor S15 xor ... xor S1" that satisfies them. If we have and exact observation, there are 16 different states and based on the present of each state (S1 up-to S16) we have $$2^{16}$$ different LFSR equation that should be examined. In most of the cases in the cryptography, we never look for the equation of LFSR, because based on Kerckhoffs's principle, algorithm and the way which algorithm works, is known for every one and the only secret thing is KEY (seed) which in this question we did in the reverse of Kerckhoffs's principle and we concealed the algorithm (LFSR equation) and we had key! But this was the way how you can recover the LFSR equation.