Berlekamp-Massey Algorithm — recover the minimal LFSR from raw keystream

Berlekamp-Massey finds the shortest LFSR — its minimal feedback (connection) polynomial and linear complexity L — that reproduces a given binary sequence, in roughly O(n·L) field operations (worst case O(n²) when L is close to n).

The signal that betrays it

You are looking at raw keystream bits (or a bitstream you've reduced to keystream via known-plaintext XOR) and you *don't* know the LFSR's taps — only that the source smells linear: short period relative to the bit count, or a challenge that says "shift register", "taps", "feedback polynomial" without giving them to you. The diagnostic use is as valuable as the recovery use: run Berlekamp-Massey on any suspicious binary sequence and look at the recovered complexity L versus the sequence length n. If L comes out much smaller than n/2, the sequence *is* LFSR-like (or LFSR-adjacent) and the recovered polynomial predicts the rest of it; if L is close to n/2, the sequence looks like it has no simple linear structure — Berlekamp-Massey doesn't just fail quietly there, it tells you "not this attack" and it's the fastest way to rule out an LFSR hypothesis before spending time hand-deriving taps.

How it's exploited

Feed it enough bits. The algorithm needs at least 2L consecutive output bits to nail down an LFSR of true complexity L — but since L is exactly what you're trying to find out, the operational rule of thumb is simpler: feed it everything you have. There's essentially no downside to over-supplying bits (it costs you compute, not correctness), and under-supplying is the actual failure mode — with fewer than 2L bits the algorithm returns a polynomial consistent with what it's seen but not the true minimal one, and it will predict garbage past the boundary.

What comes out. The algorithm returns (L, C): the linear complexity L and the connection polynomial C(x), whose nonzero coefficients *are* the taps. This is a direct handoff into LFSR State Recovery — when the keystream itself hands you the seed — Berlekamp-Massey is specifically the "unknown taps" branch of that problem: once you have C, clock the recovered LFSR forward from the known window to predict/extend the keystream, or XOR it against ciphertext to recover plaintext beyond the bits you fed in.

Minimal reference implementation (bits as a list of 0/1, GF(2) arithmetic throughout): ``python def berlekamp_massey(bits): # bits: list of 0/1 C, B = [1], [1] L, m, b = 0, 1, 1 for n in range(len(bits)): d = bits[n] for i in range(1, L + 1): d ^= C[i] * bits[n - i] if d == 0: m += 1 elif 2 * L <= n: T = C[:] C += [0] * (len(B) + m - len(C)) for i, bb in enumerate(B): C[i + m] ^= bb L, B, m = n + 1 - L, T, 1 else: C += [0] * (len(B) + m - len(C)) for i, bb in enumerate(B): C[i + m] ^= bb m += 1 return L, C # complexity L, connection polynomial C ` In practice, don't hand-roll it under time pressure: SageMath ships berlekamp_massey(sequence) over GF(2)`, and it's the faster path in a live engagement — reach for the library call first, keep the from-scratch version only as a fallback when Sage isn't available or you need to adapt it to a non-binary field.

Non-binary sequences. The same algorithm generalizes to any field, not just GF(2) — if the "keystream" is actually a sequence of field elements (e.g. an LCG-like generator over a prime field dressed up as a stream cipher), Berlekamp-Massey over that field recovers the equivalent minimal linear recurrence. The core idea — find the shortest linear recurrence consistent with the observed run — is the same mechanism used, more generally, in PRNG State Prediction — recovering the internal state of a non-cryptographic generator whenever a generator's output turns out to satisfy *some* linear recurrence even if it isn't literally an LFSR.

What does NOT work

- Guessing taps by hand from a short window. It's tempting to eyeball a handful of bits and propose a tap set, but unless the register is tiny this is a waste of time compared to just running the algorithm — Berlekamp-Massey is the closed-form answer to exactly this guess, and it's cheap. - Feeding it fewer than `2L` bits and trusting the output. The algorithm will still return *a* polynomial, but it's only guaranteed minimal and correct once you've crossed the 2L threshold for the true complexity. If predictions past your known window start being wrong, the first suspect is "not enough bits", not "wrong technique" — go back and get more keystream before concluding the source isn't linear at all. - Applying it directly to a nonlinear combiner or filter generator. If the keystream comes from combining multiple LFSRs through a nonlinear boolean function (a combination or filter generator), the observed output sequence is *not* itself the output of a single short LFSR, so Berlekamp-Massey either fails to converge to a small L or returns a large, useless complexity close to n. A large recovered L here is itself the tell that you're facing a nonlinear generator and need a correlation attack or an algebraic attack per output tap instead — see LFSR State Recovery — when the keystream itself hands you the seed for that branch. Don't keep throwing more bits at it hoping L will shrink; it won't, because there genuinely isn't a short linear recurrence to find. - Treating it as a decryption primitive on its own. Berlekamp-Massey only recovers structure (taps + complexity); it has no opinion about the LFSR's *initial state* beyond what's implicit in the bits you fed it, and it does nothing for Stream-Cipher Keystream Reuse — the umbrella break behind every reused-keystream challenge scenarios where the real problem is that you have ciphertext-ciphertext XOR, not raw keystream — peel that layer first (crib-drag or known-plaintext) before Berlekamp-Massey has anything linear to chew on.

Related

LFSR State Recovery — when the keystream itself hands you the seed 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 PRNG State Prediction — recovering the internal state of a non-cryptographic generator