# Finding keys of modified DES encryption

This is a question I had in my exam today, and I'll be glad if someone can help me to find the answer.

A student built an encryption algorithm (something between DES and 3DES), in which the encryption is based on 2 keys, $K_1$ and $K_2$, and calculated this way:

$$Cipher = E_{K_1} (E_{K_2} (plaintext))$$

where $E_{K_i}$ is encryption using the key $K_i$.

An attacker knows:

1. A single plaintext.
2. The ciphertext of that plaintext.
3. The encryption algorithm.
4. Each key is 56-bit.

How can he find the 2 keys?

Of course there's the brute-force solution, looking in all the possible pairs of keys until we find the correct one.

My question is: Can we find another way, better than the brute-force, in order to find the keys?

• I think you're looking for the "meat-in-the-middle" (thank you Gilles) attack. It provides you sub-bruteforce speed ($2^{57}$ computations vs. $2^{112}$ for brute-force) and only requires a bit ($2^{56}$) storage. Wikipedia – SEJPM Jul 19 '15 at 16:09
• I think this may be a duplicate (hoping we had a question about 2DES before), but I can't find a corresponding "original" question... – SEJPM Jul 19 '15 at 16:18
• @SEJPM: The closest thing I found was this question, but it has itself been closed as a duplicate (somewhat questionably, IMO, as discussed in the comments and in this meta thread). My previous reopen vote seems to have expired; let me re-cast it. – Ilmari Karonen May 20 '16 at 17:40

## 1 Answer

You can do this slightly better with an additional $\mathcal{0}(2^{56})$ memory and with $\mathcal{0}(2^{56})$ time.

You can notice that the relation $c \leftarrow E_{k_1}(E_{k_2}(m))$ can be rewritten as $D_{k_1}(c) = E_{k_2}(m)$ (just apply the decrypt function on both sides.

First step consists in the generation of every pair $(k_2, E_{k_2}(m))$ and storing them in table (preferably a hash-table for fast lookups).

Having a table with all the pairs $k_2, E_{k_2}(m)$ you can now try all values for $k_1 = 0,2^{56}$ and apply the decrypt function $D_{k_1}$ on the ciphertext received initally. If the value $D_{k_1}(c)$ exists in your precomputed table then you have found the other key $k_2$ which was used to encrypt the original plaintext.

This method also stands by the name of meet-in-the-middle attack.

• Thank you. I didn't know the meet-in-the-middle attack, and it seems to be the answer desired. – Asaf Kahlon Jul 20 '15 at 3:41