# Double encryption : what method is the best?

Given the block-ciphers defined as follows :

$$1.$$ $$C=$$ $$E_{k1}(E_{k2}(M))$$

$$2.$$ $$C=$$ $$E_{k1{\oplus}k2}(M)$$

$$3.$$ $$C=$$ $$(E_{k1}(r),E_{k2}(r$$ $${\oplus}$$ $$M))$$

where $$C$$ is the cipher text, $$E$$ is the block cipher, $$M$$ the message to be encrypted, $$k1$$ and $$k2$$ the sender and receiver respective secret keys and $$r$$ a randomly generated string with a length equals to that of $$M$$.

Assumptions:

• we need to encrypt $$M$$ so that both keys $$k1$$ and $$k2$$ (having a length of $$n$$ bits) are needed for decryption.
• We have access to a particular ciphertext/message pair $$(M,C)$$.

Questions:

• Having that pair $$(M,C)$$, how would we decrypt some other cipher text $$C$$ $$'$$ in each method?
• Which method is the easiest ?
• Assuming $$n$$ is sufficiently large, which method is the most efficient to use?

Initial thoughts:

• Brute-forcing the keys $$k1$$ and $$k2$$ would take $$2^{2n}$$, and $$k1{\oplus}k2$$ would reduce it to $$2^n$$ since the resulting key is of lengh $$n$$ if use the second method.
• The first method keeps the complexity of brute-forcing the keys to $$2^{2n}$$, so it seems a bit more robust.
• The third method seems the most robust since it adds a random string $$r$$ to the encryption, and therefore raising the complexity of a cipher text decryption, since not only do we need to figure out $$k1$$ and $$k2$$, we need to have $$r$$ as well to retrieve $$M$$.
• For all the methods, and since we need to use both keys in decryption, the sender and the receiver need to share their respective keys, which could be a drawback in some sense.

Any suggestions or guidance from you guys about that matter would be appreciated. I'm not expecting a straight answer but rather some guidance as to how to tackle this kind of problems. Also feel free to correct me as I am relatively new to cryptography.

• I think you are moving in the right direction, but you should look up Meet in the Middle attacks. – Maarten Bodewes Oct 16 '18 at 23:54
• Compare the operations for efficiency. And, talking about key distribution in this question is not an answer here, compare the three. – kelalaka Oct 17 '18 at 8:15
• @MaartenBodewes thank you sir for your feedback. Traffic interception and MITM attacks might be an issue when it comes to key distribution/sharing. Yet, I need to find a way as to how to figure out some other cipher text C' given the pair (M,C). Any ideas about how to start thinking ? – Joseph Oct 17 '18 at 11:37
• @kelalaka thank you for your feedback. Any ideas about how to further compare the complexity of the encryption in the three methods, especially in the third one ? There is always a trade-off between security and performance, so how do I tackle this ? – Joseph Oct 17 '18 at 12:00
• Meet in the Middle is not Man in the Middle. And "Meat in the Middle" is Raclette. – Maarten Bodewes Oct 17 '18 at 13:08