Why is triple-DES using three different keys vulnerable to a meet-in-the-middle-attack?

Among other sources, this Wikipedia entry states that triple-DES using three separate keys $$(k_1, k_2, k_3)$$ is vulnerable to meet-in-the-middle-attacks, while triple-DES using only two keys $$(k_1, k_2, k_1)$$ is not.

Why is this attack possible if all the keys are different, but not if the first and the third are the same?

• Note that the meet in the middle attack is definitely not the only reason why triple DES has lower security than you would expect by just looking at the key sizes. Check the latest NIST and ECRYPT recommendations, e.g. on keylength.com . Commented Feb 14, 2013 at 17:18
• @owlstead Thanks for the Link. I would never use 3DES anyway, this was just a question raised and not answered by the Wikipedia article. Commented Feb 14, 2013 at 22:52

The main difference is that with two 56 bit keys the maximal security level is 112 bit, and thus an attack that has a cost of $2^{112}$ operations is no attack, whereas for three 56 bit keys the maximal security level is 168 bits, and an attack that has a cost of $2^{112}$ operations counts as an attack.

This means that two-key 3DES is still a bit weaker than three-key 3DES, but not as much as we'd expect of an ideal 168 bit cipher.

With meet-in-the middle the cipher gets split into two halves, which are attacked separately. The cost of the attack is the sum of the attacks on the two halves, which is dominated by the more expensive half. So meet-in-the-middle is possible if you can split the cipher in a way that the more expensive half is cheaper to attack than guessing the whole key. (Disregarding memory use)

With two keys, one half has (k1,k2) and the other k1. Attacking the first half costs $2^{112}$ operations, attacking the second half costs $2^{56}$ operations. For a total of $~2^{112}$ operations.

With three keys, one half has (k1,k2) and the other k3. Attacking the first half costs $2^{112}$ operations, attacking the second half costs $2^{56}$ operations. For a total of $2^{112} + 2^{56} \approx 2^{112}$ operations.

So meet-in-the-middle gives us an attack with $2^{112}$ operations against either of them, but it's only better than brute-force when using three keys.

• Thanks for your answer, but the question I was trying to ask is why Meet in the Middle won't work (or will not make the attack "cheaper") on 2 keys as opposed to three keys. Or is 114 operations a fixed value for meet-in-the-middle? EDIT: Seeing your edit, it now is a bit clearer to me what you mean. Thanks. Commented Feb 14, 2013 at 14:01
• @malexmave There is no way to split either of them into two halves in a way where the more expensive half has less than 2^112 keys. Commented Feb 14, 2013 at 14:03
• @CodesInChaos OK, but to make the answer complete you could maybe explain why it is possible to split triple DES with 3 keys in two halves. Commented Feb 14, 2013 at 23:02
• Let me just see if I understand this correctly. The absolute security of a two-key 3DES EDE (or said differently, three-key EDE where K1 == K3) scheme is very near identical to that of a three-independent-keys 3DES EDE scheme; the three-key scheme is only considered "worse" because we'd expect the three-key scheme to, in an ideal world, provide three times the algorithm's key length worth of security, not twice the algorithm's key length, so in the three-independent-keys scheme we aren't getting our full 168 bits worth?
– user
Commented Apr 18, 2015 at 17:09
• @MichaelKjörling Yes. If you use random keys, 3-key 3DES is at least as strong as 2-key 3DES, but it doesn't provide the 168 bits of security we'd expect from an ideal 168 bit cipher. MitM has nearly the same cost against both 2-key and 3-key 3DES. But since "attack" is often defined as "faster than brute-force" and brute-force is slower with a 168 bit key, MitM now counts as an attack. (If you'd allow related-key attacks the 3-key variant would probably end up worse, but related keys are not applicable to well designed protocols, so I didn't mention that in my answer.) Commented Apr 18, 2015 at 17:21