Linear cryptanalysis

Linear cryptanalysis is, alongiside differential cryptanalysis, one of the most fundamental forms of cryptanalytic attack against symmetric block ciphers. Like differential cryptanalysis, it too is rooted in the statistical analysis of the cipher. Unlike it, though, it is a known-plaintext attack. We don't need access to an oracle to abuse it, only a lot of messages.

Originally introduced by Mitsuru Matsui in the early 1990s, this technique was used to mount the first known attack on the full 16 rounds of the Digital Encryption Standard (DES). Since then, it has become a cornerstone of cipher evaluation and design.

Here we'll go over the core ideas behind linear cryptanalysis: what it means to "approximate" a cipher with linear expressions, how we measure the quality of these approximations, and why (and how!) they can be exploited.

Linear Cryptanalysis

At its heart, linear cryptanalysis tries to find linear relationships between the input bits, output bits, and key bits of a cipher. In other words, we're interested in approximating nonlinear functions with linear ones. These relationships usually don’t hold always, and instead with some probability. If this probability is significantly different from 0.5 (i.e. very different from a random permutation, i.e. "biased"), we can use that bias to infer information about the key.

Somewhat more formally, the cryptanalyst's goal is to find Boolean expressions of the form:

$$P_i \oplus P_j \oplus \cdots \oplus C_k \oplus C_l \oplus \cdots = K_m \oplus \cdots$$

that hold with probability $p \neq \frac{1}{2}$, where:

• $P$: bits of the plaintext,
• $C$: bits of the ciphertext,
• $K$: bits of the key.

A truly random permutation (which is a cipher's goal to emulate) should have such expressions hold with probability exactly 0.5. Any consistent deviation can tell us something about the key.

Bias

A central idea in linear cryptanalysis is bias: the amount by which a linear approximation deviates from $\frac{1}{2}$. It can be understood as how dependable our approximation is. We calculate it as $p - \frac{1}{2}$ for a probability $p$, so it is bounded by $[-\frac{1}{2}, \frac{1}{2}]$. The greater the magnitude, the greater the bias; we want to get as far away from zero as possible.

Formally put, let $X$ be the function of some bits of the plaintext and ciphertext (and possibly the key), and $q$ a linear approximation of $X$. We define the bias $\varepsilon$ as: $$\varepsilon = \Pr[X = q] - \frac{1}{2}$$ The larger the absolute bias $|\varepsilon|$, the more useful the approximation. This may be counter intuitive at the moment, but a relation that's almost never holds is as useful as one that almost always holds; approximations that're no better than guesswork are what we seek to avoid. Even a small bias (e.g., $\varepsilon = 2^{-10}$) can be exploited with enough data, as we'll see later.

Correlation

For practical reasons, we prefer the bounds of our bias to be "nicer". Doubling the bias, we get the correlation for a given approximation. That is, we define $$ \textbf{corr} = 2\epsilon $$ Our correlation is then bounded by $[-1, 1]$. This comes with a lot of benefits we'll only see later. For now, we'll try to express everything in terms of correlation.

Approximating Basic Boolean Functions

Before we get to approximating an S-Box, it’s helpful to see how we approximate basic Boolean operations like AND, OR, and XOR. These approximations lay the groundwork for understanding how nonlinear components can be approximated with linear expressions.

Approximating XOR

Let’s start with the easy one. The XOR operation is already linear (over $\mathtt{F}_2$), so it doesn't need approximation: $$x \oplus y = x + y \mod 2$$ Finding linear combinations of bits via XOR'ing them (e.g. $x_1 \oplus x_2 \oplus x_5$) is exactly what we’re trying to use in linear cryptanalysis.

Approximating AND

The AND operation, however, is not linear. Consider the table:

We want to approximate this function with something linear (a XOR of input/output bits). One good approximation is simply: $$x \land y \approx x$$ This approximation is obviously correct if $y = 1$, which happens half the time (assuming random inputs), and is also correct whenever $x = 0$. In total, this approximation is correct 3 out of 4 times. So:

• $\Pr[f(x, y) = x] = \frac{3}{4}$
• Bias $\varepsilon = \frac{3}{4} - \frac{1}{2} = \frac{1}{4}$
• Correlation $\textbf{corr} = 2\epsilon = \frac{1}{2}$ This isn't the only (good) approximation though. Other possible approximations are:
• $x \land y \approx y$ (same bias),
• $x \land y \approx 0$ (correct in 3 out of 4 cases as well)

Approximating OR

Another common Boolean function is OR, which is also nonlinear. We know that the OR operation behaves as follows:

Immediately, we can spot several good approximations. The obvious one is $x \lor y \approx 0$, while a more interesting one is $x \oplus y$, both holding in 3 of out of 4 cases. This then gives us a bias of $\varepsilon = \frac{1}{4}$, and a correlation of $\textbf{corr} = \frac{1}{2}$.

Task Both OR and AND don't actually have "bad" approximations. That is, neither has a linear approximation that has a bias of $\varepsilon = 0$, and the absolute bias for every approximation is always $|\varepsilon| = \frac{1}{2}$. Using the basic properties of linear functions, prove this claim.

Why this matters

S-boxes are just small Boolean functions. In PRESENT's case we've 4 bits going in, and 4 bits coming out. Internally, they’re implemented using combinations of AND, OR, XOR, and NOT. We've shown the first two to be nonlinear, while the last two certainly are linear. In the next section, we'll create a Linear Approximation Table (LAT), by which we’re measuring how well we can approximate more complex Boolean functions (such as an S-Box) with XOR expressions, just as we did above.

The above understanding of biases in basic gates helps us appreciate where the approximations in the S-box come from, and why certain input/output combinations are more useful than others.