![]() |
|
|||
![]() |
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
![]() |
|
![]() |
[an error occurred while processing this directive]
3.6 Differential CryptanalysisOne 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 DEFINITION 3.1 Let Sj be a particular S-box (1 ≤ j ≤ 8). Consider an (ordered) pair of bitstrings of length six, say 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 It is easy to see that any set For each pair in 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 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 and
Observe that the distribution tabulated in Example 3.1 consists of the values 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 = E ⊕ J, 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 where Suppose we define a set testj as follows: DEFINITION 3.4 Suppose Ej and 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 Observe that there will be exactly Example 3.2 Suppose Hence, If we have a second such triple 3.6.1 An Attack on a 3-round DESLets 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:
Now, suppose we have chosen the plaintexts so that
Then At this point, Now, f(R2, K3) = P(C) and and consequently This is the output x-or for the eight S-boxes in round three. Now, R2 = L3 and 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. Lets look at an example to illustrate.
Copyright © CRC Press LLC
![]() |
![]() |
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
![]() |
![]() |