Suppose triple DES is performed by choosing two keys $K_1$ and $K_2$ and computing $C = T (T (T (L, K_1), K_2), K_2)$. How to attack this modified version with a meet-in-the-middle attack, in which the attacker knows at least one $(L,C)$ pair?

  • $\begingroup$ Can you please clarify what $T(M,K)$ means? Encryption using plain DES? $\endgroup$ – SEJPM May 2 '16 at 19:06
  • $\begingroup$ Sorry but I can't seem to find T(M,K) anywhere in the question. Triple DES has been used in this case $\endgroup$ – lockerz May 2 '16 at 19:13
  • $\begingroup$ Just to be sure at what knowledge level you are: What research have you done? For example, did you search this site for Q&As like “Why is triple-DES using three different keys vulnerable to a meet-in-the-middle-attack?” and its accepted answer? That might already answer your question… $\endgroup$ – e-sushi May 2 '16 at 19:13
  • $\begingroup$ oh, sorry, I was slightly unclear up there then: You write $T(L,K_1)$. Is this plain DES encryption or is it rather full Triple-DES encryption (so you'd be doing 9x DES in this case)? $\endgroup$ – SEJPM May 2 '16 at 19:16
  • $\begingroup$ It is plain DES encryption I guess..I searched a lot and mostly found the answers when the keys are T((L,k1),k2,k1) and unsure what would happen in this case where it is T(L,k1),k2,k2) $\endgroup$ – lockerz May 2 '16 at 19:20

This illustrates the importance of getting the key order right with 3DES two-key keying option. With the correct order of $k_1$, $k_2$, $k_1$ you get something that should be impossible to attack with current resources, while with the incorrect order in the question it is feasible to attack.

The outer two encryption layers can be joined into a single cipher, which we may call DES2. That is a 64-bit block cipher with a 56-bit key, just like DES. It is approximately twice as expensive to compute.

The question then becomes the simple case of applying the meet-in-the-middle attack to double encryption. The inner cipher is DES, the outer DES2. The fastest option is to build the table for the inner encryption encryption in $2^{56}$ DES calls, since you then only need to compute the outer cipher $2^{55}$ times on average (i.e. $2^{56}$ DES calls).

You need memory for a $2^{56}$ item table, unless you apply a time-memory tradeoff. It would be expensive but on the verge of doable even with this brute force approach. You may also be able to get away with a factor of 2 or so fewer calls by making use of related keys. Other improvements are likely possible.


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.