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

Finally,thelastpartiskeyderivation.Afterthedifferentialshavebeentracedallthewaytothesecond-to-last
round, as before, we then have to ensure that this final differential only modifies the bits of the round function
that are affected by some subset of the key bits.
At this point, just as before, we take the two values ofthe ciphertext and runthem through the previous round
function. We will be brute-forcing the appropriate key portions of the round functions. The key value that gives
us the highest number of the expected characteristics will be our guess.
In the next sections, I'll show how to use these ideas on FEAL and DES.

7.7.1 Differential Cryptanalysis of FEAL
In this section, we will see how the differential cryptanalysis method can be applied to the FEAL block cipher I
introduced in Section 4.7. This technique was first presented in Reference [3].
To review, FEAL has a simple DES-like Feistel structure, with an S-box that uses a combination of integer
addition, the XOR operation, and bitshifting.
Note, however, that the S-boxes are slightly more complicated than they appear at first glance. They take a
16-bit input and give an 8-bit output. To combat this, consider the middle 16 bits of the f -function, denoted by
the equations

These can be regarded together as one S-box with a 16-bit input and 16-bit output, since their inputs are the
same. The distribution table for this ''super'' S-box has some very interesting properties. Notably, most of the
entries (98%) are 0. Furthermore, three of the entries hold with a probability of 1, for example:

Some interesting characteristics include iterative characteristics , those in which the input and output XOR
differentials are the same. These allow us to construct longer expressions with less complicated analysis. For
example, in FEAL, the following is a four-round iterative characteristic that holds with probability 2 −8 :

7.7.2 Differential Cryptanalysis of DES
At the time when differential cryptanalysis was developed, DES was in widespread use and was often the target
of many new techniques. The use of differential cryptanalysis against DES was first presented in Reference [2],
as one of the first uses of differential cryptanalysis, and with surprising results (see Table 7-5 ) .

Table 7-5 Differential Cryptanalysis Attack Against DES: Complexities for Different Numbers of Rounds [2]
ROUNDS COMPLEXITY OF ATTACK

2 4 4

2 8

6

2 16 8

2 26 9

2 35 10

2 36 11