# Are there any LFSR-based ciphers with variable feedback polynomials?

All LFSR-based stream ciphers that I know of use a fixed feedback polynomial (i.e. the taps are always in the same position). I know that, at least for non-trivial output lengths, it is necessary to ensure that the polynomial is primitive to avoid creating an LFSR with a short cycle. Are there any published stream ciphers which use a secret-dependent or otherwise variable feedback polynomial? I am only aware of one proposed modification to A5/1. If there are good reasons why this design is so rare (just as there are good reasons why data-dependent rotations are rare), what are they? I can think of a few possibilities:

• The security improvement is too slight to be worth the added implementation complexity.

• Deterministically selecting a new feedback polynomial with good properties on-the-fly is difficult.

• There simply is not enough research into the behavior of LFSRs with variable taps.

To the best of my knowledge, an $$n$$-bit LFSR requires $$n$$ bits of keystream to determine the state. With secret feedback polynomials, $$2n$$ bits are required (using the Berlekamp-Massey algorithm to find the tap positions). It seems to me like this would be a simple way to make known-plaintext attacks harder.

Although I'm most curious about LFSRs, an answer describing NLFSRs would also be interesting.

• For, LFSR you can design one like, take two LFSR, let A's inner state defines the tap of the B. The problem will be, it will hard to analyze the periodicity and you may end up with all zero inner state for B. – kelalaka Aug 28 '19 at 8:27
• @kelalaka Assuming only very few bits are extracted for each new sequence of taps, wouldn't it be sufficient to ensure only that the state for B is non-zero and, if not, try again? It wouldn't likely give you a primitive polynomial, but that shouldn't be an issue if very few bits are extracted (so a short period wouldn't matter). – forest Aug 28 '19 at 8:30
• @kelalaka Do you mean like Snow v cipher? – hardyrama Aug 28 '19 at 8:32
• @hardyrama no. Use each of the inner states of A as the selector of taps of B. – kelalaka Aug 28 '19 at 8:37
• LSFRs were chosen historically for their ease of implementation and efficiency in hardware. Hardware is fixed. All the key-material has to go into the registers, basically. So this design idea wasn't considered in the starting period of "electronic" cryptography (after the rotor machines and such, an LSFR is a longer self-mutating wheel, so it was a logical step up). The focus was different. – Henno Brandsma Sep 2 '19 at 22:13