THE GARDEN

LFSR State via Companion Matrix (Time-Reversal)

Updated 13 Sep 2026

• •

  What it is

  • •

    An LFSR clock is a linear map S_next = M*S over GF(2). When the feedback coefficient of outgoing cell 0 is 1, the map is invertible, allowing an observed state to be rewound by M^(-t). Known taps alone do not guarantee invertibility; also track exactly which clock the recovered state represents.

• •

  When to apply

  • •

    An LFSR's feedback taps are known (or just recovered), and you need the state at a different point in time than what's directly visible — especially recovering an original seed that was clocked forward some number of steps before any output became observable.

• •

  Symbols and assumptions

  • •

    States are column vectors over $GF(2)$. For a left-shifting n-cell register, matrix M has $M_{i,i+1}=1$ and the feedback coefficients in its last row.

• •

  Math — step by step

  • •
    1. Multiplication $S_{t+1}=MS_t$ reproduces the shift: row i copies old cell i+1, while the final row XORs the taps. Repeating gives $S_t=M^tS_0$.
  • •
    2. M is invertible exactly when the feedback includes outgoing cell 0 with coefficient 1. Otherwise that bit disappears and distinct states can merge.
  • •
    3. When invertible, $S_0=M^{-t}S_t$. You can also solve the feedback equation for the discarded bit and undo one shift at a time. This reverses the linear state transition, not an arbitrary nonlinear output filter.
• •

  Worked example

  • •

    For n=3, taps $\{0,1\}$, $M=\begin{pmatrix}0&1&0\\0&0&1\\1&1&0\end{pmatrix}$. Applying it to $(1,0,0)^T$ gives $(0,0,1)^T$.

  • •

    Given new state $(a,b,c)$, the old state must be $(c\oplus a,a,b)$ because $c=\text{old}_0\oplus\text{old}_1$ and $a=\text{old}_1$. Thus $(0,0,1)$ rewinds to $(1,0,0)$.

  • •

    For Destroyer’s taps, old cell 0 is $S^{\prime}_{127}\oplus S^{\prime}_0\oplus S^{\prime}_1\oplus S^{\prime}_6$. Prepend it to the first 127 new cells. Undo exactly 256 warm-up clocks after recovering the first observed state.

• •

  Python

  • •

    def mat_inv2(A):
            n = len(A)
            M = [A[i][:] + [1 if i==j else 0 for j in range(n)] for i in range(n)]
            row = 0
            for col in range(n):
                piv = next(r for r in range(row, n) if M[r][col] == 1)
                M[row], M[piv] = M[piv], M[row]
                for r in range(n):
                    if r != row and M[r][col] == 1:
                        M[r] = [M[r][j]^M[row][j] for j in range(2*n)]
                row += 1
            return [M[i][n:] for i in range(n)]
    
    S0 = mat_vec(mat_pow(mat_inv2(M), steps), S_t)   # recover the earlier state
    

• •

  SageMath

  • •

    M = Matrix(GF(2), n, n)  # build the companion matrix from the recovered taps
    S0 = (M^-1)^steps * S_t   # or equivalently M^(-steps) * S_t
    

• •

  Related

  • •

    Linear Feedback Shift Register (LFSR)

  • •

    Berlekamp-Massey Algorithm

• •

  Cards

  • •

    Why can an LFSR's state be "rewound" to an earlier point in time at all?

    • •

      When the outgoing cell has feedback coefficient 1, the clock matrix is invertible over GF(2). Its inverse undoes one transition; apply it the known number of warm-up clocks.

  • •

    What do you need to know before you can build the companion matrix and rewind the state?

    • •

      The exact feedback taps — either given directly, or recovered first via Berlekamp-Massey.

◌ Explore connections in Graph view