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$– SEJPMMay 2, 2016 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$– lockerzMay 2, 2016 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-sushiMay 2, 2016 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$– SEJPMMay 2, 2016 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$– lockerzMay 2, 2016 at 19:20
1 Answer
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.