# What vulnerabilities does the LFSR filter generator have?

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.

• 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.
– fgrieu
Jul 2 at 8:32
• Is the answer satisfactory to you as the poster of the question? Jul 13 at 8:03

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.
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.