2

So studying double encryption (double DES) and understanding why it is subject to a meet-in-the-middle attack, I tried to see if the same attack could be applied to a triple encryption with only two different keys and no decryption operation. I.e.:

$$c=E_{k2}(E_{k1}(E_{k1}(m)))$$

where $c$ is the ciphertext, $m$ the plaintext and ${k_1,k_2}$ the two keys.

It seems the normal way is to have encryption-decryption-encryption with either 2 or 3 different keys. However, with only two keys and three sequential encryptions provide any more security than double DES? I guess you could still apply the meet-in-the-middle attack, since there are intermediary values to which you can apply the same attack, but I'm a bit confused to whether it adds more security than double DES?

I guess it would require $2^{56}$ additional operations to perform a meet-in-the-middle attack since there is an extra step compared to double DES?

Additional question: Does it matter in which order you apply the keys? I.e. is there a difference between encrypting with $k_2-k_1-_1$ vs. $k_1-k_2-k_1$?

All keys in my question are of size 56-bits.

e-sushi
  • 17,617
  • 12
  • 80
  • 223
Force444
  • 145
  • 7
  • Related question: [Why is triple-DES using three different keys vulnerable to a meet-in-the-middle-attack?](http://crypto.stackexchange.com/questions/6345/why-is-triple-des-using-three-different-keys-vulnerable-to-a-meet-in-the-middle) – CodesInChaos Jun 20 '15 at 08:38

1 Answers1

7

The meet-in-the-middle attack still applies; instead of attack effort $2^{57}$ DES invocations, you just increased it by $2^{56}$ extra DES block encryptions, i.e. up to about $2^{57.6}$ in total: a mere +50% increase. On the other hand, you also made the overall block cipher (your two-key triple encryption) 50% more expensive to use, so the overall security has not changed at all: attacker and defender have been slowed by the same amount.

What would make the construction much stronger is what is down with the true Triple-DES in two-key mode: $E_{k1}(D_{k2}(E_{k1}(m)))$. With the keys used alternately, the meet-in-the-middle is effectively prevented.

You could replace the middle decryption with an encryption: $E_{k1}(E_{k2}(E_{k1}(m)))$. This would still be secure, but no longer backward compatible with "plain DES", for no obvious gain (DES encryption and decryption are identical, save for the ordering of the sub-keys, so converting a decryption block to an encryption block does not seem to imply any implementation advantage).

e-sushi
  • 17,617
  • 12
  • 80
  • 223
Tom Leek
  • 911
  • 4
  • 5
  • 1
    Stating that 2-key TDES effectively prevents meet-in-the-middle is an oversimplification; it helps, but is not quite bullet-proof. See Paul C. van Oorschot and Michael J. Wiener: [_A Known-Plaintext Attack on Two-Key Triple Encryption_](http://www.scs.carleton.ca/~paulv/papers/Euro90.pdf) (in [proceedings of Eurocrypt 1990](http://link.springer.com/chapter/10.1007/3-540-46877-3_29)). Their attacks is far from practical, but is much better than brute-forcing the 112-bit key. More [there](http://crypto.stackexchange.com/q/2466/555). – fgrieu Jul 07 '16 at 22:07