Linear Cryptanalysis

1. Core Idea: Linear Approximations with Bias

Linear cryptanalysis (Matsui, 1993) is a known-plaintext attack: find linear equations $P_{i_1} \oplus \cdots \oplus C_{j_1} \oplus \cdots \oplus K_{k_1} \oplus \cdots = 0$ that hold with probability $p
e 1/2 $. The **bias**$ \epsilon = |p - 1/2| $is the signal — ideal cipher gives$ \epsilon = 0$; S-box nonlinearity leaves small biases attackers amplify. Needs only known (not chosen) plaintext — weaker attacker assumption than differential, but far more data.

2. Piling-Up Lemma (Worked)

Combine approximations: bias of XOR of $n$ independent approximations:

\epsilon_{1..n} = 2^{n-1}\prod_{i=1}^{n}\epsilon_i \quad \text{(Piling-Up)}

Worked: S-box approximations with biases $\epsilon_1 = 1/4$ , $\epsilon_2 = 1/8$ , $\epsilon_3 = 1/8$ : combined $\epsilon = 2^2 \times \frac{1}{4} \times \frac{1}{8} \times \frac{1}{8} = \frac{4}{256} = \frac{1}{64}$ . Data needed $\approx c/\epsilon^2$ (Matsui's rule: $N \approx 1/\epsilon^2$ pairs): here $N \approx 64^2 = 4096$ known plaintexts. Each added round multiplies biases (shrinking fast) — same exponential-rounds defense as differential.

S-box linear table logic: for S-DES $S0$ , mask relation $a \cdot X = b \cdot S(X)$ over $GF(2)$ inner products: count agreements over 16 inputs; $10/16 \to \epsilon = 10/16 - 1/2 = 1/8$ . Best nonzero entry per S-box is its linear strength; DES S-boxes keep max bias $\le 1/4$ -ish per box.

3. Matsui's Algorithm 1 and 2 (Key Recovery)

Algorithm 1 (key-bit decision): use $r-1$ -round approximation with bias $\epsilon$ : count agreements over $N$ known pairs; if agreements $> N/2$ , key-XOR sum $= 0$ , else $1$ . Success rate from normal approximation: $N = 1/\epsilon^2$ gives $\approx 97.7\%$ .
Algorithm 2 (key extraction): peel last round — for each candidate last-subkey, partially decrypt and measure bias of the approximation; right key shows $|\epsilon|$ , wrong keys $\approx 0$ . Recovers 26 key bits of DES with $2^{43}$ known plaintexts; remaining 30 by brute force → total $\approx 2^{43}$ data + $2^{43}$ work (1994 experiment: 50 days).
DES full-16 needs $2^{43}$ known pairs ( $\approx 1$ TB) — impractical; 8-round DES needs only $\approx 2^{21}$ .

4. Differential vs Linear (Exam Table)

Point	Differential (Topic 5)	Linear (this topic)
Plaintext	Chosen pairs with fixed $\Delta$	Known (arbitrary) pairs
Signal	S-box difference non-uniformity, prob $p$	Linear-approximation bias $\epsilon = \\|p-1/2\\|$
Combiner	$P = \prod p_i$	$\epsilon = 2^{n-1}\prod\epsilon_i$ (Piling-Up)
Data	$\approx c/P$	$\approx c/\epsilon^2$
DES-16 cost	$2^{47}$ chosen	$2^{43}$ known (Matsui experiment)
Designer defense	Low max differential prob + rounds	Low max linear bias + rounds (wide trail bounds both)

AES: max S-box bias $2^{-4}$ with branch number 5 → 4-round bias $\le 2^{-75}$ , data $2^{150}$ — immune.

Exam Points

Bias definition + Piling-Up formula with $1/4, 1/8, 1/8 \to 1/64$ worked combiner — 5-mark numerical core.
$N \approx 1/\epsilon^2$ rule + Matsui Algorithm 1 majority logic.
Known-vs-chosen distinction + full table differential-vs-linear — guaranteed 5-marker.
DES numbers ( $2^{43}$ known, 50-day experiment) vs AES immunity line.

Linear Cryptanalysis