Also known as: LFSR, PRBS generator
A linear-feedback shift register (LFSR) is a shift register whose incoming bit is a linear (XOR) function of selected bits, called taps, producing a long, repeatable pseudo-random sequence from a small amount of state.1
How it works
An LFSR holds a few bits of state. On each clock the bits shift one position, the bit shifted out becomes the output, and a new input bit is computed by XORing the selected tap positions together. The choice of taps is described by a feedback polynomial; a “maximal-length” polynomial of n bits cycles through all 2ⁿ−1 non-zero states before repeating, giving a long pseudo-random binary sequence (PRBS).
- Cheap — a handful of flip-flops and XOR gates; common in hardware.
- Deterministic — the same seed and taps always reproduce the same keystream, so a receiver can regenerate it exactly.
- Linear — because the feedback is pure XOR, the sequence is predictable: observing a modest run of output lets an attacker solve for the taps and state, so an LFSR alone is not a secure stream cipher.
Relevance to SDR
LFSRs are everywhere in digital radio, but as scrambling rather than secrecy. Many trunked and digital-voice protocols scramble (whiten) their bit stream with a fixed LFSR sequence to remove long runs and DC bias; because the polynomial and seed are public, GopherTrunk simply regenerates the same sequence and XORs it back out — no key is involved. That is the opposite of a one-time pad, whose key is secret and never reused.
The linearity of an LFSR also makes it a natural first hypothesis when reverse-engineering an unknown bit transform. In the clean-room talker-alias analysis (issue #773), an LFSR-style update was tested against captured data and ruled out — the observed mapping was nonlinear, pointing instead at a fixed substitution table rather than a linear feedback sequence.
Sources
-
Linear-feedback shift register — Wikipedia, for taps, feedback polynomials, maximal-length sequences, and the linearity weakness. ↩