Search in book...
Toggle Font Controls
Create new playlist

Name your new playlist

Playlist description (optional)
Sign In

Email address

Password

Forgot Password?

or

Continue with Facebook

Continue with Google
Sign Up

Full Name

Email address

Confirm Email Address

Password

or

Continue with Facebook

Continue with Google

6.5 Meet-in-the-Middle Attacks

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

$E_{K} (m)$ $E_{K} (m)$ for all possible keys $K$ $K$
$D_{L} (c)$ $D_{L} (c)$ for all possible keys $L$ $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)$ $(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 $K_{1}, K_{2}$ $K_{1}, K_{2}$ .

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$ $N$ possible keys, Eve needs to compute $N$ $N$ values $E_{L} (m)$ $E_{L} (m)$ . She then needs to compute $N$ $N$ numbers $D_{L} (c)$ $D_{L} (c)$ and compare them with the stored list. But these $2 N$ $2 N$ computations (plus the comparisons) are much less than the $N^{2}$ $N^{2}$ computations required for searching through all key pairs $K_{1}, K_{2}$ $K_{1}, K_{2}$ .

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

We know that one of these $2^{48}$ $2^{48}$ matches is from the correct pair $(K_{1}, K_{2})$ $(K_{1}, K_{2})$ , and the other matches are probably caused by randomness. If we take a random pair $(K, L)$ $(K, L)$ and try it on a new plaintext–ciphertext $(m_{1}, c_{1})$ $(m_{1}, c_{1})$ , then $E_{L} (E_{K} (m_{1}))$ $E_{L} (E_{K} (m_{1}))$ is a 64-bit block that has probability $2^{- 64}$ $2^{- 64}$ of matching the 64-bit block $c_{1}$ $c_{1}$ . Therefore, among the approximately $2^{48}$ $2^{48}$ random pairs, we expect $2^{48} 2^{- 64} = 2^{- 16}$ $2^{48} 2^{- 64} = 2^{- 16}$ matches between $E_{L} (E_{K} (m_{1}))$ $E_{L} (E_{K} (m_{1}))$ and $c_{1}$ $c_{1}$ . In other words, it is likely that the second plaintext–ciphertext pair eliminates all extraneous solutions and leaves only the correct key pair $(K_{1}, K_{2})$ $(K_{1}, K_{2})$ . If not, a third round should complete the task.

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.

Table of Contents for 6.5 Meet-in-the-Middle Attacks

Create new playlist

Sign In

Sign Up

Table of Contents for
6.5 Meet-in-the-Middle Attacks