3
$\begingroup$

I know that MITM can break three keys into two parts $(K_1,K_2)$ and $K_3$ where the worst time complexity is $2^{112}$.

My questions is whether we are able to break three keys $(K_1,K_2,K_3)$ into three different parts, then starts to attack each key independently? If we can, will the time complexity and space usage both be $O(2^{56})$? assuming each key size is $56$ bits.

$\endgroup$
1

1 Answer 1

2
$\begingroup$

No, we are not able to break 3-keys 3-DES encryption using something similar to Meet-in-the-Midle with cost much lower than $2^{112}$ encryptions; much less triple encryption in general.

In the case of triple encryption with 3 k-bit keys in general, in order to apply MitM, we'd need to group 2 keys together on one side, thus would have cost $O(2^{2k})$ for this half. There's even a formal proof, see this. The space complexity of that MitM remains $O(2^k)$ blocks, since we can chose to pre-compute the values for the side with the shortest key, then perform the search with the other half.

In the case of DES, we know the structure and can open the block cipher, and in particular break the middle cipher into two halves of 8 rounds. However, each of these haves still receives all the keys bits of the midle DES, therefore we can't use that to reduce the complexity of plain MitM to $2^{56+28}$ encryptions on each half, as we could if 28 key bits went exclusively to the first 8 rounds, and the 28 other bits exclusively to the last 8 rounds.

Notice that clever attacks exist against 2-keys 3-DES, and are nearly practical; see this.

$\endgroup$
2
  • $\begingroup$ if we need to group 2 keys together, will the space complexity also be O(2^2k)? $\endgroup$ Oct 14, 2016 at 6:32
  • $\begingroup$ @Zhongce Lewis Xie. Welcome to crypto.se! I have hopefully addressed your comment (if so, it is a good idea to remove it, as any obsolete comment). Notice that on crypto.se you can nicely typeset formulas, including in comments; $O(2^{2k})$ is written $O(2^{2k})$. More there. $\endgroup$
    – fgrieu
    Oct 14, 2016 at 6:44

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.