LFSR State Recovery — when the keystream itself hands you the seed

A Linear Feedback Shift Register's output is a linear function of its initial state and its tap coefficients, so a handful of observed keystream bits, solved as a system over GF(2), hands you the whole register — present and future.

The signal that betrays it

- A stream-cipher challenge whose keystream comes from a single LFSR, or from a known/guessable tap polynomial. - You already have a stretch of keystream in hand — most often surfaced via Stream-Cipher Keystream Reuse — the umbrella break behind every reused-keystream challenge (a reused keystream XORed out between two ciphertexts) or via a known-plaintext XOR. - Concrete tell in the update logic: "shift the register, feed back the XOR of a fixed subset of bit positions (the taps)". If it's maximal-length, the sequence period is 2ⁿ−1 for an n-bit register — seeing that exact period number surface in challenge code, comments, or docs (e.g. 2^32-1, 2^61-1) is itself the giveaway that you're looking at an LFSR. - If instead several LFSRs feed into a *nonlinear* Boolean combining function, that's a related but distinct signal — see "What does NOT work" below; don't treat it as the same problem.

Case A — taps known, state unknown (n-bit register)

- Collect n consecutive output bits. - The state-to-output map is linear, so solve it with Linear Algebra over GF(2) — solving bit-level unknowns as a linear system mod 2. - In practice the output stream is often literally the state bits shifting out one at a time — the first n observed bits *are* the seed, no linear algebra required, just read it off directly.

Case B — taps unknown too

- With 2n consecutive bits, set up the equations s_{i+n} = ⊕ⱼ cⱼ · s_{i+j}, which are linear in the unknown tap coefficients cⱼ. Solve as a GF(2) linear system, or run Berlekamp-Massey Algorithm — recover the minimal LFSR from raw keystream directly on the bitstream — it recovers the minimal feedback polynomial (and implicitly the state) from exactly 2n bits in one pass, and is the faster, standard route once taps aren't given. Public cross-reference: Berlekamp–Massey reconstructing the shortest LFSR that generates a sequence from 2n consecutive terms is the textbook result, not an ad hoc trick. - Field-tested reference stepper, used to validate a recovered state/tap pair by regenerating the stream and comparing: ``python def lfsr_step(state, taps): # state, taps: bit lists (LSB-first) fb = 0 for i, t in enumerate(taps): if t: fb ^= state[i] return [fb] + state[:-1], state[-1] # new_state, output_bit `` - Recovering plaintext: once state and taps are known, regenerate the full keystream forward from the seed and XOR it against the ciphertext.

What does NOT work

- Setting up a plain GF(2) linear system directly on the *combined* output of a nonlinear combiner/filter generator (multiple LFSRs mixed through a nonlinear Boolean function). The output is no longer linear in the constituent states, so the Case A/B approach above fails outright — it's not that it's slower, the equations are simply wrong. - For that case, the field-tested next step is a correlation attack: a divide-and-conquer technique that recovers each constituent LFSR's initial state separately by exploiting the statistical correlation between that LFSR's own sequence and the nonlinearly-combined output, rather than solving for everything at once. This is a genuinely different (and heavier) attack family — public cross-reference: the statistical weakness it exploits is exactly what Siegenthaler's correlation-immunity criterion (1984, "Correlation-Immunity of Nonlinear Combining Functions") was designed to defend *against* — Siegenthaler is the source of the defensive property, not the attack itself — and the attack was later sped up into "fast correlation attacks" by Meier and Staffelbach, confirming this is established cryptanalysis, not a workaround improvised for one challenge. Treat it as a fallback, not a first move, given the extra machinery it needs versus a straight linear solve.

Related

Berlekamp-Massey Algorithm — recover the minimal LFSR from raw keystream Linear Algebra over GF(2) — solving bit-level unknowns as a linear system mod 2 Stream-Cipher Keystream Reuse — the umbrella break behind every reused-keystream challenge Repeating-Key XOR — recovering key length and key from a Vigenère-style stream