# Decrypting LFSR, knowing the beginning of the cyphertext, and nothing else

I have a cipher-text in binary, I know the beginning of the plain-text. I know that it is encrypted using LFSR, and I know nothing else.

How can I attack, and decrypt it?

What I have tried;

I converted the beginning of my plain-text to binary, which had a length of 84. My ciphertext's length is 952. I've got the first 84 bits of my cipher-text, XOR'd it with the known part of plain-text in binary, assuming that this would give me the first 84 bits of my key-stream, which was not periodic.

After that, I have used the Berlekamp-Massey algorithm with that 84 bits of the key-stream, to find the smallest possible connection polynomial that could be used to get it. (I don't know if it was definitely the connection polynomial for my key-stream, knowing that the long gap is huge and the known keystream is not periodic, it probably is not)

I then tried some shenanigans but nothing worked, I couldn't take any further steps. I've tried using the known cipher-text as the initial sequence and the polynomial I've got from the BM algorithm as the connection polynomial to generate another key, but that neither worked for my known plain-text or the rest, therefore assuming this was not a correct method to continue.

What further steps can be taken to decrypt this cipher?

• – kelalaka Nov 11 '20 at 20:26
• I don't have the seed. That question is heavily reliant on that. Should I brute-force some random seeds until I get a matching result? If that's the case, the shortest possible connection polynomial I've got from Berlekamp-Massey had a degree of 27. Doesn't that mean trying out 2^27 different seeds? That method therefore, does not seem feasible, which I have read before I asked my question. Point out if I'm missing something. – Ataberk Özbay Nov 11 '20 at 21:10
• The seed in your case the known plaintext. Use BM to construct the LFSR then fill it run and x-or the rest of the ciphertext. It is a little tricky to achieve since there is one way to check. – kelalaka Nov 11 '20 at 21:13
• Litte up for your effort, hard to see knowadays. The degree 27 from 84 bits is a clear indication that you have the correct polynomial. – kelalaka Nov 11 '20 at 21:24
• I've used the step you have showed before, it does not work. How do you conclude that I have the correct polynomial from degree of 27 and 84 bits? Is it for sure? I don't think that my algorithm is incorrect, but it might be as well. – Ataberk Özbay Nov 11 '20 at 21:43

If, when given the first 84 bits of keystream, a proper Berlekamp-Massey implementation outputs a polynomial of degree 27, then it also has found a 27-bit initial state, such that the 27-bit LFSR with this initial state has output starting with the 84-bit keystream. And one can have high confidence ($$p\approx1-2^{2\cdot27-84}>99.9999999\%$$) this is not by accident.