Are ciphertext-only attacks on LFSRs possible?

Question

Reading about LFSR, I know that breaking an LFSR by knowing it's design and having enough (plaintext, ciphertext) pairs is an relatively easy task but let's assume we know the design of LFSR and a just a long ciphertext, which is the result of xoring plaintext and LFSR output. Is there any way to decrypt the ciphertext?

For example suppose we have an LFSR with primitive characteristic polynomial $x^{51}+x^{9}+1$ and a 5600 bit ciphertext, is there any way to obtain plaintext which we already know is an English plaintext?

One brute-force approach is to try all $2^{51}$ possible seed values, xoring ciphertext with LFSR output and check if resulting plaintext has normal english letter entropy, but this approach gets harder and harder having a larger LFSR degree.

Answer 1

For text known to be ASCII encoded as octets with high-order bit of octets at zero, that reveals one bit of the output of the LFSR out of 8. It allows finding the original state of the LFSR from (say) the first 51 octets of the ciphertext by merely solving a system of linear boolean equations; then decipher the rest. There is no guesswork involved.

For 7-bit plus parity (where the high-order bit of each octet is the eXlusive-OR of the 7 others, or the complement of that), linear algebra works too.

Things get more difficult as the plaintext becomes less redundant. With 7-bit ASCII, noticing that space, digits, common punctuation and all lowercase letters are in range $[\mathtt{0x20}\dots\mathtt{0x3F}]\cup[\mathtt{0x60}\dots\mathtt{0x7F}]$, we know that every such 7-bit symbol has bit with weight 5 set, and there is fair chance that 51 such characters occur in a row somewhere in the 800-character plaintext. A guess of where allows to decode the rest, and it is easy to detect if the guess was right or not, thanks to characteristics of English text.

More generally, if 51 bits at almost any position can be guessed, then the rest is uniquely determined with basic linear algebra, and the guess is verifiable by checking that the resulting plaintext is appropriately redundant. An LFSR is such that a bad guess is weeded out with very high likelihood using very simple tests, unlikely to falsely rule out a bad guess. We can even do with a lenient chi-squared test that the plaintext resulting from a guess is random, and when it's not, it will be correct. This has the advantage of working regardless of language.

As long as enough bits can be guessed, these techniques work with LFSRs of hundreds of bits, including with unknown feedback polynomial (just add the taps as additional unknowns).