Linear Cryptanalysis

Question

What is the principle of linear cryptanalysis, as applied to a block cipher ? For instance, this page gives the rough outline of differential cryptanalysis.

Answer 1

There is a reasonably clear description in section 2 of Pascal Junod's thesis.

A linear approximation, which allows guessing 1 key bit

Linear cryptanalysis begins by finding a linear equation which holds with probability distinct from $1/2$. We are talking about linearity in $\mathbb{Z}_2$, i.e. we XOR bits together. The question is a XOR of some specific bits of the plaintext, the ciphertext and the key (I am talking about linear cryptanalysis of a block cipher, as it was originally designed, about DES by Matsui in 1993). The XOR of several bits is either 0 or 1, and, assuming that the block cipher is "perfect", it should give 0 with probability $1/2$ and 1 with probability $1/2$.

Now let's assume that a given equation will yield 1 with probability slightly higher than $1/2$: for a given key, if you do the XOR with many plaintexts and corresponding ciphertexts, you will get 1 a little more often that you will get 0. This is the bias which linear cryptanalysis will exploit.

The first basic step is that by gathering many plaintext/ciphertext pairs, where the encryption used the key we want to attack (this is a "known plaintext attack"). For each of them, the equation is a XOR between a few bits of the plaintext, a few bits of the ciphertext, and a few bits of the key. For each pair, we know the plaintext and ciphertext, so the equation tells us what is the value of the XOR of the few key bits. The equation is "right" a bit more often than "wrong", so, with enough pairs, a majority emerges and gives us a definite answer. This yields 1 indirect key bit.

Guessing many more key bits

1 key bit is not much (although it divides by two the cost of exhaustive search), so Matsui enhanced the attack in the following way. Let's consider the linear cryptanalysis over the first 15 rounds of DES (DES has 16 rounds). That cryptanalysis has a corresponding linear equation. A quirk of DES (at that point it becomes useful to have a look at some schematics about DES) is that we can "mostly" see the output of the 15th round. For linear cryptanalysis, we are interested in some specific bits of the plaintext and of the "ciphertext", the ciphertext being here the output of the 15th round. We have the output of the 16th round; from it, we can compute the value of the bits we are interested in, from the output of the 15th round, provided that we correctly guessed a dozen specific key bits. That's because the 16th round modifies the output of the 15th round using the key, but not all key bits are involved in the computation of each bit for this round. Only 12 key bits in total have any influence on our "back-computation" where we try to compute the bits-for-the-equation in the 15th round.

Now comes the really smart part. Matsui runs 4096 linear cryptanalyses in parallel. That is, given the plaintext/ciphertext pairs (for the full 16 rounds of DES), Matsui tries each of the $2^{12} = 4096$ possible values for the 12 key bits, each of them allowing him to recompute the output of the 15th round, and apply the 1-bit linear cryptanalysis. Now, for the one instance where he guessed correctly, the 1-bit linear cryptanalysis "works" and a clear majority emerges; but for the others, the incorrect guess on the key bits means that we work with wrong values (for the 15th-round bits), so the equation does not work and no clear majority emerges. So the attack not only yields one indirect key bit (from the equation) but also twelve additional key bits: the twelve bits which make the 15-round linear approximation work. 13 key bits, now that's good: it divides cost of exhaustive key search by 8192.

Matsui got even further by doing the "guess some key bits" for two rounds, the first and the last, using a linear approximation of 14 rounds (rounds 2 to 15). This yields 22 direct key bits (and one indirect). DES has 56 key bits, so the remaining $2^{33}$ are easily obtained by exhaustive key search (only 8 billions of possibilities).

Limitations

The real problem with linear cryptanalysis is that it needs many known plaintext/ciphertext pairs, enough for a clear majority to emerge when applying the linear approximation (the equation is only slightly more often right than wrong). Matsui computed the number of needed pairs to be $2^{43}$, although Junod found out that with a few tweaks, $2^{39}$ are enough. Each plaintext is 8 bytes, so we are talking about 4 terabytes. There are not many attack situations where the attacker can correctly guess 4 terabytes of plaintext, and still needs to obtain the key...

(Linear cryptanalysis of DES is how I first entered the realm of cryptography; my task was to reimplement Matsui's method on DES reduced to 8 rounds. The approximation on 6 rounds is much better than on 14 rounds, so it requires only a million or so plaintext/ciphertext pairs. It took less than a minute on the machines of that era, 50 MHz Sparc systems. The part about guessing some key bits and doing many 1-bit cryptanalyses simultaneously is what took me the most time to understand. It was very educational.)