Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Among other sources, this wikipedia entry states that triple DES using three seperate keys (k1, k2, k3) is vulnerable to meet-in-the-middle-attacks, while triple DES using only two keys (k1, k2, k1) is not.

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

share|improve this question

migrated from security.stackexchange.com Feb 14 '13 at 14:06

This question came from our site for Information security professionals.

    
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 . –  owlstead Feb 14 '13 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. –  malexmave Feb 14 '13 at 22:52
add comment

1 Answer

up vote 17 down vote accepted

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.

share|improve this answer
    
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. –  malexmave Feb 14 '13 at 14:01
1  
@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^114 keys. –  CodesInChaos Feb 14 '13 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. –  owlstead Feb 14 '13 at 23:02
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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