Meet-in-the-Middle Attack

Meet-in-the-Middle Attack

Thus, the use of double DES results in a mapping that is not equivalent to a single DES encryption. But there is a way to attack this scheme, one that does not depend on any particular property of DES but that will work against any block encryption cipher.

The algorithm, known as a meet-in-the-middle attack, was first described in [DIFF77]. It is based on the observation that, if we have

C = E(K₂, E(K₁, P))

then (see Figure 6.1a)

X = E(K₁, P) = D(K₂, P)

Given a known pair, (P, C), the attack proceeds as follows. First, encrypt P for all 2⁵⁶ possible values of K₁ Store these results in a table and then sort the table by the values of X. Next, decrypt C using all 2⁵⁶ possible values of K₂. As each decryption is produced, check the result against the table for a match. If a match occurs, then test the two resulting keys against a new known plaintext-ciphertext pair. If the two keys produce the correct ciphertext, accept them as the correct keys.

---

[Page 178]

For any given plaintext P, there are 2⁶⁴ possible ciphertext values that could be produced by double DES. Double DES uses, in effect, a 112-bit key, so that there are 2¹¹² possible keys. Therefore, on average, for a given plaintext P, the number of different 112-bit keys that will produce a given ciphertext C is 2¹¹²/2⁶⁴ = 2⁴⁸. Thus, the foregoing procedure will produce about 2⁴⁸ false alarms on the first (P, C) pair. A similar argument indicates that with an additional 64 bits of known plaintext and ciphertext, the false alarm rate is reduced to 2^48-64 = 2^-16 Put another way, if the meet-in-the-middle attack is performed on two blocks of known plaintext-ciphertext, the probability that the correct keys are determined is 1 2^-16. The result is that a known plaintext attack will succeed against double DES, which has a key size of 112 bits, with an effort on the order of 2⁵⁶, not much more than the 2⁵⁵ required for single DES.

Triple DES with Two Keys

An obvious counter to the meet-in-the-middle attack is to use three stages of encryption with three different keys. This raises the cost of the known-plaintext attack to 2¹¹², which is beyond what is practical now and far into the future. However, it has the drawback of requiring a key length of 56 x 3 = 168 bits, which may be somewhat unwieldy.

As an alternative, Tuchman proposed a triple encryption method that uses only two keys [TUCH79]. The function follows an encrypt-decrypt-encrypt (EDE) sequence (Figure 6.1b):

C = E(K₁, D(K₂, E(K₁, P)))

There is no cryptographic significance to the use of decryption for the second stage. Its only advantage is that it allows users of 3DES to decrypt data encrypted by users of the older single DES:

C = E(K₁, D(K₁, E(K₁, P))) = E(K₁, P)

3DES with two keys is a relatively popular alternative to DES and has been adopted for use in the key management standards ANS X9.17 and ISO 8732.^[1]

^[1] (ANS) American National Standard: Financial Institution Key Management (Wholesale). From its title, X9.17 appears to be a somewhat obscure standard. Yet a number of techniques specified in this standard have been adopted for use in other standards and applications, as we shall see throughout this book.

Currently, there are no practical cryptanalytic attacks on 3DES. Coppersmith [COPP94] notes that the cost of a brute-force key search on 3DES is on the order of 2¹¹² (5 x 10³³) and estimates that the cost of differential cryptanalysis suffers an exponential growth, compared to single DES, exceeding 10⁵².

It is worth looking at several proposed attacks on 3DES that, although not practical, give a flavor for the types of attacks that have been considered and that could form the basis for more successful future attacks.

---

[Page 179]

The first serious proposal came from Merkle and Hellman [MERK81]. Their plan involves finding plaintext values that produce a first intermediate value of A = 0 (Figure 6.1b) and then using the meet-in-the-middle attack to determine the two keys. The level of effort is 2⁵⁶, but the technique requires 2⁵⁶ chosen plaintext-ciphertext pairs, a number unlikely to be provided by the holder of the keys.

A known-plaintext attack is outlined in [VANO90]. This method is an improvement over the chosen-plaintext approach but requires more effort. The attack is based on the observation that if we know A and C (Figure 6.1b), then the problem reduces to that of an attack on double DES. Of course, the attacker does not know A, even if P and C are known, as long as the two keys are unknown. However, the attacker can choose a potential value of A and then try to find a known (P, C) pair that produces A.