Linear Cryptanalysis & Approximation Tables

Linear cryptanalysis (Matsui, 1993) is a known-plaintext attack that finds linear approximations (XOR of specific bits) of a cipher that hold with probability p ≠ 1/2. Using many plaintext-ciphertext pairs, statistical bias reveals key bits.

A linear approximation for an S-box: sum of selected input bits XOR sum of selected output bits = 0 (mod 2) with probability p. Expressed as: P[a·x XOR b·y = 0] = 1/2 + ε, where a,b are bit masks and ε is the bias (|ε| >> 0 is desirable).

The LAT counts: for each input mask a and output mask b, the number of inputs x where (a·x) XOR (b·S(x)) = 0. Subtract 2^{n-1} to get the bias. A good S-box has |max_bias| = 1 (probability 1/2 ± 1/2^{n/2}) — as flat as possible.

For independent linear approximations through multiple rounds, biases multiply: ε_total = 2^{r-1} * ε_1 * ε_2 * ... * ε_r. Each round approximation halves the effective bias. After many rounds, total bias approaches 0, requiring exponentially more pairs to detect.

To attack r-round cipher: find linear trail ε through r-1 rounds. Collect N = 1/ε^2 known plaintexts. For each candidate last-round key byte k': XOR-decrypt last round partially, check if the linear approximation holds more than N/2 times. Correct k' shows correct bias.

Matsui attacked 16-round DES in 1993 using a 14-round linear approximation with bias 2^{-21.4}. Required 2^{43} known plaintexts. Recovered 26 key bits in phase 1; remaining 30 by exhaustive search. First practical attack faster than brute force on full DES.

AES S-box has maximum LAT entry |ε| = 4/256 = 1/64 per S-box. The Wide Trail Strategy bounds the number of active S-boxes in any 4-round trail to ≥ 25. Total bias ≤ (1/64)^{25/2} ≈ 2^{-75}. Requires 2^{150} known plaintexts — infeasible.

Differential: known/chosen plaintext pairs; exploits output differences. Linear: known plaintexts; exploits statistical linear approximations. Both are chosen-plaintext for practical attacks. Both are design criteria: S-boxes must resist both (low DDT max AND low LAT max).

Use multiple linear approximations simultaneously to reduce data complexity. Nyberg and Leander extended Matsui's method: combining M approximations reduces data by factor log(M). Applied to PRESENT, SIMON, and other lightweight ciphers.

Linear approximation applied to stream ciphers: find correlation between the keystream and a linear function of LFSR output. This correlation (if non-zero) enables faster-than-exhaustive key recovery. Inspired design of nonlinear combining functions in stream ciphers.

Integral cryptanalysis (Knudsen-Wagner): choose a set of plaintexts where certain bytes take all 256 values while others are fixed. After several rounds, XOR of all outputs in certain positions is 0 (balanced). Exploits AES's structure; breaks reduced-round AES efficiently.

What does the piling-up lemma state about combining linear approximations?

Linear cryptanalysis finds biased linear approximations of S-boxes. AES resists via its LAT-optimal S-box and Wide Trail. Matsui broke DES with 2^43 known plaintexts using a 14-round trail. Next: birthday attacks and collision finding.