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$
3
  • $\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, 2015 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, 2015 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$ May 20, 2016 at 17:40

1 Answer 1

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$
1
  • $\begingroup$ Thank you. I didn't know the meet-in-the-middle attack, and it seems to be the answer desired. $\endgroup$ Jul 20, 2015 at 3:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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