Linear S-Box Cryptanalysis (Affine Cipher Break)

Updated 13 Sep 2026

• •

  What it is

  • •

    A block cipher's resistance to algebraic attacks depends on its S-box being genuinely non-linear (real AES achieves this via a multiplicative-inverse-in-$GF(2^8)$ step). If an S-box is instead just an affine function of its input ($S(x) = c \cdot x \oplus k$ for fixed field constants $c, k$), then every round operation built from it becomes linear or affine too, and the entire multi-round cipher collapses into a single affine function of plaintext and key: $C = L(P) \oplus K_{eq}$, where $L$ is a fixed, invertible linear map and $K_{eq}$ is one constant absorbing every round key's contribution. That's breakable two ways: (1) directly — since $L(\mathbf{0}) = \mathbf{0}$, encrypting an all-zero plaintext gives $K_{eq}$​ outright, after which $C \oplus K_{eq} = L(P)$ inverts by running each linear component backward; or (2) symbolically — treat every key bit as a free variable, build the cipher's output as linear polynomials over $GF(2)$ from one known plaintext/ciphertext pair, and solve the resulting linear system (trivial for a Gröbner basis solver).

• •

  When to apply

  • •

    A "custom AES" or similar cipher's S-box looks unusual — checking whether it's affine (rather than assuming non-linearity) is worth doing whenever a challenge hints at "linear cryptanalysis," a home-rolled S-box, or the category itself suggests linearity.

• •

  Math

  • •

    If $S(x) = c \cdot x \oplus k$ (multiplication in $GF(2^8)$), then $S(0) = k$ reveals the additive constant directly, and $S(x) \oplus k = c \cdot x$ is a pure linear map, invertible via a precomputed multiplication table for $c^{-1}$.

• •

  Worked example

  • •

    Testing this challenge's 256-entry S-box against the hypothesis $S(x) = (x \cdot 0x2a) \oplus 0x2a$ (multiplication in $GF(2^8)$, AES's reduction polynomial) matched all 256 entries exactly — confirming the S-box is fully affine, not the genuinely non-linear real-AES S-box it was dressed up to resemble.

• •

  Python

  • •

    def gmul(a, b):  # GF(2^8) multiplication, AES modulus 0x11b
        p = 0
        for _ in range(8):
            if b & 1: p ^= a
            hi = a & 0x80
            a = (a << 1) & 0xFF
            if hi: a ^= 0x1b
            b >>= 1
        return p
    
    inv_mult = [0] * 256
    for i in range(256):
        inv_mult[gmul(i, 0x2a)] = i   # inverse of the *linear* multiplicative core
    
    # K_eq = encrypt(b"\x00" * 16); then per ciphertext block: strip K_eq, run
    # inv_mix_columns / inv_shift_rows / inv_sub_bytes (via inv_mult — no affine
    # constant needed once K_eq is stripped out)
    

• •

  SageMath

  • •

    from sage.crypto.sbox import SBox
    S = SBox(sbox_table)
    S.polynomials(groebner=True)   # degree-1 (affine) equations confirm linearity at a glance
    # then build the whole cipher symbolically over GF(2), plug in one known
    # plaintext/ciphertext pair, and solve the resulting linear ideal for the key bits
    

• •

  Related

  • •

    AES

• •

  Cards

  • •

    What's the practical consequence of a block cipher's S-box being affine instead of non-linear?

    • •

      The entire multi-round cipher collapses into a single affine function of plaintext and key, breakable either by direct inversion or by solving a linear system.

  • •

    What's the fastest way to check whether a suspicious S-box is actually linear/affine?

    • •

      Sage's SBox(table).polynomials(groebner=True) — degree-1 output equations confirm affineness immediately.

◌ Explore connections in Graph view