Cryptography: Theory and Practice:The Data Encryption Standard

cryptography: theory and practice Cryptography: Theory and Practice
by Douglas Stinson
CRC Press, CRC Press LLC
ISBN: 0849385210   Pub Date: 03/17/95
  

Previous Table of Contents Next


3.6 Differential Cryptanalysis

One very well-known attack on DES is the method of “differential cryptanalysis” introduced by Biham and Shamir. This is a chosen-plaintext attack. Although it does not provide a practical method of breaking the usual 16-round DES, it does succeed in breaking DES if the number of rounds of encryption is reduced. For instance, 8-round DES can be broken in only a couple of minutes on a small personal computer.

We will now describe the basic ideas used in this technique. For the purposes of this attack, we can ignore the initial permutation IP and its inverse (it has no effect on cryptanalysis). As mentioned above, we consider DES restricted to n rounds, for various values of n ≤ 16. So, in this setting, we will regard L0R0 as the plaintext, and LnRn as the ciphertext, in an n-round DES. (Note also that we are not inverting LnRn.)

Differential cryptanalysis involves comparing the x-or (exclusive-or) of two plaintexts to the x-or of the corresponding two ciphertexts. In general, we will be looking at two plaintexts L0R0 and with a specified x-or value . Throughout this discussion, we will use prime markings (′) to indicate the x-or of two bitstrings.

DEFINITION 3.1  Let Sj be a particular S-box (1 ≤ j ≤ 8). Consider an (ordered) pair of bitstrings of length six, say . We say that the input x-or (of Sj) is and the output x-or (of Sj) is .

Note that an input x-or is a bitstring of length six and an output x-or is a bitstring of length four.

DEFINITION 3.2  For any , define the set to consist of the ordered pairs having input x-or .

It is easy to see that any set contains 26 = 64 pairs, and that

For each pair in , we can compute the output x-or of Sj and tabulate the resulting distribution. There are 64 output x-ors, which are distributed among 24 = 16 possible values. The non-uniformity of these distributions will be the basis for the attack.

Example 3.1

Suppose we consider the first S-box, S1, and the input x-or 110100. Then

For each ordered pair in the set Δ(110100), we compute output x-or of S1. For example, S1(000000) = E16 = 1110 and S1(110100) = 916 = 1001, so the output x-or for the pair (000000, 110100) is 0111.

If this is done for all 64 pairs in Δ(110100), then the following distribution of output x-ors is obtained:

In Example 3.1, only eight of the 16 possible output x-ors actually occur. This particular example has a very non-uniform distribution. In general, if we fix an S-box Sj and an input x-or , then on average, it turns out that about 75 - 80% of the possible output x-ors actually occur.

It will be convenient to have some notation to describe these distributions and how they arise, so we make the following definitions.

DEFINITION 3.3  For 1 ≤ j ≤ 8, and for bitstrings of length six and of length four, define

and


Figure 3.8  Possible inputs with input x-or 110100

counts the number of pairs with input x-or equal to which have output x-or equal to for the S-box Sj. The actual pairs having the specified input x-ors and giving rise to the specified output x-ors can be obtained from the set . Observe that this set can be partitioned into pairs, each of which has (input) x-or equal to .

Observe that the distribution tabulated in Example 3.1 consists of the values . The sets are listed in Figure 3.8.

For each of the eight S-boxes, there are 64 possible input x-ors. Thus, there are 512 distributions which can be computed. These could easily be tabulated by computer.

Recall that the input to the S-boxes in round i is formed as B = EJ, where E = E(Ri-1) is the expansion of Ri-1 and J = Ki consists of the key bits for round i. Now, the input x-or (for all eight S-boxes) can be computed as follows:

It is very important to observe that the input x-or does not depend on the key bits J. (However, the output x-or certainly does depend on these key bits.)

We will write each of B, E and J as the concatenation of eight 6-bit strings:

and we write B* and E* in a similar way. Let us suppose for the moment that we know the values Ej and for some j, 1 ≤ j ≤ 8, and the value of the output x-or for . Then it must be the case that

where .

Suppose we define a set testj as follows:

DEFINITION 3.4  Suppose Ej and are bitstrings of length six, and is a bitstring of length four. Define

where .

That is, we take the x-or of Ej with every element of the set .

The following result is an immediate consequence of the discussion above.

THEOREM 3.1

Suppose Ej and are two inputs to the S-box Sj, and the output x-or for Sj is . Denote . Then the key bits Jj occur in the set testj .

Observe that there will be exactly bitstrings of length six in the set testj ; the correct value of Jj must be one of these possibilities.

Example 3.2

Suppose . Since N1 (110100, 1101) = 8, there will be exactly eight bitstrings in the set test1 (000001, 110101, 1101). From Figure 3.8, we see that

Hence,

If we have a second such triple , then we can obtain a second set test1 of possible values for the keybits in J1. The true value of J1 must be in the intersection of both sets. If we have several such triples, then we can quickly determine the key bits in J1. One straightforward way to do this is to maintain an array of 64 counters, representing the 64 possibilities for the six key bits in J1. A counter is incremented every time the corresponding key bits occur in a set test1 for a particular triple. Given t triples, we hope to find a unique counter which has the value t; this will correspond to the true value of the keybits in J1.

3.6.1 An Attack on a 3-round DES

Let’s now see how the ideas of the previous section can be applied in a chosen plaintext attack of a 3-round DES. We will begin with a pair of plaintexts and corresponding ciphertexts: and . We can express R3 as follows:

can be expressed in a similar way, and hence

Now, suppose we have chosen the plaintexts so that , i.e., so that


Figure 3.9  Differential attack on 3-round DES

Then and so

At this point, is known since it can be computed from the two ciphertexts, and is known since it can be computed from the two plaintexts. This means that we can compute from the equation

Now, f(R2, K3) = P(C) and , where C and C*, respectively, denote the two outputs of the eight S-boxes (recall that P is a fixed, publicly known permutation). Hence,

and consequently

This is the output x-or for the eight S-boxes in round three.

Now, R2 = L3 and are also known (they are part of the ciphertexts). Hence, we can compute

and

using the publicly known expansion function E. These are the inputs to the S-boxes for round three. So, we now know E, E*, and C′ for the third round, and we can proceed, as in the previous section, to construct the sets test1, . . ., test8 of possible values for the key bits in J1, . . . , J8.

A pseudo-code description of this algorithm is given in Figure 3.9. The attack will use several such triples E, E*, C′. We set up eight arrays of counters, and thereby determine the 48 bits in K3, the key for the third round. The 56 bits in the key can then be computed by an exhaustive search of the 28 = 256 possibilities for the remaining eight key bits.

Let’s look at an example to illustrate.


Previous Table of Contents Next

Copyright © CRC Press LLC



Cryptography. Theory and Practice
Modern Cryptography: Theory and Practice
ISBN: 0130669431
EAN: 2147483647
Year: 1995
Pages: 133
Authors: Wenbo Mao

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net