Cryptanalysis of Linear Feedback Shift Registers

Question

It is well known that simple m-sequence linear feedback shift registers have a linear algebraic structure and therefore the generator seed can easily be deduced using the Berlekamp-Massey algorithm. Are there any other algorithms that can that can be used to "break" LFSR's and if so how does the algebra of said algorithm(s) compare to the Berlekamp-Massey algebra?

Answer 1

The Berlekamp-Massey algorithm is an iterative algorithm that solves the following problem.

Given a sequence $s_0, s_1, s_2, \ldots$ of elements of a field, find the shortest linear feedback shift register (LFSR) that generates this sequence.

Here, LFSR is a linear array of $n$ elements with initial value $$(s_0, \quad s_1,\quad \ldots, \quad s_{n-2}, \quad s_{n-1})$$ and successive values $$(s_0, \quad s_1, \quad \ldots, \quad s_{n-2}, \quad s_{n-1})\\ \downarrow\\ (s_1, \quad s_2, \quad \ldots, \quad s_{n-1}, \quad s_n)\\ \downarrow\\ (s_2, \quad s_3, \quad \ldots, \quad s_n, \quad \quad s_{n+1})\\ \downarrow\\ \cdots \quad \cdots$$ where the array contents shift leftwards at each step (clock cycle) so that the field elements falling off the left end (the LFSR output) are the given sequence, while the field elements shown as entering the LFSR on the right* are being computed as a linear combination of the LFSR contents at the previous step. In particular, for $i \geq 0$, the state transition can be expressed as $$\biggr(s_i, \quad s_{i+1}, \ldots, \quad s_{i+n-2}, \quad s_{i+n-1}\biggr)\\ \downarrow\\ \biggr(s_{i+1}, \quad s_{i+2}, \ldots, \quad s_{i+n-1}, \quad \sum_{j=0}^{n-1}c_{n-j} s_{i+j}\biggr),$$ that is, the linear combination $c_ns_i + c_{n-1}s_{i+1} + \cdots + c_1s_{i+n-1}$ of previous LFSR contents is being fed back into the right end of the LFSR as $s_{n+i}$ (and hence the name linear feedback shift register).

As mentioned previously, the Berlekamp-Massey algorithm finds the shortest LFSR that generates the given sequence meaning it figures out the values of the $c_i$ elements. The iterative process consists of finding the shortest LFSR that generates the first $t$ elements $s_0, s_1, \ldots s_{t-1}$ and checking if the LFSR finds $s_t$ correctly. If so, $s_{t+1}$ is checked, while if not, the $c_i$'s are updated so that the revised LFSR generates $s_t$. If the sequence was indeed created by a $n$-stage LFSR as described above, the Berlekamp-Massey algorithm finds all $n$ coefficients $c_i$ after examining $s_0, s_1, \ldots, s_{2n-1}$. From this point onwards, the Berlekamp-Massey algorithm can continue checking the rest of the sequence (if so desired) but does not need to update the $c_i$'s because each check of the next symbol simply reports back that everything is OK.

---

Let $S(z) = \sum_i s_i z^i$ and $C(z) = -1 + \sum_{i=1}^n c_iz^i$ denote generating functions of the given sequence and LFSR feedback coefficients. Then, the equation $$s_{i+n} = c_ns_i + c_{n-1}s_{i+1} + \cdots + c_1s_{i+n-1}$$ is equivalent to saying that the coefficients of $z^{i+n}$ in the product $C(z)S(z)$ is $0$ for all $i \geq 0$. But the coefficients of $z^0, z^1, \ldots, z^{n-1}$ are not zero. When only the first $2n$ symbols $s_0, s_1, s_{2n-1}$ have been looked at, what the Berlekamp-Massey algorithm has solved (thus far) is the congruence $$C(z)S(z) \equiv D(z) \bmod z^{2n}$$ where $\deg D(z) < n$. Indeed, Berlekamp's formulation of what is now called the Berlekamp-Massey algorithm envisioned solving congruences $$C^{(m)}(z)S(z) \equiv D^{(m)}(z) \bmod z^{m}$$ (where $\deg D^{(m)} \leq m/2$) iteratively for $m=1, 2, \ldots, $ until arriving at the desired solution at $m = 2n$.

---

Finally and at long last, the extended Euclidean algorithm for polynomial greatest common divisors can be used to solve the congruence $$C(z)S(z) \equiv D(z) \bmod z^{2n}.$$ Define $\hat{S}(z) = s_0 + s_1z + \cdots +s_{2n-1}z^{2n-1}$ and start the extended Euclidean algorithm to find the gcd of $z^{2n}$ and $\hat{S}(z)$. The extended Euclidean algorithm begins with $r_0(z) = z^{2n}, r_1(z) = \hat{S}(z)$ and finds the sequence of remainder polynomials $r_2(z), r_3(z), \ldots$ etc where $r_i(z)$ is the remainder when $r_{i-2}(z)$ is divided by $r_{i-1}(z)$. It also expresses each $r_i(z)$ as $$r_i(z) = \alpha_i(z)r_0(z) + \beta_i(z)r_1(z)$$ where polynomials $\alpha_i(z)$ and $\beta_i(z)$ are computed iteratively. Consider the smallest value of $i$ for which $\deg r_i(z) < n$. We have $$r_i(z) = \alpha_i(z)z^{2n} + \beta_i(z)\hat{S}(z)$$ and so $$\beta_i(z)\hat{S}(z) \equiv r_i(z) \bmod z^{2n}.$$

Notice that the Euclidean algorithm processes the the $s_i$ in descending order of subscripts whereas the Berlekamp-Massey algorithm processes the $s_i$ in ascending order of subscripts. The Euclidean algorithm can be reformulated to process the $s_i$ in increasing order of subscripts in which case it is virtually indistinguishable from the Berlekamp-Massey algorithm. Either way, the algorithms have very similar computational complexity.

---

For details on the extended Euclidean algorithm and its connections to the Berlekamp-Massey algorithm, see R. E. Blahut's Algebraic Codes for Data Transmission, Cambridge Press 2003.

Answer 2

Berlekamp-Massey can be used if you do not know the feedback polynomial and you do not know the initial fill.

If you do know the feedback polynomial but do not know the initial fill, you can use other simpler methods. For instance, if you just look at any $n$ consecutive bits of output (where the register is $n$ bits wide), then you immediately learn the state of the register at a single point of time. You can then run the LFSR forward or backward to learn its state at all other times (e.g., to learn the initial seed) or to see all other outputs (learn the entire sequence of outputs from the LFSR).

If you have a "noisy" observation of LFSR outputs and want to reconstruct the LFSR sequence, you can use low-weight syndrome decoding methods. By "noisy", I mean that there are some bit errors in your observations. In other words, you don't get to view the LFSR output directly: it is first filtered through a binary symmetric channel (BSC), and you only get to see the output of that channel. More precisely, instead of observing the LFSR output $Y_1,Y_2,\dots$, you observe $Z_1,Z_2,\dots$ where $Z_i = Y_i \oplus E_i$ and each $E_i$ is iid Bernoulli($p$) (i.e., $\Pr[E_i=1]=p$, $\Pr[E_i=0]=1-p$) for some $p<1/2$. There are known techniques for reconstructing the LFSR sequence, given noisy observations of it -- but these techniques have higher computational complexity.

When you ask for other methods, precisely what problem are you trying to solve? The method to use will depend upon what problem you are trying to solve. It is hard to answer this question without knowing exactly what problem you have or what the application is.