3
$\begingroup$

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.

$\endgroup$
7
  • $\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, 2019 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, 2019 at 8:30
  • $\begingroup$ @kelalaka Do you mean like Snow v cipher? $\endgroup$
    – hardyrama
    Aug 28, 2019 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, 2019 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$ Sep 2, 2019 at 22:13

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
2
  • $\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, 2019 at 11:39
  • $\begingroup$ @forest, please see my second answer $\endgroup$
    – kodlu
    Jun 1, 2023 at 14:10
2
$\begingroup$

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 $$ enter image description here

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:$

enter image description here 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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.