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

This equation holds because the input to the function is the plaintext ( L 0 ) and the linear expression output of the
function must match up with the appropriate portion of the round values.
We can do a very similar calculation to obtain a linear expression for the third round. It turns out that, since
we are using the same equation to derive it, the R 1 portion drops out, leaving us with known values and the key
bits on the right-hand side. If we were analyzing a three-round variant of DES, we would then use Matsui's Al-
gorithm 1 to start deriving information about the key bits at this point (which I omit since it will not add much
to our discussion).
However, we are more concerned with breaking the full cipher. In essence, we simply obtain an expression
for the cipher, being one round short of the full cipher (as done above with EASY1). We engineer it so that the
final round of calculation depends on only a subset of all of the bits involved in the final round key.
Matsui gives us the following 15-round linear expression to attack the full 16 rounds of DES:
Here, we omit all of the key bits on the right-hand side for Matsui's Algorithm 2 (since we don't use them to
derive any key information). Also, note that F 16 depends on the 48-bit subkey K 16 . However, only 6 bits of the
subkey are used to calculate bit 15, so we can brute-force those bits.
We do get one advantage (among the increased complexity) in attacking a Feistel structure: There is very
little difference between using the above 15-round approximation and deriving six key bits on the last round and
doing a very similar calculation for a 15-round approximation, but working backwards, and using the approx-
imation for the last 15 rounds rather than the first. This way, we can also, independently, brute-force the bits of
K 1 , and we double our key bits.
Matsui claims that this method allows us to derive 14 key bits of a 56-bit DES key, by using 2 47 known plain-
texts [4]. Note that this isn't an awfully big improvement over brute-force guessing of the entire key; we still
have to brute-force a 6-bit key (twice); our running time would be on the order of 2 54 .
Afterthecalculation ofthe14keybitsisdone,it'snotrelatively time-consuming totake oneoftheplaintexts
and brute-force the other 42 key bits until the correct ciphertext comes out. This technique is definitely better
than the normal time of 2 56 required to brute-force the DES key.
Matsui later came to improve even further on this method [3]. By backing off a little and using a 14-round
linearapproximation,itispossibletorequireevenfewerknownplaintextswithevenmoreaccuracythanbefore.
Using his improved method, DES is breakable with an 85 percent success rate using 2 43 known plaintexts and a
running time of about 2 43 .
6.8 Multiple Linear Approximations
There are two clear ways to make linear cryptanalysis more powerful: collecting more plaintext-ciphertext
pairs, or using more linear expressions with the same plaintext-ciphertext pairs. The technique of multiple lin-
ear approximations focuses on this second technique, introduced in Reference [2].
This concept can be used with Matsui's Algorithm 1 or Algorithm 2, using the idea that rather than requiring
more plaintext-ciphertext pairs, we should attempt to use several linear approximations at each step. This, in
turn, makes the linear expressions have a lower variance, which can either make the results more accurate or
allow us to use fewer plaintext-ciphertext pairs with the same accuracy.
In normal linear cryptanalysis, we are looking at equations of the form