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

Question

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.

Answer 1

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.

Edit:

If we use a secret key to choose one of a collection of primitive polynomials, this would clearly be a way of keeping control of the macro properties of the generator. But it is unclear how much extra security this buys, since assuming the polynomials to be roughly the same degree, the security properties of the keystream won't change much [assuming LFSRs are input to something like a combination generator, or other nonlinear filtering function] and the attacker's required complexity won't improve.

Answer 2

This answer is independent of the first; It addresses @forest's request though almost a year later.

The results summarized are from an applied mathematics conference paper Cumulative Shift Register Sequences by K J Horadam [Melbourne, Australia, early 1990s] from which a book was produced but this book is not widely available. I will only provide a summary. I think it's an interesting topic but as far as I know no work along these lines have been published in the open literature. Someone who has time may choose to follow this lead.

The usual correspondence between LFSRs and generating polynomials is well known. The generalization rests on the idea of using a given binary sequence $\{c_t\}_{t\geq 1}$ to generate a new cumulative binary $\{k_t\}_{t\geq 0}$ sequence defined by $$ k_t=c_1 k_{t-1}+c_2 k_{t-2}+\cdots+c_{t-1}k_1+c_t k_0,\quad t\geq 1, $$ with the initial condition $k_0=1.$ All operations are modulo $2.$ Therefore $$ k_0=1,\\ k_1=c_1 k_0=c_1, k_2=c_1 k_1+c_2, k_0=c_1^2+c_2=c_1+c_2,\\ k_3=c_1+c_3~(detail~omitted),\\ k_4=c_1c_2+c_1+c_2+c_4,\\ \cdots $$

The cumulative shift register sequence is modelled as the contents of an infinite register slid to the left, one stage per clock tick, past the oppositely oriented shift register containing $\{c_t\}_{t\geq 1,$ which controls which register contents are XORed and fed back into the first empty stage.

Linear recursive sequences (usual LFSR sequences) are simply the special case of those cumulative recursive sequences that are generated by a "truncated" binary sequence.

If $c(x)=\sum_{t\geq 1} c_t x^t$ and $k(x)=\sum_{t\geq 0} k_t x^t$ and are the two generating functions corresponding to the two sequences one can show $$ k(x)=\frac{1}{1+c(x)}=1+c(x)+c(x)^2+\cdots $$ where we consider formal power series without regard to convergence. Proceeding further and collecting the powers $x^t$ in that series eventually yields a formula for $k_t:$

Note that this closed formula for the generating function is not necessarily fully reduced since further cancellations modulo $2$ can take place.

Since not much more is known, this may be a good topic for a student to pursue.