4
$\begingroup$

As the title suggests, I wonder what kinds of attacks there are in the LFSR filter generator. The most representative attack is the fast correlation attack and inversion attack. I wonder what other attacks are possible.

$\endgroup$
2
  • 2
    $\begingroup$ As far as I get it, the output of an "LFSR filter generator" for key $K\in\{0,1\}^n$ is $f(S_i)$ for incremental $i$, a public filter function $f:\{0,1\}^n\to\{0,1\}$, and a public polynomial $P(x)$ of degree $n$ with binary coefficients, with $S_0=K$ and $S_{i+1}=S_i\,x\bmod P(x)$. Vulnerabilities will depend on $n$, on $P$ and $f$. We might want $n$ to be large, $P$ to be primitive, and $f$ to be non-linear, for some definition of that. $\endgroup$
    – fgrieu
    Jul 2 at 8:32
  • $\begingroup$ Is the answer satisfactory to you as the poster of the question? $\endgroup$
    – kodlu
    Jul 13 at 8:03
2
$\begingroup$

At a minimum $P(x)$ must be primitive and $f:\{0,1\}^n \rightarrow \{0,1\}$ must be highly nonlinear and resilient of high order (correlation immune of high order plus balanced) are necessary conditions.

  • Nonlinearity (minimal Hamming distance of the truth table of the boolean function from affine functions), must be high for resisting linear/affine approximation attacks. This is computed via the fast Walsh-Hadamard transform.

There is a more recent class of attacks which are resisted by functions $f$ with high algebraic immunity denoted $AI(f)$. Denote the state update mapping corresponding to the polynomial $P$ by $L:\{0,1\}^n\rightarrow \{0,1\}^n$ and note that the output bit $s_t$ is given by its $t-$fold composition where $x_0$ is the initial state of the LFSR, usually chosen randomly by using the secret key. $$ s_t=L(L(\cdots L(x_0))):=L^t(x_0). $$ The keystream $(s_t)$ is vulnerable to attacks if there are relations of low degree between the keystream bits and bits of the state. These relations can exist even when the algebraic degree of $f$ is high. Such relations correspond to low degree multiples of $f$, i.e., $$ g(x)f(x)=h(x) $$ where we can find a polynomial $g(x)$ such that $h(x)$ has low degree. It turns out this is equivalent to the existence of a low degree annihilator of $f$ or $1+f$ and $f$ is said to have a high algebraic immunity if no low degree annihilator of $f$ or $1+f$ exists.

See Anne Canteaut's paper for details and some references here.

$\endgroup$

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.