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

The basic linear cryptanalytic method is to use a linear expression for only as much of the encryption al-
gorithm as is necessary. We chain together the linear expressions for the individual S-boxes into rounds, and the
rounds together to the point that we need.
The critical part comes when we run into key bits. As shown above, we will acquire key bits on the right-
hand side of the equation, but since those bits don't change, we ignore them. However, one of the times that
we do run into key bits, we will, instead of simply tacking them onto the end of our ever-growing linear ex-
pression, stop right there and brute-force the relevant key bits. Depending on where we stop, we will have a
different number of key bits that will affect the linear expression. Essentially, whichever key bits give us the
largest measured bias for a large number of plaintext-ciphertext pairs will be the key bits that, most likely, are
correct.
This is best illustrated with a simple example, as shown in Figure 6-4 . For the three-round variant, we brute-
force six of the bits that affect the output of the third round, and we figure out which key gives us the correct
bias. For each subkey (representing the values of the desired key bits concatenated), in the order of 0 to 63, we
can construct a list of how many plaintext-ciphertext pairs matched the linear expression on the previous page.
Figure 6-4 Linear cryptanalysis of a three-round variant of EASY1.