Differential Cryptanalysis - Modern Cryptanalysis: Techniques for Advanced Code Breaking - page 170

amount of ciphertext with known plaintext values, but in addition have the ability to manipulate this plaintext!
This is a fairly tall order and is a bit less practical than a known-plaintext attack or a ciphertext-only attack.
Finally, we have the fact that to execute the attack at all, we must store a large number of plaintext-ciphertext
pairs. There are ways around this, in test scenarios at least, where we reverse the order that we do things. We
first generate a new plaintext-ciphertext pair, XOR the plaintext to obtain the resultant ciphertext, and then try
every possible subkey against it, incrementing their respective counts, as necessary. At the end of this compu-
tation, we can throw away the pairs and generate new ones. Thus, in some cases, we can mitigate this storage
problem.
Moreover, the improvements in time over exhaustive search represent a tremendous breakthrough, even con-
sidering the strenuous requirements to implement the improvements.
Although differential cryptanalysis has several drawbacks, the overall concept has had a powerful impact on
cryptanalysis. In the following sections, we examine some of the fundamental extensions of differential crypt-
analysis.
7.9 Differential-Linear Cryptanalysis
An interesting combination of the two important algorithms presented in the last two chapters, linear and dif-
ferential cryptanalysis , appeared in Reference [12], courtesy of Susan Langford and Martin Hellman.
The trick is to use a linear expression, developed in the way already shown, and to measure what changes
in the plaintext do to the value of that linear expression. In this way, we aren't simply brute-forcing the subkey
by calculating counts on the linear expression; rather, we are using carefully selected differentials that should
produce fixed, expected probabilities of the two linear expressions being XORed being equal to 0. As before,
we normally expect this to happen roughly half the time for any arbitrary linear expression and difference; thus,
any deviation from this can be used.
A good example that the authors show is using a three-round linear approximation for DES. A normal linear
expression proposed by Matsui is
This holds with a probability of either approximately 0.695 or 0.305.
The differential attack comes from noting that we can toggle bits 29 or 30 (or both) of the L 1 value, and this
will produce no changes in the fourth-round linear approximation. This means, at this point, that our linear ap-
proximations XORed together have a probability of 1 of occurring.
Carrying this out to an eight-round approximation, the probability of the linear expression XOR becomes
We add the numbers together since we could either be right twice in a row or wrong with our expression twice
in a row, and we can't really tell the difference. As the authors of the paper say, two wrongs make a right in
binary arithmetic.
This means we have a bias of 0.076, giving us an approximate number of plaintext-ciphertext pairs:
We can even pull another trick to reduce this number further.
Since we still have to get bits 29 and 30 to toggle in L 1 , we will naturally have to toggle bits in the plaintext
( L 0 and R 0 ). Toggling the same two bits in R 0 will perform this.