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

So far, we know well what the term cryptanalysis means. The “linear” in linear cryptanalysis stems from the
fact that we want to manipulate and solve linear binary equations . For linear binary equations, this means the
equations looks like
Because of the commutativity of the XOR operator, this equation is the same as
(obtained by taking the previous equation and XORing Z to both sides).
These binary equations will be built to relate the inputs and outputs of various portions of the ciphers. For
example, we might wish to have an equation of two input bits of a round input — X 0 and X 2 — with three output
bits of a round — Y 1 , Y 2 , and Y 4 — which would look like
This equation will most likely not be true all the time, but some of the time. We will generate many such equa-
tions, and eventually, we will use these relations to build up a linear “approximation” of the entire cipher, where
the final input bits and output bits will consist of the key, plaintext, and ciphertext. The more accurate the ap-
proximation, the less work we will have to do to figure out the key.
One quick note: The equations don't quite work out if we have an expression equal to 1 (instead of 0), such
as
Technically speaking, this is not a linear equation, but an affine equation (since it uses a nonzero constant).
Sometimes people refer to these equations as “parity” equations, since parity is the sum of all of the bits of
a number, and we are interested in the parities for the left-hand side and the right-hand side to match.
The linear cryptanalysis method models the cipher as a linear equation, similar to the ones above, using bits
of the plaintext, ciphertext, and key as the variables in the equation. For most ciphers, the ciphertext is suffi-
ciently random-looking, with regard to the plaintext, so that any arbitrary linear expression should be true about
half the time. For example, when we examine any one of the ciphertext bits, we should see that the bit is 0 half
of the time and 1 the other half of the time.
Linear cryptanalysis attempts to find expressions that aren't quite as random: The probability of getting a 0
or 1 isn't quite 1/2. As we find expressions with probabilities farther from 1/2, the success rate of determining
the key from these expressions goes up.
6.2 Matsui's Algorithms
Matsui proposes two algorithms for linear cryptanalysis, although only one is regularly used.
Assume that we have some equation involving bits of plaintext, ciphertext, and a key, such as
(although we haven't discussed how to obtain such a representation).
Assuming the bits have good diffusion and confusion characteristics, this equation is true fairly randomly
and unpredictably, that is, happening about half of the time. When the events have probability different from
1/2, we say that this difference is a bias . If p is the probability that the above is true, then | p - 1/2| is the bias —
that is, the difference between p and 1/2, ignoring the sign of the result (the absolute value).