THE GARDEN

Correlation Attack on Filtered LFSRs (Belief Propagation)

Updated 19 Sep 2026

• •

  What it is

  • •

    A fast correlation attack treats a filtered LFSR’s output as a noisy version of a linear sequence. Parity constraints from the recurrence help correct those noisy observations and recover the internal state.

• •

  When to apply

  • •

    The filter has a biased linear approximation and enough observed keystream is available to decode a sequence satisfying the known recurrence.

• •

  Symbols and assumptions

  • •

    Destroyer’s output is z=1+F. The approximation is $\ell=x_1+x_2+x_5$. Let $y_t=u_{t+16}+u_{t+32}+u_{t+127}$ be the corresponding exact linear sequence, and observe $w_t=z_t+1$. All bit additions are XOR.

• •

  Math — step by step

  • •
    1. Enumerating all 64 filter inputs gives F=ℓ on 48 inputs. Thus w=z+1 agrees with y on 3/4 of uniform local input tuples. Using z without complementing it would give only 1/4 agreement.
  • •
    2. A linear combination of shifted copies of an LFSR sequence obeys the same recurrence. Hence $y_t+y_{t+1}+y_{t+2}+y_{t+7}+y_{t+128}=0$. These sparse checks link noisy observations across time.
  • •
    3. In characteristic 2, squaring cancels cross terms. Squaring the shift polynomial $1+D+D^2+D^7+D^{128}$ gives $1+D^2+D^4+D^{14}+D^{256}$. Repeated squaring supplies checks at power-of-two spacings. These extra checks are related, not independent new measurements.
  • •
    4. Under a crossover-probability 1/4 channel model, the initial log odds for y_t=0 over y_t=1 are $L_t=(1-2w_t)\log3$. Positive means 0 is favored; negative means 1 is favored.
  • •
    5. Belief propagation alternates parity-check messages $m_{c\to v}=2\operatorname{atanh}(\prod_{u\in c\setminus v}\tanh(m_{u\to c}/2))$ and variable messages $m_{v\to c}=L_v+\sum_{d\ne c}m_{d\to v}$. Excluding the recipient prevents immediately feeding a message back to itself. Decide bit 1 when total log odds are negative.
  • •
    6. From decoded y, solve 128 equations $y_t=hM^tS$ over GF(2), where h selects cells 16,32,127. The resulting 128×128 observation matrix has rank 128 for this recurrence, checked offline. This yields S at the first observed clock.
  • •
    7. Reverse 256 warm-up clocks to recover the initial key state. Pack bits in the source’s most-significant-bit-first order. Regenerate all 20,000 observed bits; a parity-consistent or plausible-looking candidate is not sufficient.
• •

  Worked example

  • •

    One parity check is $y_0+y_1+y_2=0$. Suppose independent incoming beliefs favor $y_1=y_2=0$ with probability 0.75 each. Their parity is 0 with probability $0.75^2+0.25^2=0.625$, so the check sends odds $0.625/0.375=5/3$ favoring y0=0.

  • •

    If the direct observation w0=1, its channel odds favor y0=0 by only 1/3. Combining this one independent check gives odds $(1/3)(5/3)=5/9$, so y0=1 is still favored. Several consistent checks can eventually outweigh one noisy observation.

• •

  Checks and pitfalls

  • •

    Cycles in the parity graph and temporal dependence in the filter errors make this an approximate decoder; convergence is not guaranteed. Clip numerical messages before atanh, bound iterations, and verify against the actual nonlinear generator.

  • •

    Offline synthetic tests of the pasted final solver recovered and verified 2 of 3 fixed keys; one failed to converge. These are local reproducibility checks, not a live service replay or an estimate of the general success probability.

  • •

    With 2,500 zero plaintext bytes, XOR encryption exposes 20,000 keystream bits. The pasted service also imposes a 15-second connection timeout; precomputation and runtime need separate attention.

• •

  Related

  • •

    Boolean Functions and Algebraic Normal Form (ANF)

  • •

    Annihilator Attack on Filtered LFSRs (Quadratic Linearization)

  • •

    LFSR State via Companion Matrix (Time-Reversal)

  • •

    Sequential Confidence Amplification for Noisy Binary Oracles (SPRT-style)

• •

  Python

  • •

    import math, numpy as np
    
    def check_message(incoming):
        p = np.tanh(np.clip(incoming/2, -10, 10))
        return np.array([2*np.arctanh(np.clip(np.prod(np.delete(p,j)),
                                                -.999999,.999999))
                         for j in range(len(p))])
    
    def initial_llr(observed_w):
        # w agrees with the linear sequence with probability 3/4.
        return (1 - 2*np.asarray(observed_w, dtype=np.int8))*math.log(3)
    

◌ Explore connections in Graph view