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.
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, 2021 at 8:32
-
$\begingroup$ Is the answer satisfactory to you as the poster of the question? $\endgroup$– kodluJul 13, 2021 at 8:03
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
