THE GARDEN

Annihilator Attack on Filtered LFSRs (Quadratic Linearization)

Updated 19 Sep 2026

• •

  What it is

  • •

    An annihilator is a nonzero low-degree Boolean polynomial g with z(x)g(x)=0 for every input. When observed z=1, it forces g=0 and can replace a high-degree filter equation with an easier one.

• •

  When to apply

  • •

    A filtered LFSR has known linear state evolution and a filter with a useful low-degree annihilator. This is an exact algebraic attack, distinct from statistical correlation decoding.

• •

  Symbols and assumptions

  • •

    Destroyer uses 128 unknown initial bits k. At each output, filter inputs are cells 0,16,32,64,96,127, named $x_0,\ldots,x_5$. Actual output is z=1+F.

• •

  Math — step by step

  • •
    1. For the supplied filter, use $g=x_0x_1+x_0x_2+x_0x_5+x_1x_2+x_1x_4+x_1x_5+x_2x_4+x_2+x_4x_5+x_5$. Exhaustive evaluation of all 64 inputs gives z·g=0. It is g that annihilates z=1+F; do not substitute F for z.
  • •
    2. Keep observations with z_t=1, for which $g(x(t))=0$. A zero output supplies no such constraint: $0\cdot g=0$ regardless of g.
  • •
    3. Propagate each tapped state bit as a linear form in the 128 original k-bits. Substituting into degree-2 g produces a degree-at-most-2 equation in k. In the Boolean ring, $k_i^2=k_i$.
  • •
    4. Lift monomials to variables $V=(k_i,\ k_ik_j\text{ for }i<j)$. There are $128+\binom{128}{2}=8256$ columns. Every selected output adds a homogeneous linear equation, giving AV=0 over GF(2).
  • •
    5. Compute the kernel and enforce product consistency $V_{ij}=V_iV_j$. The zero vector always solves a homogeneous system. If rank is 8255, the one-dimensional kernel has one nonzero vector; test whether it encodes a valid key. Higher nullity requires more work than taking the first basis vector.
  • •
    6. Rebuild the real generator from each candidate key and compare the full observed keystream. Enough equations by count does not guarantee independent rows, a unique key, or acceptable runtime.
• •

  Worked example

  • •

    Toy filter z=ab has annihilator g=1+a: $ab(1+a)=ab+a^2b=ab+ab=0$. Observing z=1 therefore forces a=1; observing z=0 alone does not.

  • •

    Toy lift with two bits: V=(a,b,v), where v=ab. Equations a+b=0 and b+ab=0 become a+b=0 and b+v=0. The kernel is {000,111}; its nonzero vector gives a=b=v=1 and passes v=ab. The zero vector illustrates why a homogeneous solve needs candidate interpretation.

• •

  Checks and pitfalls

  • •

    The local filter check found g=1 on 16/64 inputs and z=1 on 32/64; their supports are disjoint. For a nonzero valid lifted key, rank cannot be 8256 because that would leave only V=0.

  • •

    The dump’s middle solver is this annihilator approach. Its later NumPy solver uses biased linear observations and belief propagation instead.

  • •

    Reference: Claude Carlet, Boolean Functions for Cryptography and Coding Theory, discussion of annihilators and algebraic immunity.

• •

  Related

  • •

    Boolean Functions and Algebraic Normal Form (ANF)

  • •

    Linear Feedback Shift Register (LFSR)

  • •

    Algebraic Attack via Boolean Polynomial Ring (Gröbner Basis Key Recovery)

  • •

    Correlation Attack on Filtered LFSRs (Belief Propagation)

• •

  Python

  • •

    from itertools import product
    
    def annihilator_g(x):
        x0,x1,x2,x3,x4,x5 = x
        return ((x0&x1)^(x0&x2)^(x0&x5)^(x1&x2)^(x1&x4)^
                (x1&x5)^(x2&x4)^x2^(x4&x5)^x5)
    
    # F is the exact six-input filter copied from the challenge.
    assert all(((1 ^ F(x)) & annihilator_g(x)) == 0
               for x in product((0,1), repeat=6))
    # Build lifted rows only for observations z_t == 1, solve the GF(2)
    # kernel, enforce v_ij == v_i*v_j, then regenerate the full stream.
    

◌ Explore connections in Graph view