6.5 Meet-in-the-Middle Attacks – Introduction to Cryptography with Coding Theory, 3rd Edition

6.5 Meet-in-the-Middle Attacks

Alice and Bob are using an encryption method. The encryption functions are called EK, and the decryption functions are called DK, where K is a key. We assume that if someone knows K, then she also knows EK and DK (so Alice and Bob could be using one of the classical, nonpublic key systems such as DES or AES). They have a great idea. Instead of encrypting once, they use two keys K1 and K2 and encrypt twice. Starting with a plaintext message m, the ciphertext is c=EK2(EK1(m)). To decrypt, simply compute m=DK1(DK2(c)). Eve will need to discover both K1 and K2 to decrypt their messages.

Does this provide greater security? For many cryptosystems, applying two encryptions is the same as using an encryption for some other key. For example, the composition of two affine functions is still an affine function (see Exercise 11 in Chapter 2). Similarly, using two RSA encryptions (with the same n) with exponents e1 and e2 corresponds to doing a single encryption with exponent e1e2. In these cases, double encryption offers no advantage. However, there are systems, such as DES (see Subsection 7.4.1) where the composition of two encryptions is not simply encryption with another key. For these, double encryption might seem to offer a much higher level of security. However, the following attack shows that this is not really the case, as long as we have a computer with a lot of memory.

Assume Eve has intercepted a message m and a doubly encrypted ciphertext c=EK2(EK1(m)). She wants to find K1 and K2. She first computes two lists:

  1. EK(m) for all possible keys K

  2. DL(c) for all possible keys L.

Finally, she compares the two lists and looks for matches. There will be at least one match, since the correct pair of keys will be one of them, but it is likely that there will be many matches. If there are several matches, she then takes another plaintext–ciphertext pair and determines which of the pairs (K, L) she has found will encrypt the plaintext to the ciphertext. This should greatly reduce the list. If there is still more than one pair remaining, she continues until only one pair remains (or she decides that two or more pairs give the same double encryption function). Eve now has the desired pair K1, K2.

If Eve has only one plaintext–ciphertext pair, she still has reduced the set of possible key pairs to a short list. If she intercepts a future transmission, she can try each of these possibilities and obtain a very short list of meaningful plaintexts.

If there are N possible keys, Eve needs to compute N values EL(m). She then needs to compute N numbers DL(c) and compare them with the stored list. But these 2N computations (plus the comparisons) are much less than the N2 computations required for searching through all key pairs K1,  K2.

This meet-in-the-middle procedure takes slightly longer than the exhaustive search through all keys for single encryption. It also takes a lot of memory to store the first list. However, the conclusion is that double encryption does not significantly raise the level of security.

Similarly, we could use triple encryption, using triples of keys. A similar attack brings the level of security down to at most what one might naively expect from double encryption, namely squaring the possible number of keys.

Example

Suppose the single encryption has 256 possible keys and the block cipher inputs and outputs blocks of 64 bits, as is the case with DES. The first list has 256 entries, each of which is a 64-bit block. The probability that a given block in List 1 matches a given block in List 2 is 264. Since there are 256 entries in List 2, we expect that a given block in List 1 matches 256264=28 entries of List 2. Running through the 256 elements in List 1, we expect 25628=248 pairs (K, L) for which there are matches between List 1 and List 2.

We know that one of these 248 matches is from the correct pair (K1, K2), and the other matches are probably caused by randomness. If we take a random pair (K, L) and try it on a new plaintext–ciphertext (m1, c1), then EL(EK(m1)) is a 64-bit block that has probability 264 of matching the 64-bit block c1. Therefore, among the approximately 248 random pairs, we expect 248264=216 matches between EL(EK(m1)) and c1. In other words, it is likely that the second plaintext–ciphertext pair eliminates all extraneous solutions and leaves only the correct key pair (K1, K2). If not, a third round should complete the task.