Linear Cryptanalysis - Modern Cryptanalysis: Techniques for Advanced Code Breaking - page 146

6.6 Linear Expressions and Key Recovery
The previous attack is only for a two-round variant of the cipher and does not go into how the key is derived
from a linear expression. Let's try building a slightly more complicated linear expression to represent a slightly
larger cipher. We are going to use the two linear expressions in Table 6-5 to attack a three-round EASY1 cipher.

Table 6-5 Two Linear Expressions Used to Perform Linear Cryptanalysis on the EASY1 Cipher
EXPRESSION BIAS

X 0 ⊕ X 1 ⊕ X 2 ⊕ X 3 ⊕ X 4 = Y 3 14

X 5 = Y 1 ⊕ Y 2 10

We simply chain together the two linear expressions. The combined bias for the two of them is therefore

We can then calculate the approximate number of pairs required:

Comparing this with the previous required number of plaintext-ciphertext pairs (131,072), we can see the
value of having linear expressions with higher biases.
Up until this point, we haven't really seen how the bits of the key fit into this analysis. Now I'll show how to
use the expressions to find the key bits.
The first question one might ask is, how do key bits affect these linear expressions for a cipher? In short, they
don't. This is the beauty of the linear cryptanalytic method. For example, if we have a simple cryptographic
function that operates on a plaintext (P) to produce a ciphertext ( C ), then we can use two keys (K 1 and K 2 ), as
well as an S-box function ( S ), to obtain

Assume that we have a linear expression for the S-box, say, X 0 = Y 1 ⊕ Y 3 . It turns out that this linear expression
will be true for the entire cryptographic function as well with the same bias as the original expression (or it will
be false with the same bias, if the key bits all XOR to 1 instead of 0). To show this, we rewrite the above equa-
tion as

We can then XOR in the appropriate key bits that the linear expression “runs through,” obtaining something
along the lines of

or, rewriting it:

The only thing changed is the right-hand side; instead of a 0, we have some key bits. Furthermore, the key bits
aren't going to change (since we are doing a known-plaintext attack against a single key); they are always go-
ing to XOR to a 0 or a 1. In the case of a 1, the sign of the bias just flip flops; and won't change much in the
expression.