# 6.5 Meet-in-the-Middle Attacks

Alice and Bob are using an encryption method. The encryption functions are called , and the decryption functions are called , where  is a key. We assume that if someone knows , then she also knows  and  (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  and  and encrypt twice. Starting with a plaintext message , the ciphertext is . To decrypt, simply compute . Eve will need to discover both  and  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 ) with exponents  and  corresponds to doing a single encryption with exponent . 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  and a doubly encrypted ciphertext . She wants to find  and . She first computes two lists:

1.  for all possible keys 

2.  for all possible keys .

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  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 .

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  possible keys, Eve needs to compute  values . She then needs to compute  numbers  and compare them with the stored list. But these  computations (plus the comparisons) are much less than the  computations required for searching through all key pairs .

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  possible keys and the block cipher inputs and outputs blocks of 64 bits, as is the case with DES. The first list has  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 . Since there are  entries in List 2, we expect that a given block in List 1 matches  entries of List 2. Running through the  elements in List 1, we expect  pairs  for which there are matches between List 1 and List 2.

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