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

Assuming a known-plaintext attack, we would know several values of the P and C bits, and we would be
looking for the K bits. Matsui's “Algorithm 1” uses the above equation, along with its bias, to get us a single bit
of information about the key itself.
This algorithm, and the next, both use the principle of maximum likelihood : If it's the most probable (or
one of the most probable) causes, then assume it is the correct cause.
Matsui's Algorithm 1
Assume that we have a linear expression of the form:
Also, we must know the probability, p, of this equation holding true.
1. Collect many valid plaintext-ciphertext pairs for a particular key (the amount of which to be determin-
ed by the probability of the equation, specified below).
2. For each plaintext-ciphertext pair, calculate the left side of the above linear expression. Let T be the
number of times the left side is equal to 0.
3. If T is more than half of the pairs and p is greater than 1/2, then we guess that the right side (the K bits
XORed) is 0.
4. If T is less than half of the pairs and p is less than 1/2, then we also guess 0 for the XOR of the K bits.
5. Otherwise, guess that the XOR of the K bits must be 1.
These last three steps are there because we are assuming that our bias and probability are accurate, meaning
that if p is less than 1/2, we expect that the equation is usually false, and if p is greater than 1/2, then the equa-
tion is usually true, which would require the above scenarios to work out, for example, since if we expect it to
be false and the left side is 0, then the right side must be 1 so that the whole equation is false, and so forth.
This algorithm doesn't offer a whole lot: We get a small amount of information for some collection of plain-
text-ciphertext pairs. If we had a large collection of plaintext-ciphertext pairs as well as several such equations
with large biases, then we might be able to construct a set of equations of key bits, which could possibly be used
to derive the key bits themselves.
This isn't always practical. For most good ciphers, the biases for the full cipher will usually be very small (in
that any linear expression will usually be true close to half the time). Luckily, Matsui issued another algorithm
for extracting key bits, which relies on, potentially, only a single number of linear expressions, but a large num-
ber of plaintext-ciphertext pairs.
The idea is to have another equation, similar to the one above. However, instead of counting how many times
the left-hand side is true, we will try every value of the K bits and count how many times the overall equation is
true.
Matsui's Algorithm 2
Assume we have a linear expression of the form:
Also, we must know the probability of this equation holding true, p.
1. Collect a large number of plaintext-ciphertext pairs for a single key that we wish to obtain (again, de-
pending on the probability of the equation).