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?

• 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 – poncho Jan 25 '17 at 17:27
• Wow, they're even more terrible than I could reasonably imagine. ;) – Elias Jan 25 '17 at 17:28
• "Terrible" isn't very objective. They are certainly unfit for some uses, but they have properties that are desirable for others. – bmm6o Jan 25 '17 at 21:57
• @Elias, do you have any comments on the answer below? – kodlu Jan 27 '17 at 4:39

1 Answer

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.

• 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. – Elias Jan 27 '17 at 8:49