# Can the key-complement property of DES be used against 3DES?

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.

• "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. Feb 20, 2016 at 14:21

yes,it is possible because in meet in the middle attack on 3DES,see below 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