# Stream ciphers based on LFSRs

As mentioned in the beginning of §6.2.1, linear feedback shift registers are widely used in keystream generators because they are well-suited for hardware implementation, produce sequences having large periods and good statistical properties, and are readily analyzed using algebraic techniques. Unfortunately, the output sequences of LFSRs are also easily predictable, as the following argument shows. Suppose that the output sequence s of an LFSR has linear complexity L. The connection polynomial C(D) of an LFSR of length L which generates s can be efficiently determined using the Berlekamp-Massey algorithm

• (Algorithm 6.30) from any (short) subsequence t of s having length at least n = 2L (cf. Fact 6.35). Having determined C(D), the LFSR (L, C(D)) can then be initialized with any substring of t having length L, and used to generate the remainder of the sequence s. An adversary may obtain the required subsequence t of s by mounting a known or chosen- plaintext attack (§1.13.1) on the stream cipher: if the adversary knows the plaintext subsequence mi, m2,... , m,i corresponding to a ciphertext sequence ci, сг,... , cn, the corresponding key stream bits are obtained as т*фс*, 1 < г < n.
• 6.44 Note (use ofLFSRs in keystream generators) Since a well-designed system should be secure against known-plaintext attacks, an LFSR should never be used by itself as a keystream generator. Nevertheless, LFSRs are desirable because of their very low implementation costs. Three general methodologies for destroying the linearity properties of LFSRs are discussed in this section:
• (i) using a nonlinear combining function on the outputs of several LFSRs (§6.3.1);
• (ii) using a nonlinear filtering function on the contents of a single LFSR (§6.3.2); and
• (iii) using the output of one (or more) LFSRs to control the clock of one (or more) other LFSRs (§6.3.3).

Desirable properties of LFSR-based keystream generators

For essentially all possible secret keys, the output sequence of an LFSR-based keystream generator should have the following properties:

• 1. large period;
• 2. large linear complexity; and
• 3. good statistical properties (e.g., as described in Fact 6.14).

It is emphasized that these properties are only necessary conditions for a keystream generator to be considered cryptographically secure. Since mathematical proofs of security of such generators are not known, such generators can only be deemed computationally secure (§1.13.3(iv)) after having withstood sufficient public scrutiny.

• 6.45 Note (connectionpolynomial) Since a desirable property of a keystream generator is that its output sequences have large periods, component LFSRs should always be chosen to be maximum-length LFSRs, i.e., the LFSRs should be of the form (L, C(D)) where C(D)1j2[D) is a primitive polynomial of degree L (see Definition 6.13 and Fact 6.12(ii)).
• 6.46 Note (known vs. secret connection polynomial) The LFSRs in an LFSR-based keystream generator may have known or secret connection polynomials. For known connections, the secret key generally consists of the initial contents of the component LFSRs. For secret connections, the secret key for the keystream generator generally consists of both the initial contents and the connections.

For LFSRs of length L with secret connections, the connection polynomials should be selected uniformly at random from the set of all primitive polynomials of degree L over Z2. Secret connections are generally recommended over known connections as the former are more resistant to certain attacks which use precomputation for analyzing the particular connection, and because the former are more amenable to statistical analysis. Secret connection LFSRs have the drawback of requiring extra circuitry to implement in hardware. However, because of the extra security possible with secret connections, this cost may sometimes be compensated for by choosing shorter LFSRs.

6.47 Note (sparse vs. dense connection polynomial) For implementation purposes, it is advantageous to choose an LFSR that is sparse; i.e., only a few of the coefficients of the connection polynomial are non-zero. Then only a small number of connections must be made between the stages of the LFSR in order to compute the feedback bit. For example, the connection polynomial might be chosen to be a primitive trinomial (cf. Table 4.8). However, in some LFSR-based keystream generators, special attacks can be mounted if sparse connection polynomials are used. Hence, it is generally recommended not to use sparse connection polynomials in LFSR-based keystream generators.