A linear feedback shift register (LFSR) is a bit register that shifts its state one position per step, emits the ejected bit, and feeds a new bit back into the register. The feedback bit is the XOR of selected state positions, called taps. This makes the mechanism circular rather than a normal shift register that discards old bits. section 4.2
Figure 4.7 A linear feedback shift register showing execution of the first few steps
The execution trace makes the essential cycle visible: output one end bit, shift the remaining state, XOR tapped bits, and insert the result. section 4.2
Length is the number of state bits. An LFSR eventually repeats its output; for length L, its maximum period is 2^L − 1. Fibonacci LFSRs calculate one feedback bit from the tapped state bits, while Galois LFSRs apply XOR at tap locations as the output bit is ejected. section 4.2
A practical Fibonacci implementation keeps state and taps, then generates each output bit in this order:
- Save the current rightmost state bit as output. section 4.2.1
- XOR every state bit whose corresponding tap is active to calculate the incoming bit. section 4.2.1
- Shift all state positions right and place the calculated bit at the leftmost position. section 4.2.1
- Call bit generation eight times to assemble a byte of keystream, then XOR that byte with plaintext. section 4.2.1
Using an LFSR as a stream cipher
The initial state acts as the encryption key, while generated output supplies the keystream for XOR encryption. An implementation can discard the first number of bits equal to the register length so the plaintext is not XORed directly with initial key bits. That separation does not make a single LFSR secure: its linear output remains reversible. section 4.2.1 section 4.4
Known plaintext exposes keystream bits because ciphertext XOR plaintext equals the keystream. Given enough observed bits and a known LFSR length, place consecutive observations in a Boolean state matrix, invert it, and solve for the tap coefficients. A cloned register can then reproduce later keystream bits and decrypt ciphertext whose plaintext was not known. section 4.2.2 section 10.1.2
Recovering a timestamp message
A known prefix, "ATTACK AT ", is XORed with its ciphertext to recover keystream bits. Candidate register lengths are tried until recovery produces a cloned LFSR whose decryption parses as a timestamp; the successful clone reveals the remaining message. section 4.2.2
Do not rely on a single LFSR to protect stream-cipher traffic. LFSRs remain attractive because they are simple, fast, and hardware-efficient, but stream-cipher designs combine them in more elaborate, nonlinear ways to raise linear complexity and resist correlation-based recovery. section 4.2 section 10.1.2
