2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – SEJPM Jul 19 '15 at 16:09
  • $\begingroup$ I think this may be a duplicate (hoping we had a question about 2DES before), but I can't find a corresponding "original" question... $\endgroup$ – SEJPM Jul 19 '15 at 16:18
  • $\begingroup$ @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. $\endgroup$ – Ilmari Karonen May 20 '16 at 17:40
3
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.