LFSR Keystream Generators and the Linearity That Must Be Broken

A linear feedback shift register is a chain of flip-flops with a feedback tap that XORs selected stages back into the input. It produces a bit stream with excellent statistical properties, it is cheap in both hardware and software, and it is completely unsuitable as a cipher on its own. The reason is not subtle: the output sequence satisfies a linear recurrence, and a linear recurrence can be solved from a short prefix.

The history of stream cipher design is largely the history of trying to keep the LFSR’s cheapness while removing its linearity, and most of the failures along the way came from combining linear components in ways that left the combination nearly linear.

The register and its recurrence

A register of $L$ stages, with taps at positions given by a polynomial $c(x)$ of degree $L$ over $\mathrm{GF}(2)$, produces the sequence $s_t$ satisfying

$$s_{t+L} = \sum_{i=0}^{L-1} c_i , s_{t+i}$$

The tap polynomial determines everything. If it is primitive over $\mathrm{GF}(2)$, the sequence has period $2^L - 1$ and passes the usual randomness tests: each nonzero $L$-bit window appears exactly once per period, the balance of ones and zeros is near even, and the autocorrelation is two-valued. For $L = 64$ the period is about $1.8 \times 10^{19}$ bits, which is longer than any plausible message.

Statistical quality is precisely the problem. A sequence with period $2^L - 1$ and good balance looks random to a battery of tests, and it is nevertheless determined by $L$ bits. The Berlekamp–Massey algorithm computes the shortest recurrence generating a given sequence in time quadratic in the sequence length, and it needs only $2L$ output bits to recover an $L$-stage register’s polynomial and state. For a 64-stage register that is 128 bits of known keystream. Any cipher whose keystream is a single LFSR output is broken by a known-plaintext attack of trivial cost.

This gives the central design quantity: linear complexity, the length of the shortest LFSR that reproduces the sequence. A secure keystream must have linear complexity close to half its length, so that Berlekamp–Massey on the available keystream yields nothing.

Combining registers

The obvious fix is to combine several LFSRs with a nonlinear function. Let $n$ registers of lengths $L_1, \dots, L_n$ feed a Boolean function $f$ of $n$ variables, and let the output be $f$ applied to the current output bit of each register. The resulting sequence has period dividing the product of the individual periods, and its linear complexity is bounded by

$$L \leq \sum_{i=1}^{n} \binom{n}{i} L_i$$

with the sum running over the terms of $f$‘s algebraic normal form. For $f$ of degree $d$, the bound is $\sum_{i=1}^{d} \binom{n}{i} L_i$. A high-degree function with many registers gives a large linear complexity, which is why early designs used functions of degree 2 or 3 over a handful of registers.

The bound is necessary, not sufficient. Meier and Staffelbach showed that combining registers with a low-weight function leaves a correlation between the output and individual register outputs, and that correlation supports a fast correlation attack: guess the state of one register, generate its output, check the correlation against the observed keystream, and keep the guess if the agreement rate exceeds chance. The attack’s cost is roughly $2^{L_i}$ per register guessed, so the shortest register dominates, and the attack is practical when the shortest register is short and the correlation is not tiny.

The same paper introduced the concept of a parity check attack: the correlation need not be direct. If the output function has a linear approximation with bias $\epsilon$, then the keystream agrees with a linear combination of register outputs at rate $1/2 + \epsilon$, and the combination can be attacked with a decoding algorithm. The lesson is that a Boolean combining function must have high algebraic degree, high nonlinearity — no linear approximation with large bias — and balanced output, and even then the correlation structure across many registers has to be checked.

Irregular clocking

An alternative to combining outputs is to let one register control the clocking of others. The A5/1 design used in GSM has three registers of lengths 19, 22, and 23, each with a clocking tap; at each step the majority of the three tap bits decides which registers advance. A register whose tap bit matches the majority advances, so two or three registers move per step. The output is the XOR of the three output bits.

Irregular clocking removes the direct algebraic relation between the keystream and any single register’s output, because the number of steps a register has taken is not known to the attacker. It also reduces the effective period and introduces its own weaknesses. Biham and Dunkelman’s analysis of A5/1 exploited the clocking rule: because two of the three registers always advance together, the relative clocking between pairs of registers is constrained, and a guess-and-determine attack can exploit that constraint. The design also has a short 64-bit key and a frame-dependent initialisation that leaks.

