Lecture 4: Stream Ciphers and Linear Feedback Shift Registers by Christof Paar

Summary

The lecture introduces linear feedback shift registers (LFSRs) as a basic hardware building block for stream ciphers. LFSRs are compact and can generate long sequences with a good statistical appearance, but a single LFSR is not secure for cryptographic use because its linear structure makes it vulnerable to attack.

1. Stream ciphers and keystreams

• A stream cipher generates a sequence of bits called a keystream and combines it with plaintext, typically using XOR.
• A one-time pad uses truly random key bits that are as long as the message. It is provably secure, but the key-length requirement makes it impractical for most real-world uses.
• The lecture introduces practical stream-cipher building blocks and explains why they should not necessarily be used alone.

2. Flip-flops and shift registers

• A flip-flop stores one bit and updates its stored value when it receives a clock pulse.
• Connecting flip-flops in sequence forms a shift register. On each clock pulse, the stored bits shift along and a bit is output.
• A plain shift register only outputs its initial contents and then runs out of meaningful bits. To keep generating bits, it needs feedback that supplies a new input bit on each clock.

3. How an LFSR works

• An LFSR adds feedback to a shift register. In the example, the new input bit is calculated by XORing selected register bits.
• The register’s contents form its state. A nonzero initial state and a chosen feedback rule determine the entire output sequence.
• The three-bit example uses feedback from two stages and has a cycle of length seven. The all-zero state is excluded: with three bits, there are eight possible states, but the nonzero states make up the seven-state maximum-length cycle.
• In general, a register with (m) flip-flops has at most (2^m - 1) states in a nonzero cycle. Once a state repeats, the deterministic process repeats from that point onward.

4. General LFSRs and feedback choices

An (m)-stage LFSR is specified by:

• The number (m) of flip-flops.
• The feedback choices, represented by binary coefficients (p_j).

A coefficient of 1 means that the corresponding register bit contributes to the feedback XOR; a coefficient of 0 means it does not. The sequence can be described by a recurrence such as:

[ s_{i+m} = \sum_{j=0}^{m-1} p_j s_{i+j} \pmod 2. ]

Different feedback choices produce different sequences and periods. Adding more feedback taps does not automatically improve the period or security.

5. Polynomials and maximum-length sequences

• LFSR feedback configurations are commonly written as polynomials, with their coefficients corresponding to the feedback choices.
• Certain feedback polynomials, called primitive polynomials, produce maximum-length sequences of (2^m - 1) bits for a nonzero initial state.
• Primitive-polynomial tables are commonly used to select suitable feedback configurations.
• LFSRs are attractive in hardware because a relatively small register can generate an extremely long sequence. They can also have good statistical properties, making their output resemble random bits in many basic tests.

6. Why a single LFSR is insecure

Good statistical appearance is not the same as cryptographic security. A single LFSR is linear, which makes its output predictable once enough information is known.

The lecture outlines a known-plaintext attack:

1. The attacker obtains ciphertext and knows an initial portion of the plaintext—for example, predictable file headers.
2. XORing the known plaintext with the ciphertext reveals the corresponding keystream bits.
3. Given the LFSR’s degree (m), the attacker uses the recurrence to form linear equations in the unknown feedback coefficients.
4. The equations can be solved using Gaussian elimination or related linear-algebra methods.
5. With the feedback configuration and initial state recovered, the attacker can generate the remaining keystream and XOR it with the ciphertext to recover the rest of the plaintext.

The lecture describes the attack as requiring a sufficiently long known output segment—stated in the subtitles as at least (2^m) output bits—and notes that an unknown register degree can be guessed and tested.

7. Combining LFSRs

• The lecture uses A5/1 in GSM as an example of a stream cipher built from three LFSRs.
• Its point is that weak components may be used as building blocks in a more complex design: combining several LFSRs and controlling their synchronization irregularly can make the system harder to attack than a single LFSR.
• The takeaway is not to use a single LFSR as a cryptographic stream cipher, even if its sequence is long and statistically convincing.

Speakers and sources featured

• Christof Paar — lecturer and primary speaker.
• Unidentified students and audience members — ask questions and provide brief answers during the lecture.
• Lecture notes and the course textbook — referenced as places to find details and tables of primitive polynomials.
• Roberto Avanzi — mentioned as having calculated a list of primitive polynomials for the textbook.