This section is rather technical and can be skipped on a first reading.
Differential cryptanalysis was introduced by Biham and Shamir around 1990, though it was probably known much earlier to the designers of DES at IBM and NSA. The idea is to compare the differences in the ciphertexts for suitably chosen pairs of plaintexts and thereby deduce information about the key. Note that the difference of two strings of bits can be found by XORing them. Because the key is introduced by XORing with , looking at the XOR of the inputs removes the effect of the key at this stage and hence removes some of the randomness introduced by the key. We’ll see that this allows us to deduce information as to what the key could be.
We eventually want to describe how to attack the above system when it uses four rounds, but we need to start by analyzing three rounds. Therefore, we temporarily start with instead of .
The situation is now as follows. We have obtained access to a three-round encryption device that uses the preceding procedure. We know all the inner workings of the encryption algorithm such as the S-boxes, but we do not know the key. We want to find the key by a chosen plaintext attack. We use various inputs and obtain outputs .
We have
Suppose we have another message with . For each , let and . Then is the “difference” (or sum; we are working mod 2) of and . The preceding calculation applied to yields a formula for . Since we have assumed that , we have . Therefore, and
This may be rearranged to
Finally, since and , we obtain
Note that if we know the input XOR, namely , and if we know the outputs and , then we know everything in this last equation except .
Now let’s analyze the inputs to the S-boxes used to calculate and . If we start with , we first expand and then XOR with to obtain , which are the bits sent to and . Similarly, yields . The XOR of these is
(the first equality follows easily from the bit-by-bit description of the expansion function). Therefore, we know
the XORs of the inputs to the two S-boxes (namely, the first four and the last four bits of );
the XORs of the two outputs (namely, the first three and the last three bits of ).
Let’s restrict our attention to . The analysis for will be similar. It is fairly fast to run through all pairs of four-bit inputs with a given XOR (there are only 16 of them) and see which ones give a desired output XOR. These can be computed once for all and stored in a table.
For example, suppose we have input XOR equal to 1011 and we are looking for output XOR equal to 100. We can run through the input pairs (1011, 0000), (1010, 0001), (1001, 0010), ..., each of which has XOR equal to 1011, and look at the output XORs. We find that the pairs (1010, 0001) and (0001, 1010) both produce output XORs 100. For example, 1010 means we look at the second row, third column of , which is 110. Moreover, 0001 means we look at the first row, second column, which is 010. The output XOR is therefore .
We know and . For example, suppose and . Therefore, and , so the inputs to are and , where denotes the left four bits of . If we know that the output XOR for is 100, then must be one of the pairs on the list we just calculated, namely (1010, 0001) and (0001, 1010). This means that or 1010.
If we repeat this procedure a few more times, we should be able to eliminate one of the two choices for and hence determine four bits of . Similarly, using , we find four more bits of . We therefore know eight of the nine bits of . The last bit can be found by trying both possibilities and seeing which one produces the same encryptions as the machine we are attacking.
Here is a summary of the procedure (for notational convenience, we describe it with both S-boxes used simultaneously, though in the examples we work with the S-boxes separately):
Look at the list of pairs with input and output .
The pair is on this list.
Deduce the possibilities for .
Repeat until only one possibility for remains.
We start with
and the machine encrypts in three rounds using the key , though we do not yet know . We obtain (note that since we are starting with , we start with the shifted key )
If we start with
(note that ), then
We have and . The inputs to have XOR equal to 1010 and the inputs to have XOR equal to 1011. The S-boxes have output XOR , so the output XOR from is 010 and that from is 100.
For the pairs , produces output XOR equal to 010. Since the first member of one of these pairs should be the left four bits of , the first four bits of are in . For the pairs , produces output XOR equal to 100. Since the first member of one of these pairs should be the right four bits of , the last four bits of are in .
Now repeat (with the same machine and the same key ) and with
A similar analysis shows that the first four bits of are in and the last four bits are in . Combining this with the previous information, we see that the first four bits of are 0011 and the last four bits are 0100. Therefore, (recall that starts with the fourth bit of .
It remains to find the third bit of . If we use , it encrypts to 001011101010, which is not , while yields the correct encryption. Therefore, the key is .
Suppose now that we have obtained access to a four-round device. Again, we know all the inner workings of the algorithm except the key, and we want to determine the key. The analysis we used for three rounds still applies, but to extend it to four rounds we need to use more probabilistic techniques.
There is a weakness in the box . If we look at the 16 input pairs with XOR equal to 0011, we discover that 12 of them have output XOR equal to 011. Of course, we expect on the average that two pairs should yield a given output XOR, so the present case is rather extreme. A little variation is to be expected; we’ll see that this large variation makes it easy to find the key.
There is a similar weakness in , though not quite as extreme. Among the 16 input pairs with XOR equal to 1100, there are eight with output XOR equal to 010.
Suppose now that we start with randomly chosen and such that . This is expanded to . Therefore the input XOR for is 0011 and the input XOR for is 1100. With probability 12/16 the output XOR for will be 011, and with probability 8/16 the output XOR for will be 010. If we assume the outputs of the two S-boxes are independent, we see that the combined output XOR will be 011010 with probability (12/16)(8/16) = 3/8. Because the expansion function sends bits 3 and 4 to both and , the two boxes cannot be assumed to have independent outputs, but 3/8 should still be a reasonable estimate for what happens.
Now suppose we choose and so that . Recall that in the encryption algorithm the output of the S-boxes is XORed with to obtain . Suppose the output XOR of the S-boxes is 011010. Then . Since , it follows that
Putting everything together, we see that if we start with two randomly chosen messages with XOR equal to , then there is a probability of around 3/8 that .
Here’s the strategy for finding the key. Try several randomly chosen pairs of inputs with XOR equal to 011010001100. Look at the outputs and . Assume that . Then use three-round differential cryptanalysis with and the known outputs to deduce a set of possible keys . When , which should happen around 3/8 of the time, this list of keys will contain , along with some other random keys. The remaining 5/8 of the time, the list should contain random keys. Since there seems to be no reason that any incorrect key should appear frequently, the correct key will probably appear in the lists of keys more often than the other keys.
Here is an example. Suppose we are attacking a four-round device. We try one hundred random pairs of inputs and . The frequencies of possible keys we obtain are in the following table. We find it easier to look at the first four bits and the last four bits of separately.
It is therefore likely that . Therefore, the key is 10*110000.
To determine the remaining bit, we proceed as before. We can compute that 000000000000 is encrypted to 100011001011 using and is encrypted to 001011011010 using . If the machine we are attacking encrypts 000000000000 to 100011001011, we conclude that the second key cannot be correct, so the correct key is probably .
The preceding attack can be extended to more rounds by extensions of these methods. It might be noticed that we could have obtained the key at least as quickly by simply running through all possibilities for the key. That is certainly true in this simple model. However, in more elaborate systems such as DES, differential cryptanalytic techniques are much more efficient than exhaustive searching through all keys, at least until the number of rounds becomes fairly large. In particular, the reason that DES uses 16 rounds appears to be because differential cryptanalysis is more efficient than exhaustive search until 16 rounds are used.
There is another attack on DES, called linear cryptanalysis, that was developed by Mitsuru Matsui [Matsui]. The main ingredient is an approximation of DES by a linear function of the input bits. It is theoretically faster than an exhaustive search for the key and requires around plaintext–ciphertext pairs to find the key. It seems that the designers of DES had not anticipated linear cryptanalysis. For details of the method, see [Matsui].