liveBook · Manning

Berlekamp–Massey algorithm

As explained in Hacking Cryptography

The Berlekamp–Massey algorithm finds a shortest linear feedback shift register that generates a given binary sequence.

The Berlekamp–Massey algorithm finds the shortest LFSR—its taps and initial state—that generates a given binary sequence, even when the register length is unknown. section 4.2.2

For a practical exploit, testing candidate lengths can replace the harder algorithm: construct and invert the LFSR matrix for each length, then accept the first error-free reconstruction. section 4.2.2

An LFSR recovery workflow uses:

  • Use the final observed bits as the recovered register state and clone the LFSR. section 4.2.2

Known-plaintext stream-cipher attack

Known plaintext such as “ATTACK AT ” reveals keystream bits by XORing it with the ciphertext. Candidate LFSR lengths are tested, and a valid clone decrypts the timestamp suffix.

How Hacking Cryptography covers it

How deep it goes
Defines shortest-LFSR recovery but stops short of deriving Berlekamp–Massey, using brute-force length testing instead.
Examples
Uses an ATTACK AT prefix, extracted keystream bits, candidate register lengths, and recovered timestamp plaintext.
What it assumes
Assumes LFSR recurrences, observed binary sequences, known plaintext, and binary matrix inversion.
What you can do after
Apply it to reconstruct an LFSR and decrypt ciphertext when a plaintext prefix exposes its keystream.
How it connects
Connects LFSRs, known-plaintext attacks, stream ciphers, matrix inversion, and binary linear recurrences.
Cover of Hacking Cryptography
liveBookmanning.com
Read Hacking Cryptography on liveBook Get the book at manning.com

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Hacking Cryptography. The section links point to the parts of the book it draws on.