encryption des attack 3des meet-in-the-middle-attack
Updated Mon, 30 May 2022 22:29:13 GMT

Triple DES with 2 keys

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?


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.