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

6.4 Matsui's Piling-up Lemma
Now that we have linear expressions for S-boxes, how do we combine them to perform linear cryptanalysis, and
what kinds of results will we get? The simple answer is that we trace the output bits of one S-box to be the input
values of other S-boxes, repeating until we have an expression relating only plaintext bits, ciphertext bits, and
key bits.
But what happens when they combine? With more rounds, the biases of the overall expression are going to
change, but how? Our natural inclination is that the biases will be multiplicative — meaning that an expres-
sion's bias of 1/4, when combined with another linear expression of bias 1/3 (lining up their inputs and outputs
appropriately) would be 1/4 × 1/3 = 1/12. This is approximately what happens, but not quite.
Matsui shows that the linear expressions “pile up” in a different sort of way [4].
Piling-up Lemma
Assume that we have n independent linear expressions, say, X 1 , X 2 , ... , X n , with associated biases ε 1 , ε 2 , ... , ε n .
We also need to assume that they are random, as we have no real preconceptions of their values, and binary, in
that they output 0 or 1. Then, the bias of an aggregate binary, linear expression,
is the expression
(where ε 1,2, ... , n is the new bias). Remember that this bias is relative to 1/2, meaning that the probability of it
happening is 1/2 plus the bias.
Matsui's piling-up lemma can be easily proven by mathematical induction, with the assumption that each
linear expression is independent. It isn't necessary to go into the full proof here — I refer the interested reader
to Reference [4].
Since the underlying expressions will not have probabilities of 100 percent or 0 percent, we cannot construct
completely exact and precise linear expressions. Instead, we try to construct expressions that are true as often
(or as seldom)as possible; hence, we often call these expressions approximations. Matsui's piling-up lemma
provides us with a means of determining how good our approximation is (if it has a very large bias, either pos-
itive or negative).
6.5 EASY1 Cipher
Now let's return our attention to the slimmed-down, simple cipher called EASY1 introduced above.
EveryportionofthecipherwillusethesameS-box,althoughlinearcryptanalysisworksquitewellregardless
of the variety and number of S-boxes used. We keep it to one S-box to make the analysis a little easier. To reit-
erate, our S-box is represented as
[16, 42, 28, 3, 26, 0, 31, 46, 27, 14, 49, 62, 37, 56, 23, 6, 40, 48,
53, 8,
20, 25, 33, 1, 2, 63, 15, 34, 55, 21, 39, 57, 54, 45, 47, 13, 7, 44,
61, 9, 60,