1
$\begingroup$

Let's suppose that there is a filter generator which based on $n$-size LFSR.

Denote a feedback polynomial as $g(x_1, x_2, \dots, x_n)$ and nonlinear filter function as $f(x_1, x_2, \dots, x_n)$.

Let $a = a_1, a_2, \dots, a_k$ be filter generator output sequence.

Attacker knows $f$ and $a$.

  1. What are boundaries for $k$ to recover $g(x_1, x_2, \dots, x_n)$?
  2. How to recover $g(x_1, x_2, \dots, x_n)$?
Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ Need more information. There are a number of nonlinear modifications to LFSR(s) with nonlinear filters or combination generators. $\endgroup$
    – kodlu
    Commented Feb 22, 2023 at 6:04
  • $\begingroup$ Thanks you @kodlu for the answer and the description of the architectures of the generators. And, I apologize for the inaccurate wording, since I meant a non-linear filter generator. I'll add more info to the first post. $\endgroup$
    – Grigoriy
    Commented Feb 23, 2023 at 5:14
  • $\begingroup$ Define it more precisely since usually what's in the answer is what's called filter generator. Edit your question with math specification. $\endgroup$
    – kodlu
    Commented Feb 23, 2023 at 5:43

1 Answer 1

Reset to default
1
$\begingroup$

For clarification, the linear complexity of a possibly nonlinear sequence is $L,$ then $2L$ bits are sufficient to determine the LFSR that will generate it, via the Berlekamp Massey algorithm. The list below examines some common types of nonlinear sequence generators.

Filter generator: (supply more details in question please)

The feedback function is linear (so an LFSR) but output is a nonlinear function applied to certain taps of the LFSR. There is a classical upper bound by Key, a lower bound due to Rueppel (Analysis and Design of Stream Ciphers book), as well as more recent results on the linear complexity of the output. The details can be quite technical to summarize, however.

Combination Generator:

Let there be $k$ LFSRs with pairwise relatively prime lengths $L_i,$ for $i=1,\ldots,k$ and feedback connections corresponding to primitive polynomials of degree $L_i.$ Then combine the outputs of these LFSRs, by means of a Boolean function $$ f:\{0,1\}^k\rightarrow \{0,1\} $$ with nonlinearity $r.$ The nonlinearity of the function $f(x_1,x_2,x_3)$ is the highest degree of a monomial in its algebraic normal form. See my answer to this question for more on how to determine the nonlinearity.

Then, the linear complexity of the output sequence resulting from this combination generator is given by $f(L_1,L_2,L_3)$ where the function is evaluated over the integers. See the answer to this question for a specific example.

NLFSR:

The period and linear complexity of feedback registers with nonlinear boolean functions as feedback functions is unsolved in general but there are some partial results. There is a chapter "Nonlinear shift registers – A survey and challenges" by Tor Helleseth, in the book Algebraic Curves and Finite Fields, De Gruyter, eds Niederreiter et al. You can find a copy online if you search, but original is paywalled. Some of the methods there are closely related to deBruijn cycles.

Specific Designs:

There are some results on linear complexity of outputs of specific designs such as Trivium, Grain, Shrinking Generator (nonlinearity introduced by an algorithmic shrinking operation), Wikipedia is a good place to start.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Thanks. I saw Key's result about filter generator in Algebraic Shift Register Sequences book by Goresky and Clapper. But I think formally it is another problem. $\endgroup$
    – Grigoriy
    Commented Feb 23, 2023 at 5:27

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.