THE GARDEN

Geffe Generator (Nonlinear LFSR Combination via Multiplexer)

Updated 13 Sep 2026

• •

  What it is

  • •

    A classic stream-cipher construction attempting to fix raw LFSRs' linearity weakness by combining three independent LFSRs nonlinearly: one LFSR (the "selector") decides, bit by bit, which of the other two LFSRs' output to use — output $=L_2$ if $L_1=1$, else $L_3$. Despite genuinely introducing non-linearity (a multiplexer isn't a linear function of its inputs), the Geffe generator is a textbook-famous broken construction: each output bit still correlates with $L_2$'s bit about 75% of the time and with $L_3$'s bit about 75% of the time (since the selector is 1 half the time, and correct half the remaining time by chance), enabling classical statistical correlation attacks against each component LFSR independently — and, as demonstrated here, the entire construction can also be broken directly via an algebraic attack (see Algebraic Attack via Boolean Polynomial Ring (Gröbner Basis Key Recovery)), since the multiplexer logic itself is exactly expressible as a low-degree polynomial over $GF(2)$.

• •

  When to apply

  • •

    A stream cipher combines multiple LFSRs where one of them is used to choose between the others' outputs (an if/else or multiplexer pattern in the combining function) — recognizing this as a Geffe generator specifically (rather than just "some nonlinear combiner") points directly at its two well-known, well-studied attack families.

• •

  Symbols and assumptions

  • •

    $a$ is the selector bit, b and c the other two outputs. Assume independent uniform bits when calculating the 75% correlation.

• •

  Math — step by step

  • •
    1. If a=1, output z=b; if a=0, output z=c. Encode this as $z=ab\oplus(1\oplus a)c=ab\oplus c\oplus ac$. The two selected branches cannot both be active.
  • •
    2. Agreement with b is certain when a=1, and occurs with probability 1/2 when a=0. Hence $P(z=b)=1/2+(1/2)(1/2)=3/4$. The same calculation holds for c.
  • •
    3. A candidate state for the b register predicts a bit sequence. Score its agreements against z and look for a statistically strong candidate, then verify the entire construction. Nonlinearity alone does not remove correlation.
• •

  Worked example

  • •

    With $(a,b,c)=(1,0,1)$, the selector returns 0. The polynomial gives $1\cdot0\oplus(1\oplus1)\cdot1=0$. With $(0,0,1)$ it gives $0\oplus1=1$.

  • •

    Across the 8 equally likely triples, all 4 with a=1 agree with b. Among the 4 with a=0, the 2 with b=c also agree. Total: $6/8=3/4$.

• •

  Python

  • •

    def geffe_bit(b0, b1, b2):
            return b1 if b0 else b2
    
    def geffe_poly(b0, b1, b2):
            return (b0 & b1) ^ ((1 ^ b0) & b2)   # identical to geffe_bit for every input
    

• •

  SageMath

  • •

    See Algebraic Attack via Boolean Polynomial Ring (Gröbner Basis Key Recovery) for how this polynomial form is used symbolically to recover an unknown key.

• •

  Related

  • •

    Linear Feedback Shift Register (LFSR)

  • •

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

• •

  Cards

  • •

    What role does the "selector" LFSR play in a Geffe generator?

    • •

      It decides, bit by bit, which of the other two LFSRs' output becomes the overall keystream bit — a multiplexer, not a linear combination.

  • •

    What are the two classical attack families against a Geffe generator?

    • •

      Statistical correlation attacks (exploiting the ~75% bit-agreement between the output and each non-selector LFSR) and algebraic attacks (expressing the multiplexer as a GF(2) polynomial and solving directly).

◌ Explore connections in Graph view