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

Figure 6-3 A simple linear expression for two rounds of EASY1 (ignore the influence of the key bits at this
point).
Using the piling-up lemma, we can make the following deductions.
Take ε 1 = −4/32 ≈ −0.125, which is the bias for the S-box expression X 0 ⊕ Y 4 = 0. The same bias will apply
for the next round's bias (ε 2 ).
Since Y 4 is mapped to X 0 in the next round, let's differentiate the rounds with superscripts. Thus, the first
round's equation is , whereas the second round's equation is .
We can then combine the two equations, knowing that = , by XORing the two equations to-
gether (where the common terms XOR and cancel each other out), obtaining
The bias for this is obtained using the piling-up lemma. We know that ε 1 = ε 2 = −4/32; thus, the combined bias
(say, ε 1,2 ) is obtained from
Figure 6-3 shows a representation of this expression.
Matsui claims that, in theory, to get a decent guess at the key bits, we will need to have on the order of 8ε -2
plaintext-ciphertext pairs. In the case above, with a bias of 2 -7 , we would need about 8(2 -7 ) -2 = 2 17 = 131,072
plaintext-ciphertext pairs. This large number of pairs shows us that this expression is not very good — since
there are only 2 18 keys possible, we are doing almost the same amount of work as brute-force. Furthermore, this
is only for a two-round variant of the cipher: More likely, we will have more rounds, and therefore the bias for
our expression will keep getting worse.