Attacks using higher order differentials

5.2.5 Attacks using higher order differentials

We consider in the following DES-like iterated block ciphers with block size of log₂ p², where pis a prime. The plaintext block is divided into two halves L and R each of a size log₂ p. Each round takes a text input of size log₂ p² and a round key of size log₂ p. We assume that there is no expansion of the text input to the F-function. One also calls the functionF, the round func-tion. In this section we adopt this convention for convenience, since it should cause no confusion. In the attacks we are going to present the complexity is measured as the number of encryptions of the analysed cipher, that the attacker has to perform for success.

Theorem 5.2.3Let f(x, k) = (x+k)²modp,pprime, be the round function in a DES-like iterated cipher of block size log₂ p²,where ‘+’ is addition mod-ule p. Then every non-trivial one round differential of f has a probability of 1/p. Secondly, the second order derivative of f is a constant.

Proof: Since a differential in general is independent of the key we will write f(x) instead off(x, k) in the following. To prove the first statement, consider

1In [56] called the nonlinear degree.

5.2. DIFFERENTIAL CRYPTANALYSIS 71 a fixed a = 0 modp. Then

f(x)−f(x+a) =_p f(y)−f(y+a)⇔ x²−(x²+a²+ 2ax) =_p y²−(y²+a²+ 2ay)⇔

−a²−2ax =_p −a²−2ay⇔ 2a(x−y) =_p 0⇔

x =_p y

since pis prime. To prove the second statement, leta₁, a₂ be constants, then

∆_a1,a2f(x)

= f(x+a₁ +a₂)−f(x+a₁)−f(x+a₂) +f(x)

= a²₂ + 2a₂(x+a₁)−(a²₂+ 2a₂x)

= 2a₁a₂

✷ Theorem 5.2.4Let f(x, k) = (x+k)² modp,pprime, be the round function in a 5 round DES-like iterated cipher of block size log₂ p² with independent round keys, i.e., a key size of 5× log₂ p. Then a differential attack using first order diflerentials needs about 2p chosen plaintexts and has a running time of about p³.

Proof: When doing a differential attack counting on the round key in the fifth round of the above cipher we need a 3 (or 4) round differential. It is easy to see that every 3 round differential has a probability of at most p⁻¹ and we obtain

S/N = p× ¹_p 1×1 = 1

where S/N is the signal to noise ratio defined on page 58 and λ = 1, since we use all pairs in the analysis and γ = 1, since in average one key value will be suggested by a pair. This attack is not possible, since the right key cannot be distinguished from other random keys. When doing a differential attack counting on the round keys in both the fourth and fifth rounds we need only a 2 round differential. And since the concepts of characteristics and differentials coincide for 2 rounds in a DES-like cipher, the probability

72 CHAPTER 5. CRYPTANALYSIS OF BLOCK CIPHERS of a 2 round differential is at least 1/pfor the above cipher. In this case we obtain

S/N = p²×1/p 1×1 =p

This attack is possible. We need about 2p chosen plaintexts and for every pair of plaintexts we do two rounds of encryption for everyp² possible keys of the fourth and fifth rounds. Therefore we obtain a complexity of aboutp³. ✷ Theorem 5.2.5Let f(x, k) = (x+k)²modp,pprime, be the round function in a 5 round DES-like iterated cipher of block size log₂ p² with independent round keys, i.e., a key size of 5× log₂ p. Then a differential attack using second order differentials needa about 8chosen plaintext with a running time of about p².

Proof: In the following addition is modulo p. Consider ∆_α,βf(x) where α = a 0 and β = b 0 for some fixed a, b, i.e the right halves of α and β are zero. See also Figure 5.6, where (0,0) denotes the trivial second order derivative of f and where in the second round the second order derivative is (a, b,2×a×b). Consider the following attack

1. Choose plaintext P₁ at random.

2. Set P₂ =P₁+α, P₃ =P₁+β and P₄ =P₁+α+β.

3. Get the encryptions C₁, . . . , C₄ of P₁, . . . , P₄ 4. For every value k₅ of the round keyRK₅ do

(a) Decrypt all ciphertexts C₁, . . . , C₄ one round using k₅. Denote these 4 ciphertexts D₁, . . . , D₄.

(b) For every valuek₄ of the round key RK₄ do i. Calculate t_i =f(D_i^R+k₄) fori= 1, . . . ,4.

ii. If (t1+t4−(t2+t3))−(D₁^L+D₄^L−(D₂^L+D₃^L)) = 2×a×b then output k₅ and k₄.

Here X^L and X^R denote the left and right halves of X respectively. In the first round all inputs to the f-function are equal. In the second round

5.2. DIFFERENTIAL CRYPTANALYSIS 73

Figure 5.6: A second order differential of a five round DES-like iterated cipher.

the inputs form a second order differential with (a, b,2×a×b). Since this differential has probability one according to Theorem 5.2.3, the difference in the four inputs to the third round is Γ = 2×a×b. Therefore the difference in the outputs of the fourth round can be computed as the exclusive-or sum of Γ and of the left halves of the ciphertexts after four rounds. Upon termination a few keys will have been suggested, among which the right keys appear, since the two round second order differential has probability one. Therefore by repeating this attack a few times only one value of (RK₄, RK₅) is suggested every time. This value is guaranteed to be the secret fourth and fifth round

74 CHAPTER 5. CRYPTANALYSIS OF BLOCK CIPHERS keys. The signal to noise ratio of the attack is

