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


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;

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.
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – SEJPM Jan 30 '20 at 14:38

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.