2DES vs. two-key triple encryption, with no decryption step

Question

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.

Answer 1

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).