Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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?
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).
