RSA Laboratories What is a Linear Feedback Shift Register?

A Linear Feedback Shift Register (LFSR) is a mechanism for generating a sequence of binary bits. The register (see Figure 2.6) consists of a series of cells that are set by an initialization vector that is, most often, the secret key. The behavior of the register is regulated by a counter (in hardware this counter is often referred to as a ``clock''). At each instant, the contents of the cells of the register are shifted right by one position, and the XOR of a subset of the cell contents is placed in the leftmost cell. One bit of output is usually derived during this update procedure.

Figure 2.6: Linear Feedback Shift Register (click for a larger image)

LFSRs are fast and easy to implement in both hardware and software. With a judicious choice of feedback taps (the particular bits that are used; in Figure 2.6, the first and fifth bits are "tapped") the sequences that are generated can have a good statistical appearance. However, the sequences generated by a single LFSR are not secure because a powerful mathematical framework has been developed over the years which allows for their straightforward analysis. However, LFSRs are useful as building blocks in more secure systems.

A shift register cascade is a set of LFSRs connected together in such a way that the behavior of one particular LFSR depends on the behavior of the previous LFSRs in the cascade. This dependent behavior is usually achieved by using one LFSR to control the counter of the following LFSR. For instance, one register might be advanced by one step if the preceding register output is 1 and advanced by two steps otherwise. Many different configurations are possible and certain parameter choices appear to offer very good security. For more detail, see an excellent survey article by Gollman and Chambers [GC89].

The shrinking generator was developed by Coppersmith, Krawczyk, and Mansour [CKM94]. It is a stream cipher based on the simple interaction between the outputs from two LFSRs. The bits of one output are used to determine whether the corresponding bits of the second output will be used as part of the overall keystream. The shrinking generator is simple and scaleable, and has good security properties. One drawback of the shrinking generator is that the output rate of the keystream will not be constant unless precautions are taken. A variant of the shrinking generator is the self-shrinking generator [MS95b], where instead of using one output from one LFSR to "shrink" the output of another (as in the shrinking generator), the output of a single LFSR is used to extract bits from the same output. There are as yet no results on the cryptanalysis of either technique.

Top of the page