/* Majority-clocked step: the register whose clocking bit differs from
   the majority is held, the others advance. Output is the XOR of three
   output taps. This structure is what makes the state unguessable
   without also guessing the clocking history. */
static void a5_step(lfsr *r1, lfsr *r2, lfsr *r3, uint8_t *out)
{
    int m = (r1->bit(8) + r2->bit(10) + r3->bit(10)) >= 2;
    if (r1->bit(8) == m) r1->clock();
    if (r2->bit(10) == m) r2->clock();
    if (r3->bit(10) == m) r3->clock();
    *out = r1->bit(18) ^ r2->bit(21) ^ r3->bit(22);
}

The security argument for irregular clocking is informal: the attacker does not know how many times each register has advanced, so the linear recurrence is not directly observable. The attacks that broke A5/1 worked by enumerating enough of the state to make the clocking history consistent, and the cost was low enough to be practical because the registers are short.

Filtering and the algebraic counterattack

A third structure feeds one long register through a nonlinear filter function, taking the output from a subset of stages. The register is long, the filter has high degree, and the linear complexity is high. This is the structure of the shrinking generator and of several eSTREAM submissions.

Filtering exposes the cipher to algebraic attacks, which became prominent in the early 2000s. The idea is to find a low-degree function $g$ such that $g \cdot f = h$ where $h$ is also of low degree, or such that $g \cdot f$ vanishes on the output. Each output bit then yields a low-degree equation in the register’s state bits, and a linearisation step treats each monomial as an independent unknown. With enough keystream the system is solvable by linear algebra. Courtois and Meier formalised this and showed that the relevant quantity is the algebraic immunity of the filter function: the minimum degree of a nonzero $g$ such that $f \cdot g$ has low degree. A function with low algebraic immunity is vulnerable regardless of its linear complexity.

The countermeasure is to choose filter functions with maximal algebraic immunity, which for an $n$-variable function is about $n/2$. That requirement was not known to designers of earlier ciphers, and several candidates were broken by algebraic attacks after submission.

Why LFSR designs persist

Given the history, it is fair to ask why anyone still builds ciphers from shift registers. The answer is cost. An LFSR with a sparse tap polynomial costs one XOR per output bit, and a hardware implementation is a shift register and a handful of gates. On a constrained device where a block cipher’s S-boxes and round logic are too large, an LFSR-based stream cipher is the only design that fits. The eSTREAM portfolio’s hardware profile exists precisely to serve that niche.

The design discipline that emerged is narrow. A candidate must specify linear complexity bounds, algebraic immunity of its filter, resistance to correlation and fast correlation attacks, resistance to guess-and-determine attacks that enumerate partial state, and resistance to divide-and-conquer attacks that exploit the independence of registers. Each of these is a different analysis, and a cipher that survives all of them is the result of extensive search rather than a single insight. The cost of getting one wrong is the whole cipher: a single biased output bit is enough for a correlation attack, whereas a block cipher with one weak round still has fourteen others.

An alternative route to nonlinearity is to abandon the linear components altogether. ARX designs replace the register with modular addition, which is nonlinear in the carry and cheap on general-purpose processors, at the cost of losing the algebraic structure that makes an LFSR’s period and statistical properties provable. The two approaches sit at opposite ends of a spectrum: one gives provable statistical quality and fragile security, the other gives no statistical proof and a security argument built from trail search. Both families are cheap and both are hard to design.

For the block-cipher side, the corresponding question is how a fixed permutation is turned into a keystream, and that belongs to the modes literature rather than here. Within this cluster, the diffusion argument for byte-oriented ciphers in diffusion and branch numbers is the natural comparison, because it shows what a proof of resistance looks like when the structure permits one.

The keystream is not the cipher

A final distinction matters for anyone implementing one of these. A keystream generator produces bits; a stream cipher is the generator plus a nonce handling scheme plus a key setup. Reusing a nonce with the same key reproduces the keystream and reveals the XOR of the two plaintexts, and the failure is total rather than partial. Designs differ in how the nonce enters the state — some load it directly, some run a setup phase — and the setup phase is where related-key and slide-style weaknesses appear. The generator’s statistical properties say nothing about the setup’s soundness, and the two must be evaluated separately. The same split exists in block ciphers between the round function and the key schedule, and in both cases the weaker of the two determines the cipher’s security.