1
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ I think you are moving in the right direction, but you should look up Meet in the Middle attacks. $\endgroup$ – Maarten Bodewes Oct 16 '18 at 23:54
  • $\begingroup$ Compare the operations for efficiency. And, talking about key distribution in this question is not an answer here, compare the three. $\endgroup$ – kelalaka Oct 17 '18 at 8:15
  • $\begingroup$ @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 ? $\endgroup$ – Joseph Oct 17 '18 at 11:37
  • $\begingroup$ @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 ? $\endgroup$ – Joseph Oct 17 '18 at 12:00
  • 1
    $\begingroup$ Meet in the Middle is not Man in the Middle. And "Meat in the Middle" is Raclette. $\endgroup$ – Maarten Bodewes Oct 17 '18 at 13:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.