Cryptography
lfsr
Updated Fri, 10 Jun 2022 14:38:22 GMT

Why is the state of an LFSR not output?


According to Wikipedia LFSRs are used as PRGs but due to their linearity they are easy to cryptanalyze. Also, using Berlekamp-Massey consecutive output bits allow reconstruction of the internal LFSR state (I think the rule was something like $2n$ bits for state size $n$).

Now my question is a much more profane one. Given the following diagram for how an LFSR works doesn't it simply output its state and, therefore become trivially predictable? enter image description here




Solution

LFSRs are very useful as building blocks of ciphers, with some nonlinearity introduced. For example Trivium is a very strong and fast cipher, which includes a little amount of quadratic nonlinearity in 3 coupled LFSRs.

An example of bad use of LFSRs--and by no means the only one--is the A5 series of ciphers, of GSM fame, where majority clocking does not include enough nonlinearity/unpredictability.





Comments (1)

  • +0 – Well, the feedback function of Trivium is not really linear so it's a little odd. I agree that shift registers can be interesting building blocks as long as sufficient nonlinearity is introduced. — Jan 27, 2017 at 08:49