THE GARDEN

Linear Feedback Shift Register (LFSR)

Updated 13 Sep 2026

• •

  What it is

  • •

    a hardware-friendly building block for stream ciphers: a register of bit-cells where, each clock cycle, the register shifts left, the leftmost bit falls off, and a new bit — the XOR of a fixed subset of "tap" positions — is fed in on the right

• •

  Symbols and assumptions

  • •

    $S_t=(u_t,\ldots,u_{t+n-1})$ is the n-bit state before clock t. Bits are in $GF(2)$: addition is XOR and multiplication is AND. Tap indexes start at zero.

• •

  Math — step by step

  • •
    1. Compute the feedback bit as the XOR of the specified old-state cells. Shift left, discard cell 0, and append the feedback. Keep output-before-clock versus output-after-clock explicit.
  • •
    2. For taps $T$, $u_{t+n}=\bigoplus_{j\in T}u_{t+j}$. Every later cell is therefore a linear expression in the initial n bits.
  • •
    3. Raw linear output is predictable once its recurrence and enough state are known. A nonlinear output filter changes the attack: its visible sequence need not have linear complexity n. Analyze the filter as well as the register.
• •

  Worked example

  • •

    Toy n=3, taps $\{0,1\}$, state $(1,0,0)$. Feedback is $1\oplus0=1$, so the next state is $(0,0,1)$.

  • •

    The following states are $(0,1,0)$, $(1,0,1)$, $(0,1,1)$, $(1,1,1)$, $(1,1,0)$, and back to $(1,0,0)$. Reading cell 0 before each clock gives the period $1,0,0,1,0,1,1$.

  • •

    For LFSR Destroyer, replace n by 128 and taps by $\{0,1,2,7\}$: $u_{t+128}=u_t\oplus u_{t+1}\oplus u_{t+2}\oplus u_{t+7}$. Its visible bit is a nonlinear function of six cells, not simply cell 0.

• •

  Why it's used

  • •

    extremely cheap to implement in hardware (just shifts and XOR gates, very few transistors)

• •

  Used in

  • •

    DVD encryption (Content Scrambling System (CSS), 2 LFSRs), GSM's A5/1 and A5/2 (3 LFSRs), Bluetooth's E0 (4 LFSRs)

• •

  Security

  • •

    An unfiltered linear recurrence is predictable from sufficient observations. Security depends on the complete construction, including filters, combination, clocking and exposed data; using LFSRs alone does not establish that every design is broken.

• •

  Related

  • •

    Content Scrambling System (CSS)

  • •

    Stream Cipher

◌ Explore connections in Graph view