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

  • 2
    $\begingroup$ Actually, the Berlekamp-Massey algorithm assumes you don't know the feed back terms. Yes, if you do, it's trivial; if you don't, Berlekamp-Massey makes it trivial $\endgroup$ – poncho Jan 25 '17 at 17:27
  • $\begingroup$ Wow, they're even more terrible than I could reasonably imagine. ;) $\endgroup$ – Elias Jan 25 '17 at 17:28
  • 1
    $\begingroup$ "Terrible" isn't very objective. They are certainly unfit for some uses, but they have properties that are desirable for others. $\endgroup$ – bmm6o Jan 25 '17 at 21:57
  • $\begingroup$ @Elias, do you have any comments on the answer below? $\endgroup$ – kodlu Jan 27 '17 at 4:39

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.

| improve this answer | |
  • $\begingroup$ 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. $\endgroup$ – Elias Jan 27 '17 at 8:49

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.