2
$\begingroup$

The comments in this recent question about the security of 3DES made me wonder if the key complement property of DES (which reduces its security by ~1 bit) can be used in the meet-in-the-middle attack on 3DES.

Can the complexity of the attack be reduced by 1-2 bits by making use of the complement property to rule out more keys than are being directly tested?

Sure, the difference between 112 and 110 bits probably does not matter in practice.

$\endgroup$
  • $\begingroup$ "Sure, the difference between 112 and 110 bits probably does not matter in practice." That kind of depends if it can be combined with other attacks. It certainly would not matter much if it didn't, simply providing a 4 x speedup of something that is practically impossible. $\endgroup$ – Maarten Bodewes Feb 20 '16 at 14:21
4
$\begingroup$

yes,it is possible because in meet in the middle attack on 3DES,see below enter image description here with Complementation Property of DES in red arrow,you can search $2^{55}$ key space instead of $2^{56}$,and for green arrow,you have $DEC_{K2}(ENC_{K1}(M))$ that without key Complementation Property,you need $2^{112}$ operations but with key Complementation Property of left ENC and middle DEC block,you need $2^{110}$ operation and in total you need $2^{55}+2^{110}\approx 2^{110}$ operations

NOTE: in green keyspace(arrow), you should calculate one encryption and then one decryption for your known plaintext,for both decryption and encryption of DES,if you test one pair key($K_{1}$ and $K_{2}$) and calculate the middle variable,because of Complementation Property of DES,you don't need to have a decryption and encryption for $K'_{1}$ and $K'_{2}$ so with every calculate of $DEC_{K2}(ENC_{K1}(M))$,you test 4=$2^2$ keys

$\endgroup$

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.