Linear cryptanalysis

In this section we examine the DES for the iterative linear characteristics described in Section 5.3. We will use the same notation as given in [64].

Definition 6.1.1 (DES) For a given S-box S_i, i = 1, . . . ,8, α ∈ GF(2)⁶ and β ∈GF(2)⁴ define

N S_i(α, β) = #{x∈GF(2)⁶, x·α =S_i(x)·β} (6.2) where ‘·’ denotes the dot product.

In the following we refer to the figures in Section 5.3 and denote by X_i be the right half of the ciphertext afteri rounds of encryption, i.e.,X_i is the input to the F-function in the (i+ 1)’th round. X₀ denotes the right half of the plaintext input to the linear characteristic. Also for every round let us fix a key k and for convenience let F(X) denote F(X, k).

118 CHAPTER 6. ANALYSIS OF SPECIFIC BLOCK CIPHERS 2-round iterative characteristics

For this type of characteristic we consider the following expression

max_α|Pr_X(F(X)·α = 0)−1/2| (6.3) One S-box of the DES is a balanced function, therefore (6.3) is zero for all Q only affecting one S-box. In [65] equation (6.3) was examined for two neigh-bouring S-boxes. The best expression uses the following two approximations,

N S₇(3_x, f_x) andN S₈(30_x, d_x)

which combined give a probability of 0.453. Since the input bits to the two S-boxes are shared combining the two expressions will cancel out all input bits and leave only output and key bits. It is the best linear approximation of the type (6.3). Also one can look for the following expressions with three neighbouring S-boxes involved.

N S_i(2_x,∗), N S_i+1(23_x,∗) andN S_i+2(30_x,∗) N S_i(3_x,∗), N S_i+1(33_x,∗) andN S_i+2(30_x,∗) N S_i(3_x,∗), N S_i+1(31_x,∗) andN S_i+2(10_x,∗)

where ‘∗’ denotes the any of the 16 possible values. When combined each of these three expressions will leave only output and key bits in the linear expression. For the DES the best one of these is of the third type,

N S₁(3_x,9_x)N S₂(31_x, b_x) andN S₃(10_x, b_x) with a probability of 0.488.

3-round iterative characteristics

For this type of characteristic we consider the following expression

max_α,β(|Pr_X1(F(X₁)·α =X₁·β)−1/2| × |Pr_X2(F(X₂)·β =X₂·α)−1/2|) (6.4) This kind of characteristic has not been reported by Matsui. However, they exist for the DES with only one active S-box per round. The best one is N S₇(4_x,8_x) and N S₈(2_x,4), with a probability of 1/2−2⁻⁸. Extended to a 14 round characteristic, one obtains a probability of 1/2−2⁻³².

6.1. DES 119 4-round iterative characteristics

As noted in Section 5.3 this is the type of characteristic used by Matsui in the attack on 16-round DES [64, 65, 66]. For this type of characteristic we consider the following expression

max_α,β|Pr_X(X₄·β =X₀·α)−1/2|² (6.5) where (see also Figure 5.9, page 88)

|Pr_X(X₄·β=X−0·α)−1/2|²

=|p_4R−1/2|²

= 4²×

A

|p₁(A)−1/2|²× |p₂(A)−1/2|²× |p₃(A)−1/2|² and where

p₁(A) = Pr_X1(X₁·A=F(X₁)·α) p₂(A) = Pr_X2(X₂·(α⊕β) =F(X₂)·A) p₃(A) = Pr_X3(X₃·A=F(X₃)·β) For one value of A one obtains the best probability using

N S₅(10_x, e_x), N S₁(4_x,4_x) and N S₅(10_x, f_x)

in the second, third and fourth rounds respectively, where the 32 bit quanti-ties are A = 00008000, α = 01040080_x and β = 21040080_x. The probability is 0.506 [64]. However, there is another value of A for the same values of α and β, namely A = 00008800, where the combinations are N S₅(11_x, e_x) in the second round, N S₈(03_x,1_x) and N S₁(34_x,4_x) in the third round and N S₅(11_x, f_x) in the fourth round. The probability is 1/2−2⁻¹⁵. For the 4 round iterative characteristic with α = 01040080_x and β = 21040080_x

