0
$\begingroup$

I am learning the meet-in-the-middle on DES attack. I understood the basic logic behind how it is performed; however, one further question is: why can we guarantee to find one and only one pair of k1 and k2?

One step further, how DES guarantee that by taking the same plaintext and different secret key, the encrypted outputs can never be the same?

$\endgroup$
  • $\begingroup$ Welcome to Cryptography. You are asking two completely different questions in one post. Please visit our help center $\endgroup$ – kelalaka Aug 28 '19 at 14:04
5
$\begingroup$

I am learning the meet-in-the-middle on DES attack.

I don't know of any meet-in-the-middle attack on DES; I'll assume you're talking about 2DES (where you apply DES with one key $k_1$, and then apply another iteration of DES (possibly in decrypt mode) with another key $k_2$.

why can we guarantee to find one and only one pair of k1 and k2?

We don't. In fact, if we're just looking at a single plaintext/ciphertext block, there are likely to be circa $2^{48}$ $k_1, k_2$ pairs that map that plaintext block into that ciphertext block.

That is not a major obstacle; what we typically assume is that we have a second plaintext/ciphertext block that can be used for validation; given a candidate $k_1, k_2$ pair, we try those keys on our second plaintext block (and see if we get the second ciphertext block). If it passes that, then it is most likely the correct $k_1, k_2$ pair.

This second check (which we may need to perform $2^{48}$ times) is less costly than the original MITM search, and so we mostly ignore that cost when estimating the cost of the attack.

One step further, how DES guarantee that by taking the same plaintext and different secret key, the encrypted outputs can never be the same?

It doesn't; we generally assume that differing keys define different DES permutations (and so two different keys can map the same plaintext block into the same ciphertext block).

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you for the answer. Just a followup question, can one-time-pad guarantees that taking the same plaintext and different secret key, the encrypted outputs can never be the same? I think so. $\endgroup$ – lllllllllllll Aug 29 '19 at 1:41
  • $\begingroup$ @lllllllllllll: About your additional question in the comment: The outputs are the same if and only if their (bitwise) xor is 0. Can you express this xor using the plaintext and both secret keys? $\endgroup$ – j.p. Aug 29 '19 at 6:26

Your Answer

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

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