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

Question

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?

Answer 1

It's used the right tools, apparently with the right input, but missed how to use their output.

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.

Next steps:

• Understand where in the Berlekamp-Massey code used lies the 27-bit initial state, and output that. Basically, if the LFSR convention is that of a Fibonacci LFSR, that initial state is the 27 first terms of the input sequence analyzed (which is why it is often not an explicit output).
• Make an auxiliary program that implements this LFSR and produces keystream.
• Verify correctness of the above by checking that the first 84-bit output is the input to the Berlekamp-Massey code / the known keystream. If not, fix whatever is wrong.
• Generate as much keystream as needed to decipher.

Note: I recall I helped fix Berlekamp-Massey code in C. Try it online!. And someone wrote some elements of the auxiliary program (but it's non-trivial to link the two). Help on use of a particular tool is off-topic, especially for CTF or homework. And writing the auxiliary program (perhaps as an extension of the Berlekamp-Massey code) is a simple and essential exercise.