Linear Feedback Shift Registers analysis

Question

Cryptanalysis of Linear Feedback Shift Registers. From this site I found that lfsr could be break by Berlekamp-Massey algorithm. What is the specific progress of this algorithm? And if there is any other way to do it

Answer 1

First of all, LFSR's are not secure when they are used alone. They have good statistical properties and one can calculate their period given the feedback polynomial. The LFSR is maximal-length if and only if the corresponding feedback polynomial is primitive. In this case, it visit all states except the all-zero state if it started with a non-zero sate.

To find the taps and internal of an LFSR, you can go in two ways;

1. Give variable names for the internal and tap point then you can generate a linear equation of the system then solve it with Gaussian elimination.
2. Use the Berlekamp-Massey algorithm, this is faster than Gaussian elimination and only requires the double of the LFSR's size. i.e. an LFSR with length $L$ can be constructed with $2L$ sequential output regardless of the number of the taps. It is an interactive algorithm that updates the taps according to a currently given output bit.

Actually, Berlakamp-Massey algorithm produces the shortest LFSR with taps that produce the given sequence. The algorithm may reach the result before consuming all $2L$ bits, however, an attacker needs to use all $2L$ bits to be sure. If the determining polynomial of the LFSR is no primitive, then there can be more than one LFSR that produces the sequence with different lengths. Berlakamp-Massey algorithm, however, always will find out the shortest LFSR.

---

The LFSR based archaic stream ciphers are;

• Combining LFSRs with non-linear combiner broken by the novel attack of Siegenthaler
• Irregular clocking as Alternating step generator
• Shrinking Generator is broken if the taps are known; Gil et. al, 2009 New Attack Strategy for the Shrinking Generator if not known then the attacks are not better than brute-force.
• Filtering the LFSR

• Self Shrinking Generator (SSG). Attack on SSG;

  • 2001 Zenner et. al; Improved Cryptanalysis of the Self-Shrinking Generator require less than 70% of the brute-force, for example for 120-bit the attack requires $\mathcal{O}(2^{83})$-time.

  • 2011 Amparo and Sabater; Cryptanalytic Attack on the Self-Shrinking Sequence Generator requires $\mathcal{O}(2^{L/2})$ for time complexity, $\mathcal{O}(2^{L/4})$ for the amount of intercepted sequence and $\mathcal{O}(L^2)$. Note This work may not be correct, see comments

  • 2006 Zhang and Fang; New Guess-and-Determine Attack on the Self-Shrinking Generator. Depending on the $L$ the length of the LFSR their attacks has;

    • $L \geq 100$ then $\mathcal{O}(2^{0.556L})$-time complexity, $\mathcal{O}(2^L)$-memory complexcity, and $\mathcal{O}(2^{0.161L})$-bit keystream
    • $L < 100$ then $\mathcal{O}(2^{0.571L})$-time complexity, $\mathcal{O}(2^L)$-memory complexcity, and $\mathcal{O}(2^{0.184L})$-bit keystream

And all the above is broken, at least, theoretically.

Also, some well-knowns due to GSM and Bluetooth.

• A5/1 and A5/2 used in GSM phones, E0 used in Bluetooth. They are broken, see the links. According to this source NSA can break A5/1.