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

2. For each candidate set of key bits, calculate a T -value, representing the number of times that the linear
equation holds true with the plaintext-ciphertext pairs.
3. Select the candidate keys that are the farthest “away” from half the number of pairs. Thus, if N is the
number of pairs, calculate T - (N/2) for each candidate, with the end result being some set of key candid-
ates with | T - (N/2) | (the absolute value of the difference) being maximized.
The point here is we are trying all values of key bits, trying to find the most likely candidate set of them. For
example, if we had a 64-bit key and we managed to find an expression involving 32 bits of the key that required,
say, 2 20 operations per key, then we would have O (2 20 × 2 32 ) = O (2 52 ) operations to derive 32 bits of key. We
could then just simply brute-force the other 32 bits [in O (2 32 ) time], which would be much easier than the pre-
vious O (2 52 ) operations. Essentially, we would then have derived the key in less than O (2 53 ) operations.
The following sections help us to find these linear expressions, as well as estimations on the number of plain-
text-ciphertext pairs and the amount of time and space that this approach will take.
6.3 Linear Expressions for S-Boxes
The first step to constructing a full linear equation to use with Matsui's algorithms is learning how to calculate
simple linear expressions and how to determine their biases.
It's easiest to first look at an example. Consider the following 3-bit S-box
[3, 7, 2, 4, 1, 5, 0, 6]
(i.e., substitute 3 for 0, 7 for 1, 2 for 2, 4 for 3, etc.).
Finding linear expressions of S-boxes requires us to find equations involving the input bits and output bits,
such as X 0 ⊕ X 2 = Y 1 ⊕ Y 2 . We can run this linear equation against all possible input values (0-7) of the ex-
ample S-box, counting it true 2 out of 8 times [for S (3) = 4 and S (7) = 6], giving us a probability of 1/4 = 0.25.
The bias, usually abbreviated ε, is then ε = (2 − 4)/8 = −1/4. Figure 6-1 shows a small S-box with a linear ex-
pression drawn over it.
Figure 6-1 Graphical representation of the expression X 2 = Y 1 ⊕ Y 2 on a 3-bit S-box.
Keeping in mind the idea behind Matsui's Algorithm 2, we try every possible set of input bits and output bits
and measure the bias. We are interested most in linear expressions with the largest amount of bias (regardless of
sign).
Since we have three possible input bits and three possible output bits that we may either keep or omit in each
linear expression, we then have to look through 2 3 × 2 3 = 2 3+3 = 2 6 = 64 different expressions. Furthermore, we
have to try all possible values of the input-output value pairs which is 2 3 (since we have 3 input bits and the
output is completely determined by them). This gives us 2 6 x 2 3 = 2 9 = 512 operations in total on the S-box.