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.

  • $\begingroup$ 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. $\endgroup$ – kelalaka Aug 28 '19 at 8:27
  • $\begingroup$ @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). $\endgroup$ – forest Aug 28 '19 at 8:30
  • $\begingroup$ @kelalaka Do you mean like Snow v cipher? $\endgroup$ – hardyrama Aug 28 '19 at 8:32
  • $\begingroup$ @hardyrama no. Use each of the inner states of A as the selector of taps of B. $\endgroup$ – kelalaka Aug 28 '19 at 8:37
  • $\begingroup$ 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. $\endgroup$ – Henno Brandsma Sep 2 '19 at 22:13

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.

  • $\begingroup$ I look forward to hearing the gist of the unpublished manuscript. It would also be interesting to learn more about why it's difficult to control the properties of such a generator. I know that, for key-dependent S-boxes in traditional SPN ciphers, there's a tradeoff between a random S-box resulting in more confusion, and having to forgo constructing an S-box with well-researched properties. I always assumed that an LFSR polynomial had much less impact on the end security, with the sole exception of determining the cycle length. $\endgroup$ – forest Aug 29 '19 at 11:39

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.