4
$\begingroup$

My Question is based on poncho's answer in this post.

If you're doing a meet-in-the-middle attack against 2DES with only on a plaintext-ciphertext pair $(P,C)$, I understand that the expected amount of remaining key candidates is $2^{48}$, assuming that DES encryption/decryption yields a random 64-bit block if done with a wrong key.

What makes me curious now is: if you have another plaintext-ciphertext pair $(P',C')$ to validate the candidates, what is the probability that a wrong key still remains?

So my approach is the following: We just start a new attack, with the reduced key set. Since there are only $2^{48}$ keys left, the possibility of a specific block is $\frac{2^{48}}{2^{64}}$ which is $2^{-16}$. Is this is already the possibility I'm looking for? If yes, then this leads me to the conclusion that despite the probability of one specific block is very small, there are still $2^{48} * 2^{-16} = 2^{32}$ candidates in the set!

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

Yes your argument is correct, to an excellent approximation.

The reason I say approximation is that the second search in the sample space should really be conducted in the restricted set of DES permuataions that already map $P$ to $C$ (sampling without replacement) but for such a huge sample space the inaccuracy due to not doing this is likely much much less than the modelling step of assuming DES is a pseudorandom permutation.

Improve this answer
$\endgroup$
1
  • $\begingroup$ So I asked my crypto teacher about this and she told me $2^{32}$ is wrong, because we we have $2^{48}$ key candidates (pairs) left. So every key of the first set only maps to one of the other set, since they matched. This was not the case in the first run of the attack, where every key could map to any of the $2^{56}$ of the other set and we didn't knew which one. So $2^{-16}$ is the probability of a wrong key remaining in the set. Only my conclusion $2^{48} * 2^{−16}=2^{32}$ is wrong, but I still don't get why ... $\endgroup$
    – Alexander Grass
    Oct 20, 2018 at 18:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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