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). Wouldn't this 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.
I think the reason this is not so popular is a combination of the three reasons you surmised. It is quite difficult to control properties of such a generator. There was at least one paper (can't recall reference) where the suggestion was to use a secret key to make a choice out of a collection of primitive LFSR polynomials.

I do know of another unpublished example, but I need to find my hardcopy of the manuscript to give you the gist of the design, which may take a day or two. It was never submitted for publication, to the best of my knowledge.