1
$\begingroup$

Let's say I was given a file from which I know that it is encrypted using a 5 bit LFSR with a given poly.

I already know that it is possible to deduce the state of an LFSR and thus all future outputs if you're given a certain length of the LFSR's output. But if that output is xored with a file, I would assume you can't, because of course you don't know the content of the file.

Am I right, or is there a way I havent't thought of?

$\endgroup$
  • $\begingroup$ A first approach would probably be to guess certain (predictable) parts of the file. $\endgroup$ – SEJPM May 5 '18 at 10:54
4
$\begingroup$

First up: a 5 bit LFSR is horribly small, so getting the initial seed which was used is a piece of cake.

But indeed, it’ll basically boil down to a (rather quick) brute-force job where – unless that file contained purely random data – you’ld have good chances detecting the initial state (resulting in successful decryption) by just looking at the first couple of bytes.

Remember executable files, images, compressed files, and specific program files (like MS Word files) all come with specific headers. And text files can easily be detected too. UTF-8, UTF-16, etc mostly include BOMs (Byte Order Marks) and even if they don’t, they’re text – which greatly differs from random binary data. This makes "attacking" easier and can speed up things in scenarios where you’re facing multiple encrypted files each using different seeds.

That being said – never, ever, use a plain LFSR for encryption. If you really need speed, use a stream cipher (and don’t forget to use a MAC for authentication, as in "encrypt-then-MAC").

$\endgroup$
  • 1
    $\begingroup$ +1: Unless the file is the output of /dev/urandom (or equivalent), then parts of it will be guessable. $\endgroup$ – Ella Rose May 5 '18 at 14:22
1
$\begingroup$

One of the code breakers' tricks though is guessing the contents of that file. Imagine if you encrypted a bitmap of the sky. And they knew that. Where the clouds were blown out, pixel value = 255 repeated. You could estimate the position of those bytes within the image file. Then the boffins can trivially break a very large LFSR.

Although 5 bits (like $x^5 + x^3 +1$) is just a period of 31. That can be trivially forced until the plain text makes sense. Does a 31 period even count as brute force?

$\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.