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

Note that other S-boxes have no input difference and, therefore, no output difference.
We now have built a characteristic for the entire three-round cipher, starting with two input bits and affecting
one intermediate output bit some of the time. We can use this model to derive six of the 18 key bits by selecting
a set of plaintext pairs, with their difference being the input differential used to develop the model. Measuring
the resulting change in the ciphertext pairs will enable us to find a portion of the key. When the ciphertext pairs
yield the expected differential, they form what is called a rightpair of plaintext-ciphertexts. (Obviously, plain-
text-ciphertext pairs that do not exhibit the desired differentials are called wrong pairs .)
An important addition to the idea of building up characteristics is the idea of an iterative characteristic —
one whose input differential is the same as its output differential at some point. These are particularly useful be-
cause they can be chained together very easily to create the larger characteristics required for analyzing ciphers
with many rounds. I'll show some examples of these when we explore the differential cryptanalysis of DES in
Section 7.7.2, although it can apply to any kind of cipher.
7.5 Key Derivation
Justasinlinear cryptanalysis, wedesire tohave some number ofplaintext-ciphertext pairs todetermine the key.
However, because differential cryptanalysis is a chosen-plaintext technique, we need to be able to pick certain
plaintexts to make the technique work.
Specifically, we pick plaintexts in pairs with differences that are necessary for the characteristic we are test-
ing. In our EASY1 cipher, this difference is Ω P = 02 80 00 00 00 (bits 30 and 32). We obtain the cipher-
texts for both plaintexts and measure the difference in the output. However, in this case, we did not construct the
differential characteristic equation to relate the plaintext and the ciphertext: We relate the plaintext to the inputs
to the last set of S-boxes. We then brute-force the relevant bits of the key, mix the key bits with the ciphertext,
reverse the mixed bits through the S-boxes, and then attempt to perform a match on the output differential. We
increment a counter for each key whenever any plaintext/ciphertext pair matches our expected differential.
In general, we expect the correct key to exhibit the probability that we found during analysis. When running
the analysis, we obtain Table 7-4 of count values in a sample run.
Table 7-4 Results From Differential Cryptanalysis of the EASY1 Cipher
Note how entry 33 (since we start counting at 0), whose value is 87, stands out among the rest.
From Table 7-4 , we can note that the largest count is 87, corresponding to the entry for subkey 33 ( 100001 ).
The key used to generate the ciphertext was 555555555 , and we can confirm that the bits of subkey 33 match