1
$\begingroup$

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?

$\endgroup$
8
  • $\begingroup$ See : Decrypting Ciphertext with partial Key Fragment using LFSR and Berlekamp-Massey $\endgroup$ – kelalaka Nov 11 '20 at 20:26
  • $\begingroup$ 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. $\endgroup$ – Ataberk Özbay Nov 11 '20 at 21:10
  • $\begingroup$ 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. $\endgroup$ – kelalaka Nov 11 '20 at 21:13
  • 1
    $\begingroup$ 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. $\endgroup$ – kelalaka Nov 11 '20 at 21:24
  • $\begingroup$ 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. $\endgroup$ – Ataberk Özbay Nov 11 '20 at 21:43
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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