A differential attack on xDES 2

In this section we considerxDES² which has a 560 bit key working on 256 bit blocks. xDES² can be seen as two five round Feistel ciphers, where in each of the ten rounds the DES is used as the f-function and where the outputs of each round are mixed, see Figure 6.3. In [115] it is assumed that all ten 56 bit round keys are independent and noted that any secure block cipher may be used instead of DES. We will assume in the following that the DES is used.

The 256 bit plaintext is divided into four block of 64 bits each,c_0,1, c_0,2, c_0,3,

6.5. XDES^I 141

Figure 6.3: One round of xDES²

and c_0,4. In general the computation of the ciphertext is as follows.

c_i,1 = c_i−1,4

c_i,2 = c_i−1,1 ⊕DES_Ki,1(c_i−1,2) c_i,3 = c_i−1,2

c_i,4 = c_i−1,3 ⊕DES_Ki,2(c_i−1,4)

where K_i,1 and K_i,2 for i = 1, . . . ,5 are ten 56 bit round keys. After five rounds of encryption the ciphertext is defined as the concatenation of c_5,4, c_5,3, c_5,2, and c_5,1. Note that the final permutation of these ciphertext blocks is not the same as the permutation of the four intermediate cipher-text blocks in the round function. The final permutation of the ciphercipher-text block has no influence on our attacks, so in the following we will assume that permutation of blocks are the same in all rounds. We can prove the following result.

Theorem 6.5.2 There exists an attack on xDES², which on input about 2³³ known plaintext finds the secret 560 bit key in time O(2⁶⁴).

Proof: First we describe a chosen plaintext attack. We define the following characteristic ∆P = (0|0|Γ|Φ) for some values of Γ and Φ. If a difference Φ in the inputs to the rightmost DES-encryption of Figure 6.3 lead to out-puts with difference Γ in the first round, the difference ∆C_i =c_i⊕c_i in the values c_i = (c_i,1 |c_i,2 |c_i,3 |c_i,4) and c_i = (c_i,1 |c_i,2 |c_i,3 |c_i,4) for i= 0, . . . ,5

142 CHAPTER 6. ANALYSIS OF SPECIFIC BLOCK CIPHERS of the two encryptions are depicted in Table 6.14 where for i= 1, . . . ,4, X_i are values we cannot predict. The attack now proceeds as follows

∆C₀ = 0 | 0 | Γ | Φ

∆C₁ = Φ | 0 | 0 | 0

∆C₂ = 0 | Φ | 0 | 0

∆C₃ = 0 | X₁ | Φ | 0

∆C₄ = 0 | X₂ | X₁ | Φ

∆C₅ = Φ | X₃ | X₂ | X₄

Table 6.14: A five round characteristic for xDES².

1. Choose a plaintext pair with the desired difference ∆P = (0|0|Γ|Φ).

2. Get the corresponding encryptions in a chosen plaintext attack.

3. If the difference of the leftmost 64 bit ciphertext blocks c_5,1 is Φ, try for all possible values of the key K_1,2 if the encryptions of the two corresponding 64 bit plaintext blocksc_0,4 yield a difference Γ and store the keys for which that holds.

4. If the difference of the leftmost 64 bit ciphertext blocks c_5,1 is not Φ, go to step 1.

In all pairs of plaintexts we choose the same values in the fourth plaintext blocks with difference Φ. Since there are 2⁶⁴ possible values of the exclusive-or of the outputs of the rightmost DES encryption, we let the third plaintext blocks run through all possibilities, i.e., the input differences we use are

∆P_i = (0 | 0 | Γ_i | Φ) for i = 0, . . . ,2⁶⁴−1. After 2⁶⁴ trials with different pairs of plaintext blocks, we are guaranteed that for at least one pair the condition for an exhaustive search in step 3 will be true and we will find the right value of K_1,2. Also we will get wrong pairs that by accident hit the difference Φ in leftmost ciphertext blocks, but by repeating the attack a few times, only the right key value of K_1,2 will be left suggested. Also we can use the knowledge in ∆C₄ above to search for the key K_5,1. For a pair satisfying the condition in step 3 it holds that encryptions of the ciphertext blocks with differenceX₂ yield a difference of X₃ after encryption with K_5,1, since the xor’ed difference from the fourth round is zero. Also we can use a

6.5. XDES^I 143 similar characteristic to attack the leftmost DES encryption in the first round and find K_1,1 and K_5,2 in a similar way as above. Then we can decrypt all ciphertexts one round and repeat the attack on a 4-round version of xDES², where our probability of success will be higher.

