How Linear Cryptanalysis Exploits Linear Approximations

Linear cryptanalysis is a prominent known-plaintext attack used against symmetric block ciphers to recover secret key bits. It operates by identifying and exploiting statistically biased linear relations between the bits of plaintext, ciphertext, and the secret key. By modeling non-linear components—primarily Substitution boxes (S-boxes)—as probabilistic linear approximations over the binary Galois field \(\mathbb{F}_2\), an attacker can combine these approximations across multiple cipher rounds to deduce the key using statistical analysis.

The Binary Foundation and Linearity

In binary symmetric cryptography, operations occur in \(\mathbb{F}_2\), where bitwise addition corresponds to the XOR (\(\oplus\)) operation and multiplication corresponds to the AND (\(\wedge\)) operation. An operation or boolean function is strictly linear if it preserves vector addition:

\[f(x \oplus y) = f(x) \oplus f(y)\]

Linear operations include bit permutations, rotations, and XOR additions (such as key mixing). However, secure ciphers introduce non-linear components, such as S-boxes, to prevent the entire encryption process from collapsing into a solvable system of linear equations.

Constructing Linear Approximations of Non-Linear S-Boxes

Linear cryptanalysis evaluates how closely a non-linear S-box can be approximated by a linear combination of its input and output bits. A linear approximation of an S-box takes the form:

\[\bigoplus_{i \in I} X_i = \bigoplus_{j \in J} Y_j\]

Where \(X_i\) represents specific input bits and \(Y_j\) represents specific output bits.

In a purely random mapping, any linear equation over input and output bits holds true with a probability of exactly \(p = 1/2\). In deterministic S-boxes, certain input-output linear combinations hold true with a probability \(p \neq 1/2\). The difference:

\[\epsilon = p - \frac{1}{2}\]

is known as the bias or linear probability bias. An attacker systematically tests all possible input and output masks against the S-box to construct a Linear Approximation Table (LAT), which documents the bias for every potential combination.

Chaining Approximations Across Rounds (Matsui’s Piling-Up Lemma)

To target an entire cipher, the linear approximations of individual S-boxes across multiple rounds must be linked together. The intermediate linear terms between rounds cancel out when combined using XOR.

The overall bias of the combined multi-round approximation is computed using Matsui’s Piling-Up Lemma. If \(n\) independent random binary variables \(X_1, X_2, \dots, X_n\) have biases \(\epsilon_1, \epsilon_2, \dots, \epsilon_n\), the probability that their XOR sum equals 0 has a total bias \(\epsilon_{total}\) given by:

\[\epsilon_{total} = 2^{n-1} \prod_{i=1}^{n} \epsilon_i\]

As long as \(\epsilon_{total} \neq 0\), a deterministic linear path exists through the cipher connecting specific plaintext bits (\(P\)), ciphertext bits (\(C\)), and key bits (\(K\)):

\[\bigoplus_{a} P_a \oplus \bigoplus_{b} C_b = \bigoplus_{c} K_c\]

The Key Recovery Mechanism

Once a multi-round linear characteristic with a significant bias \(\epsilon_{total}\) is established, the attacker executes the attack:

  1. Data Collection: The attacker collects a large number \(N\) of known plaintext-ciphertext pairs \((P, C)\). The required data complexity is proportional to the inverse square of the bias: \[N \approx c \cdot \epsilon_{total}^{-2}\] where \(c\) is a small constant.
  2. Hypothesis and Partial Decryption: The attacker guesses the subset of subkey bits involved in the final round’s S-boxes associated with the linear trail. Using these guessed bits, the attacker partially decrypts the ciphertext by one round.
  3. Statistical Counting: For each key guess, the attacker computes the linear equation across all \(N\) pairs and measures the empirical bias.
  4. Key Identification: The candidate subkey that yields an empirical bias closest to the theoretical bias \(|\epsilon_{total}|\) is identified as the correct key, while incorrect guesses yield a bias close to zero.