# DES with the bitwise complement of a key

I was reading upon Biham and Shamir's paper and a fact has been presented over there: if $P_1 = \bar P_2$ and I choose a key $K_1 = \bar K_2$ then in that case $$T_1 = DES(P_1, K_1)$$ $$T_2 = DES(P_2, K_2)$$

then $T_1 = \bar T_2$ . Does this hold for only that particular combination of S-box or it will be same for any S-box combination. I mean if I change S-boxes randomly then will it still be same?

Also there is one more thing mentioned on the paper, but I am not able to get it. PFB the image.

Here output $T$ will be $\bar T_2$ only if I $P_2$ was inserted with $\bar K$. And clearly I am entering $P_1$ (which is $\bar P_2$) hence the output can never be $T_2$. Please correct.

-
Please add a reference to the paper. Regarding your second question, the quote says $T=\overline T_2$, not $T=T_2$. Did you misread or is there a typo in your question? – otus Sep 21 '14 at 14:11
yeah, its a typo. I will correct – codeomnitrix Sep 22 '14 at 14:34

This is known as the "key complementation" property of DES; I had thought that it actually predated Biham and Shamir's work.

Does this hold for only that particular combination of s box or it will be same for any S-box combination

It'd remain even if you change the sbox's arbitrarily. The reason for this is that it is not actually caused by the sboxes. Instead, DES generate2 the inputs to the sbox's by exclusive-oring bits from the data block with bits extracted from the key. The reason this property holds is if you invert the data block and the key bits, the result of the exclusive-or will remain the same, and so the input the to sbox is exactly the same (and hence the output of the sbox is exactly the same). And, we end up exclusive-oring the output of the sbox into other data bits; that operation would preserve the key complementation property.

Also there is one more thing mentioned on the paper, but I am not able to get it.

Actually, that's a fairly straight-forward exploit of this property. I'll see if I can state it more explicitly.

Suppose you knew the encryption of two plaintexts, and these plaintexts happened to be the complement of each other. That is, we know the value $T_1 = E_k(P_1)$ and we also know the value $T_2 = E_k(P_2)$, where $P_1$ and $P_2$ are complements of each other (that is, whereever $P_1$ has a 0 bit, $P_2$ has a one bit, or in other words, $\bar{P_1} = P_2$

Consider further that we don't know the key $k$; and we'd like to find it.

One thing we can try is pick a random key $k'$, and do a trial encryption of $P_1$ with it. If our $k'$ just happened to be the value $k$, then $E_{k'}(P_1)$ would be $T_1$, and so we know know that $k'$ is likely to be the correct value.

However, consider if our $k'$ is the complement of $k$ (that is, we got every bit wrong). In that case, the key complementation property would hold, and we would have $E_{k'}(P_1) = \overline{E_{\bar{k'}}(\bar{P_1})} = \overline{E_k(P_2)} = \bar{T_2}$, that is, we would see the bitwise complement of $T_2$. So, if we see that value, that also tells us what the key is likely to be.

Hence, by doing a single DES encryption, we can actually test two keys -- that's what Biham and Shamir are pointing out.

-
Thanks Poncho, I was doing it wrongly. – codeomnitrix Sep 11 '14 at 1:48