As shown by Matsui [67] the best characteristic for an attack on the DES is the concatenation of the 2-round iterative characteristic. For the full 16-round DES this characteristic will have an average probability of (₂₃₄¹ )⁸ 2⁻⁶³. Using this characteristic we fix the values for Φ and Γ above iId we need to try about 2⁶³ pairs of plaintexts to get one right pair. How-ever, we can do better than that. We assume that for a random pair of plaintexts, the output difference is distributed uniformly for the DES. That seems a reasonable assumption in general for a good block cipher, and espe-cially for the DES, where only two characteristics have a probability below the trivial one of 2⁻⁶⁴. Therefore for a randomly chosen pair of plaintexts the probability that the condition in step 3 is satisfied is about 2⁻⁶⁴. In a collection of 2³² plaintexts we can form about 2⁶⁴ pairs of plaintexts and with a high probability we get at least one right pair. We note that, first of all, these characteristics are dependent in some way and the success of some characteristic may depend on the success of other characteristics and secondly, since the DES with a fixed key is a permutation, pairs with Γ = 0 will never be a right pair. However, by using more plaintexts, i.e., 2³³ or 2³⁴,

we can expect to get a right pair. ✷

Finally we note that our attacks can also be applied whenxDES² is used with dependent round keys.

For i ≥ 3, xDESⁱ is probably too big for the cipher to be a serious candidate-for a block cipher. As an example, for i = 3 the block size is 384 bits and the key size is 1176 bits and 21 encryptions of the DES are needed to encrypt one block of size six times a DES block.

144 CHAPTER 6. ANALYSIS OF SPECIFIC BLOCK CIPHERS

Chapter 7

Design of Block Ciphers

In this chapter we discuss some of the problems involved in the design of a block cipher. In Section 7.1 the danger of focusing solely on a few design criteria is discussed and a set of necessary design principles is listed. In Section 7.2 we discuss the block and key sizes in block ciphers. In Section 7.3 it is shown how to obtain provable security against a differential attack.

In Section 7.4 the Markov theory for block ciphers is considered and it is shown that with a high probability all iterated block ciphers will be resistant against differential attacks after sufficiently many rounds. In Section 7.5 it is shown how to obtain provable security against a linear attack. In Section 7.7 we define and show how to build strong key schedules. In Section 7.8 we give a new test for checking the nonlinear order of a block cipher. Finally in Section 7.9 multiple encryption of a block cipher is considered. We give a new proposal for a triple encryption scheme, which under reasonable assumptions is as secure as the underlying scheme though requiring only a minimum number of component keys.

7.1 Design Principles

Two generally accepted design principles for practical ciphers are the princi-ples of confusion and diffusion that were suggested by Shannon. In his own words: “The method of confusion is to make the relation between the simple statistics of the ciphertext and the simple description of the key a very

com-145

146 CHAPTER 7. DESIGN OF BLOCK CIPHERS 1. Confusion

2. Diffusion

3. Sufficiently large block size 4. Sufficiently large key size

5. Resistance against known attacks (a) - differential attacks

(b) - linear attacks 6. All keys are equally good 7. No simple relations 8. High nonlinear order

Table 7.1: Special design principles for block ciphers.

plex and involved one” [107].

“In the method of diffusion the statistical structure of the plaintext which leads to its redundancy is dissipated into long range statistics” [107]. Massey [63] interprets Shannon’s concepts of confusion and diffusion as follows

Confusion

The ciphertext statistics should depend on the plaintext statistics in a manner too complicated to be exploited by the cryptanalyst.

Diffusion

Each digit of the plaintext and each digit of the secret key should influence many digits of the ciphertext.

Shannon’s design principles are very general and informal. There have been many suggestions in the past of how to obtain good properties (diffusion/

confusion) for a block cipher, but so far there is no known exact recipe of how to construct a secure block cipher. A necessary and obvious requirement is that the cipher is resistant against all known attacks. In Table 7.1 we list

7.2. SUFFICIENTLY LARGE BLOCK AND KEY SIZE 147 more specific design principles for the design of block ciphers. We stress that a cryptographic design principle should not be over-interpreted. Design prin-ciples should be seen as “guidelines” in the construction of ciphers, evolved from years of experience, and as necessary, but not sufficient requirements.

There are many examples of this in the history of cryptography. We give a few of the most recent examples.

Consider SP (substitution-permutation)-networks, product ciphers, where the ciphertext is computed from the plaintext by applying in turn (key-dependent) substitutions and permutations to the plaintexts. The DES can be seen as a special implementation of a SP-network. In [41] a method of constructing SP-networks is given, where for every key all ciphertext bits depend on all plaintext bits. However, this fact is information that an at-tacker can exploit. In [88] O’Connor describes a differential attack on the SP-networks of [41] using a number of chosen plaintexts linear in the number of S-boxes in the network.

In [62] the group properties of a cryptosystem based on permutation groups were studied. It was claimed that the ability of a system to generate the symmetric group on the message space is “one of the strongest security conditions that can be offered”. In [81] an example of a cipher was given, that generates the symmetric group, but still is a weak cipher vulnerable to a known plaintext at tack.