Differential cryptanalysis in different modes of operation 79

The attacks by differential cryptanalysis are chosen plaintext attacks. How-ever, the efficiency of a differential attack depends on the mode of operation, which is used for the attacked block cipher. The complexity of the attacks by Biham and Shamir [7] is the number of encryptions of chosen plaintexts, which the attacker needs in the attack, assuming that the block cipher is used in the native ECB mode. A chosen plaintext attack is not a realistic attack in many settings. lt is possible to Convert a differential attack on a block cipher used in ECB mode into a known plaintext attack, which is a more realistic attack. Assume that we need m pairs of plaintexts with a certain difference. By collecting about 2^n/2×√

2mknown plaintexts, we can

pairs of plaintext pairs. If m and n are big, this forming of pairs may be computationally infeasible. Anyway, since there are exactly 2ⁿpairs of plain-texts with any certain difference, we can expect to get about m pairs with the needed difference [7]. This is not the whole story, though. If the plain-texts contain redundancy the differences of plaintext pairs are not necessarily uniformly distributed. As an example, take the exclusive-or as the difference operation. Then if the plaintexts consist of ASCII characters, every parity bit in a byte is zero, therefore in an exclusive-or of any two plaintexts all parity bits are zero.

For most of the differential attacks many pairs of plaintexts are needed [7]. It is not advisable to use the ECB mode when many plaintext blocks are to be encrypted, therefore an attacker can expect that the attacked block cipher is not used in the ECB mode. When a block cipher is used in the CBC mode, the attacker has no control over the inputs to the block cipher.

Assume in the following that a differential attack needs m pairs of chosen plaintexts, when the block cipher is used in the ECB mode. Then there exists a differential attack on the same block cipher used in the CBC mode, that needs 2^n/2 ×√

2m known or chosen plaintexts by an argument similar as above. A complexity of m pairs can be obtained for the block cipher used in the CBC mode in an adaptively chosen plaintext attack, if the initial

80 CHAPTER 5. CRYPTANALYSIS OF BLOCK CIPHERS value is not secret. The attacker chooses one random plaintext P and gets the encryption C = E_K(P ⊕ IV), where IV is an initial value. He then repeats the with plaintext P, s.t. P ⊕P have the desired difference and gets C = E_K(P ⊕IV). Assuming that the initial value is unchanged the inputs to the block cipher for the two encryptions have the desired difference.

If the initial value changes for every CBC encryption an attacker cannot do an adaptively chosen plaintext attack.

An adaptively chosen plaintext attack is the least practical of all attacks.

It is important to note, that even though Biham and Shamir’s results on the DES [7] are very impressive, the attacks are by far no practical attacks.

Assume again that a differential attack needs m pairs of chosen plain-texts, when the block cipher is used in the ECB mode. Then there exists a differential attack on the same block cipher used in the OFB mode with full feedback, that needs 2^n/2×√

2mknown or chosen plaintexts by an argument similar as for the CBC mode. A similar argument holds for the CFB mode.

But whereas the OFB mode should be used only with full feedback, as noted in Section 3.1, the CFB can be used with any feedback. If n < n bits are fed back, the attacker does not know the full output of the block cipher and the success of a differential attack decreases. Differential attacks on the DES used in the CFB mode have been considered in [97]. A modified differential attack is presented, which works for m≥3, where m is the size of plaintext and ciphertext blocks and wherembits are used in the feedback. The attacks on the DES are faster than exhaustive search only for a restricted number of rounds, i.e., up to 10 rounds. The work is motivated by the fact that for m < n, encryption in the CFB mode is slow and for small m it may be tempting to reduce the number of rounds in the DES to achieve better performance.

5.3 Linear Cryptanalysis

In 1993 M. Matsui introduced linear cryptanalysis of the DES [64]. A similar attack on FEAL appeared already in 1992 [68]. Linear cryptanalysis [64] is a known plaintext attack in which the attacker exploits linear approximations of some bits of the plaintext, ciphertext and key. In the attack on the DES (or on DES-like iterated ciphers) the linear approximations are obtained by combining approximations for each round under the assumption of

indepen-5.3. LINEAR CRYPTANALYSIS 81 dent round keys. The attacker hopes in this way to find an expression (5.6), which holds with probability p_L = ¹₂ over all keys [64] T such that |p_L− ¹₂| is maximal.

(P ·α)⊕(C·β) = (K ·γ) (5.6) where P, C,α, β,γ are m-bit strings and where ‘·’ denotes the dot product.

Since an expression (5.6) in the ideal case will have a probability one half, and since it contains only linear expressions, we call the expression (5.6) a linear approximation. Given an approximation (5.6) a linear attack usingN plaintexts and the N corresponding ciphertexts goes as follows.

Linear attack [64]

1. For all plaintexts,P, and ciphertexts,C, letT be the number of times the lefthand side of (5.6) is zero.