S/N = p²×1 1×1 =p²

where we have assumed that one key in average is suggested by each pair of plaintexts. Now it is trivial to find the remaining three round keys by similar attacks on cryptosystems with less than five rounds. As in [7] we can pack the chosen plaintexts in economical structures, thus as an example obtain four second order differentials from 8 chosen plaintexts. ✷ If the primepabove is of size, say about 2²⁵, according to Theorem 5.2.4 a differential attack using first order differential has a complexity of about 2⁷⁵ using about 2²⁶chosen plaintexts, i.e., not at all a practical attack. According to Theorem 5.2.5 a differential attack using second order differentials has a complexity of about 2⁵⁰ using only about 8 chosen plaintexts, a practical attack or at least not far from being one.

The attack in the proof of Theorem 5.2.5 can be applied to any 5 round DES-like iterated cipher, where the round function contains no expansion and where the output coordinates are quadratic, i.e., the nonlinear order of f is 2. Furthermore the attack can be converted into an attack on any 5 round DES-like iterated cipher, as we will show now. For convenience let us consider functions over GF(2). We state explicitly the definition of higher order differentials for this important case.

Definition 5.2.7Consider a Feistel cipher. A one round differential of or-der iis an (i+ 1)-tuple (α₁, . . . , α_i, β), s.t. all α_j’s are linearly independent and

⊕γ∈L(α1,... ,αi)g(P ⊕γ) = β where g is the round function.

It is seen there are 2ⁱ plaintexts in a differential of order i.

Theorem 5.2.6 Let f(x, k) be the round function in a 5 round DES-like iterated cipher of block size 2n with independent round keys, i.e., a key size of 5×n bits. Assume that the nonlinear order of f is r. Then a differential attack using differentials of order r needs about 2^r+1 chosen plaintexts with

5.2. DIFFERENTIAL CRYPTANALYSIS 75 a running time of about 2ⁿ.

Proof: According to Proposition 5.2.3 the rth-order derivative of a func-tion of nonlinear order r is a constant. Therefore we can obtain a 2 round r’th-order differential with probability one and do a similar attack as in the

proof of Theorem 5.2.5. ✷

To illustrate that the above attack works, we consider now the mappings f(x) =x^2k+1 inGF(2ⁿ) described in [85]. According to Theorem 7.3.3 every 3 round differential has a probability of at most 2³⁻²ⁿ, when n is odd and gcd(k, n) = 1.

Lemma 5.2.1 Consider f(x) =x^2k+1 in GF(2ⁿ)for n odd and gcd(k, n) = 1. Then every non-trivial one round differential of f has a probability of at most ₂²n = 2¹⁻ⁿ and the second order derivative of f, ∆_α,βf(x)is a constant with the value Γ =α×β×(α^2k−1⊕β^2k−1).

Proof: The first statement is proved in Theorem 7.3.4 and that the sec-ond derivative is a constant follows from Proposition 5.2.2. The constant is computed as follows.

∆_α,βf(x) = f(x⊕α⊕β)⊕f(x⊕α)⊕f(x⊕β)⊕f(x)

= (x⊕α⊕β)^2k+1⊕(x⊕α)^2k+1⊕(x⊕β)^2k+1⊕(x)^2k+1

= (α⊕β)^2k+1⊕α^2k+1⊕β^2k+1

= α×β×(α^2k−1⊕β^2k−1)

where we note that (x⊕α)^2k+1 = (α×x^2k)⊕(x×α^2k)⊕x^2k+1⊕α^2k+1 ✷ We implemented the attack of Theorem 5.2.5 counting on both the fourth and fifth round key using second order differentials in a five round DES-like iterated cipher with f(x) of Lemma 5.2.1 as round function and with n = 9 and k= 1, i.e., a 18-bit cipher with a 45 bit key. In 100 tests using 12 chosen plaintexts only one pair of keys was suggested and every time this pair was the right values of the fourth and fifth secret round keys. We could have used quartets as defined in [7], thereby reducing the number of chosen plaintexts to about 8.

Note, that for this cipher the probability of any 3 round differential is at most 2³⁻²ⁿ [85] where 2n is the block size. Therefore in a differential

76 CHAPTER 5. CRYPTANALYSIS OF BLOCK CIPHERS attack using first order differentials counting only on the round key in the fifth round, the last round, would yield a signal to noise ratio of

S/N = 2ⁿ×2³⁻²ⁿ

1×1 = 2³⁻ⁿ

and would not be possible for n > 3. A differential attack counting on the round keys in both the fourth and fifth rounds using, what we will call, par-tial differenpar-tials is possible as is demonstrated in the next section.

Conclusion of the attacks. We showed there exist ciphers secure against a differential attack using first order differentials, but which can be bro-ken using second order differentials. We used quadratic functions as round functions and second order differential attacks. We exploit the fact that for quadratic functions the second derivative is a constant. The attack can also be applied to ciphers using higher order functions as round functions. In general, a cipher with five rounds (or less) using round functions of nonlinear order r can be attacked using r’th-order differentials. However, attacks on a cipher with round functions of nonlinear orderr involve encryptions of 2^r chosen plaintexts and the practicality of the attack decreases as r increases.

Our attacks are limited to ciphers with 5 rounds or less and cannot be ex-tended to 6 or more rounds. In the following we will show that even in the case where the round functions are of high order, differential attacks can be mounted.