|Pr_X(X₄·β =X₀·α)−1/2|² ≥4²×(|0.006|²+|2⁻¹⁵|²)16× |0.006|² (6.6) It is seen that the improvement is hardly measurable. However, “many a little makes a mickle” and in the coming section we illustrate that for longer characteristics the improvement is bigger.

120 CHAPTER 6. ANALYSIS OF SPECIFIC BLOCK CIPHERS

Table 6.9: 4 round iterative linear characteristics.

Longer characteristics

As noted earlier calculating the probabilities of linearr-round characteristics for large r, r > 4, is a difficult task. We end this section by giving some other linear characteristics for the DES, for which the bits of the plaintext and ciphertext are the same as for Matsui’s 14 round linear characteristic used in his attack on 16 round DES [65, 66]. Matsui counts on key bits in the first and last rounds, so we consider the characteristic starting in the second round, where we assume that we know the bitX₁·α, whereX₁ is the right half of the ciphertext after one round of encryption andα= 01040080_x. The characteristic ends in the fifteenth round with knowledge about the bit X₁₅·β, where β = 21040080_x. Let L_i denote the four round characteristic obtained from L_i by interchanging the rounds number two and four. Mat-sui’s characteristic is the concatenation ofL₁,L₁, L₁, one round without any approximation and one round with the combination N S₅(10_x, f_x). Totally this characteristic has a probability, p_L, s.t. |p_L−1/2|² 2^−42.97. In Table 6.9 we have listed some other 4 round iterative linear characteristics, that can replace L₁ in a 14 round characteristic. As also explained above L₂ can re-placeL₁ directly, since for four rounds exactly the same bits of the plaintext and ciphertext are affected. The concatenation L₃, L₃ can replace L₁, L₁. This holds also forL₅, L₅. The concatenationL₄, L₄ can replaceL₁, L₁. This holds also for L₆, L₆. Totally this gives us eight paths fromX₁·α toX₁₅·β,

6.1. DES 121 yielding

|Pr_X(X₁·α=X₁₅·β)−1/2|² ≥2^−42.96.

This is only slightly higher than for the best single characteristic.

We found other characteristics like the ones in Table 6.9, however with even smaller probabilities. We looked only for other 4-round iterative char-acteristics. By examining also n-round characteristics, n > 4, one might get other interesting results. Since Matsui’s expression involves at most one S-box for each round and optimises the use of the best one-round expression, with probability ⁵²₆₄ it is doubtful that the probability of his characteristic will be higher than the above estimate.

Probabilities of iterative characteristics

In Section 6.1.1 we showed that the probabilities of characteristics in differ-ential attacks varies, when neighbouring S-boxes are considered. One S-box in the DES take a 6 bit text input and a 6 bit key input. Two neighbouring S-boxes in the DES share two input text bits and take a 10 bit text input and a 12 bit key input. Also in linear characteristics the probabilities of ap-proximations involving neighbouring S-boxes varies depending on the actual values of the four key bits, that affect the shared text bits for two S-boxes.

Example 6.1.4 Consider L₂ from Table 6.9. In the second round we use N S₈(03_x,1_x), N S₁(34_x,4_x)

When the two approximations are calculated separately the probability, |p_L− 1/2| is 2× ₆₄^2×_×⁴₆₄ 2⁻⁸ using the Piling-Up Lemma. However, if the sixth key bit of S₈ and the second key bit of S₁ are equal the exact probability,

|p_L−1/2|is ₁₀₂₄⁶ 2^7.42 and when they are different,|p_L−1/2|is ₁₀₂₄² 2⁻⁹. This splitting of the probability does not seem to have the same importance in linear cryptanalysis on the DES as in differential cryptanalysis on DES.

Whether the phenomenon can be used to find good linear approximation, where neighbouring S-boxes in some rounds are considered, is left as an open problem.

122 CHAPTER 6. ANALYSIS OF SPECIFIC BLOCK CIPHERS