2. If T > N/2 guess that K·γ = 0, otherwise guess that K·γ = 1.

The attack finds one bit of information about the key, K ·γ, and the com-plexity of a successful attack, i.e., the number of known plaintexts needed, using the above algorithm can be approximated in the following way. Let T be a binomial random variable taking on the value 0 with probability p.

Assume that |p−1/2|is small and w.l.o.g. that p >1/2. Then Pr(T > N/2) = 1−Pr(T ≤N/2)

1−Φ(N/2 + 1/2−N p p(1−p)×√

N) 1−Φ(−2√

N|p−1/2|)

= Φ(2√

N|p−1/2|)

where Φ is the normal distribution function. With N = |p−1/2|⁻² the success rate is about 97.72%. Since the number of plaintexts needed is the dominating factor in a linear attack, the complexity, N_P, of the above linear attack is [64]

N_P |p_L−1/2|⁻²

82 CHAPTER 5. CRYPTANALYSIS OF BLOCK CIPHERS wherep_L is the probability of a linear approximation of the form (5.6). This estimate shows that the quantity of interest in a linear attack is|p_L−1/2|⁻². For DES-like iterated ciphers linear approximations of the form (5.6) can be found by combining linear approximations of each round in the cipher. As in differential cryptanalysis we can define characteristics to be used in linear cryptanalysis.

Definition 5.3.1 A one-round linear characteristic is a list of input, key and output bits of one round of the block cipher and a probability p over all keys and plaintexts, s.t. the boolean value obtained by adding (modulo 2) the input and key bita equals the boolean value obtained by adding (modulo 2) the output bits with probability p. An r-round linear characteristic is the concatenation of r one-round linear characteristics.

In some rounds of a linear characteristic linear approximations are not needed.

We call these rounds trivial one-round linear characteristics.

As in differential cryptanalysis by assuming that therone round approxi-mations are independent we can calculate the probability of anr-round linear approximation from the probabilities of ther one round approximations, for example by assuming that the round keys in the cipher are independent. The probability of anr-round linear characteristic is calculated using the Piling Up-Lemma [64].

Lemma 5.3.1 Let Z_i,1 ≤ 2 ≤ n, be independent random variables, whose boolean values are 0with probability p_i. Then

Pr(Z₁⊕Z₂⊕ · · · ⊕Z_n = 0) = 1/2 + 2ⁿ⁻¹ n i=1

(p_i−1/2) (5.7) The above linear attack is not very efficient, since it finds only one bit of information about the key. However, there exists an extended linear at-tack, which finds more key bits. Instead of approximating the first and last round in an r-round iterated cipher, since we know both the plaintext and the ciphertext, we can count on all keys which affects the bits in the lin-ear approximation (5.6) in the first and last round, yielding the following approximation

(P ·α)⊕(C·β)⊕(F(P_R, K₁)·α₁)⊕(F(C_R, K_r)·α_r) = (K·γ) (5.8)

5.3. LINEAR CRYPTANALYSIS 83 where P_R,C_R are the right halves of the plain- and ciphertexts respectively.

K₁ andK_r are the key bits affecting the linear approximation in the first and r’th rounds. For all choices of the keys K₁ and K_r the approximation (5.8) can be seen as an approximation of a cipher of r-2 rounds, i.e., two rounds shorter than the original cipher. The attack goes as follows with N available plaintexts.

Extended linear attack [64]

1. For all, sayn, values of the two keys, K₁ and K_r do:

For all plaintexts, P, and ciphertexts, C, let T_i, i = 1, . . . , n, be the number of times the lefthand side of (5.6) is zero.

2. Let T_max and T_min be the maximum and minimum values of the T_i’s for i= 1, . . . , n. If |T_max−N/2|>|T_min−N/2| guess thatK₁ andK_r are the key values from the computation of T_max.

If|T_max−N/2|<|T_min−N/2|guess thatK₁ andK_r are the key values from the computation of T_min.

In case of the DES it is conjectured and confirmed by computer experiments [64, 65, 66] that the efficiency of (5.8) decreases, when the values of K₁ or K_r are incorrect values. The complexity of success of this extended attack is somewhat larger than the complexity using the first attack. In [64, 65, 66]

it is estimated that the complexity of an extended linear attack on the DES with up to 16 rounds is about

N_P c× |p_L−1/2|⁻²

where c ≤ 8 [65, 66]. Note that the success of the extended attack is inde-pendint of the parity of the key bits from the intermediate rounds, K ·γ.

And opposite to Matsui’s attack we will not use the right side of (5.8) in the attack. The reason for this follows in the coming section. Note that the practicality of this extended attack depends also on how many key bits are needed to count on in the first and last rounds. In his attack on the DES, because only one S-box is active in every round of the linear approxi-mation, Matsui counts on and finds 12 bits of the key. By using other linear approximations other bits of the key can be found.

84 CHAPTER 5. CRYPTANALYSIS OF BLOCK CIPHERS