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

32, 22, 29, 52, 19, 12, 50, 5, 51, 11, 18, 59, 41, 36, 30, 17, 38, 10,
4, 58,
43, 35, 24]
Furthermore, a permutation will take place in between rounds to accomplish more diffusion. Here is the per-
mutation used throughout the cipher:
[24, 5, 15, 23, 14, 32, 19, 18, 26, 17, 6, 12, 34, 9, 8, 20, 28, 0, 2,
21, 29,
11, 33, 22, 30, 31, 1, 25, 3, 35, 16, 13, 27, 7, 10, 4]
Recall also that six 6-bit S-boxes feed into the 36-bit P-box, which is then XORed with an 18-bit key (the
36-bit wide full key used in the cipher is derived from repeating the 18-bit key, concatenating it to itself to get
36 bits).
This requires the input to be first split six ways, fed into the S-boxes, and then rebuilt and run through the
P-box, and then finally XORed with the key. Repeat this for every round.
Note that the individual S-boxes are relatively small (as far as number of input and output bits): We can enu-
merate all possible linear expressions and test for large biases. Once we have discovered some expressions with
large biases, we can start to chain rounds together, discovering linear expressions that operate between multiple
rounds. Obviously, the more rounds we have to “stitch” together in this manner, the lower the bias is going to
be, and therefore the tougher our job is going to be.
Since more rounds generally lower the overall bias, it makes no sense (from the point of view of the commu-
nicating parties) to use a 1-round variant of the cipher. Even without linear cryptanalysis, we can use the known
S-box and P-box values and simply rewrite the known-plaintext problem to be a simple XOR equation. We can
do this because the plaintext can be processed up until the key XOR, and the ciphertext is merely the result of
this XOR, giving us a trivially solvable equation (XORing the processed plaintext, and the ciphertext will then
reveal the key). For this reason, we'll need to analyze at least a 2-round variant.
But first thing's first: the bias table. Since this is a 64 × 64 table, I can't show all of it. Instead, Table 6-3
shows a small portion of the linear expression values.
Table 6-3 A Small Part of the Complete 64 × 64 Linear Expression Bias Table for the EASY1 S-Box