Linear Feedback Shift Registers

A linear feedback shift register (LFSR) builds a keystream from a register of $n$ bits $s_0, s_1, \ldots, s_{n-1}$, where each new bit is the XOR of a fixed subset of the current bits.

• $c_1, \ldots, c_n \in \{0, 1\}$: the feedback taps, fixed for a given LFSR.
• $s_0, \ldots, s_{n-1}$: the initial state, acting as the secret key or seed.

Each step outputs 1 bit, usually $s_{i-n}$, then shifts the register and inserts the new feedback bit.

Connection Polynomial

The taps are written as a connection polynomial over $\mathrm{GF}(2)$, also called the feedback polynomial.

Each term $c_k x^k$ marks whether the tap $k$ steps back feeds into the recurrence, so $p(x)$ is a complete description of the LFSR’s wiring, independent of the initial state.

The output sequence has period $2^n - 1$, the maximum possible for an $n$-bit register, iff $p(x)$ is a primitive polynomial over $\mathrm{GF}(2)$.

Characteristic Polynomial

The recurrence itself corresponds to a characteristic polynomial, related to the connection polynomial by $x^n$ reversal.

$p^*(x)$ is primitive over $\mathrm{GF}(2)$ iff $p(x)$ is, so either polynomial can be used to check for maximal period. The characteristic polynomial is the one whose roots in the extension field $\mathrm{GF}(2^n)$ generate the output sequence, each output bit expressible as a trace function of a root raised to successive powers.

Combining LFSRs

An LFSR alone fails the unpredictability requirement of a secure keystream generator, since its recurrence is linear. Practical generators instead combine several LFSRs of different lengths and connection polynomials through a nonlinear Boolean function $f$.

• $s_i^{(j)}$: the output bit of the $j$-th LFSR at step $i$.
• $f$: a fixed nonlinear function of the $m$ component outputs.

For example, the Geffe generator combines 3 LFSRs through $f(x_1, x_2, x_3) = x_1 x_2 \oplus (1 \oplus x_1) x_3$, using $x_1$ to select between $x_2$ and $x_3$.

Security

A combining function $f$ must satisfy several properties for the resulting keystream to resist analysis.

• Balance
  $f$ outputs 0 and 1 equally often across all input combinations, so the keystream carries no statistical bias.
• High nonlinear order
  $f$ cannot be approximated by a linear or affine function of its inputs, since a close linear approximation reduces the combiner to a single large LFSR.
• Correlation immunity
  $k_i$ is statistically independent of each individual $s_i^{(j)}$, so no component LFSR’s output correlates with the combiner’s output.

A higher correlation immunity order generally forces a lower achievable nonlinear order, so the 2 properties trade off against each other rather than maximising independently. The Geffe generator above illustrates the failure mode: despite being nonlinear and balanced, its output agrees with $x_2$ on $75\%$ of inputs and with $x_3$ on $75\%$ of inputs, since $x_1$ only selects which of the two it copies.

Attacking

Berlekamp-Massey Algorithm

Targets a single LFSR directly, exploiting the linearity of its recurrence.

• $2n$ consecutive output bits give $n$ linear equations in the $n$ unknown taps $c_1, \ldots, c_n$.
• Solving this system (the Berlekamp-Massey algorithm does so in $O(n^2)$) recovers every tap and the state at that point.
• The attacker then computes every following output bit from the recurrence.

Correlation Attack

Targets a combined generator whose combining function $f$ correlates with 1 of its component LFSRs, as in the Geffe example above.

• The attacker guesses the connection polynomial of the correlated LFSR (public in most designs) and searches over its $2^n - 1$ possible initial states.
• Each candidate state produces a candidate output sequence, compared against the keystream bit by bit.
• The candidate whose sequence agrees with the keystream noticeably more than $50\%$ of the time is accepted as the recovered state.

This reduces recovering an $m$-LFSR generator’s full state from 1 search of size $2^{\sum n_j} - 1$ to $m$ separate searches of size $2^{n_j} - 1$ each, so correlation immunity directly defends against it.

Example

Take $n = 4$ with connection polynomial $p(x) = 1 + x + x^4$, so $c_1 = 1, c_2 = 0, c_3 = 0, c_4 = 1$, and initial state $s_0 s_1 s_2 s_3 = 1000$.

Continuing the recurrence for 15 steps cycles through every nonzero state of the register once before repeating, giving the maximal period $2^4 - 1 = 15$, confirming $p(x) = 1 + x + x^4$ is primitive over $\mathrm{GF}(2)$.