# 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, 2014 at 14:11
• yeah, its a typo. I will correct Sep 22, 2014 at 14:34

This is known as the 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 $$S$$-Boxes arbitrarily. The reason for this is that it is not actually caused by the $$S$$-Boxes. $$DES$$ generates the inputs to the $$S$$-Boxes by $$XOR$$ing $$R_i$$ with $$k_i$$. The reason this property holds is if you complement $$R_i$$ with $$k_i$$, the result of the $$XOR$$ won't change, and so the input the to $$S$$-Box is exactly the same (and hence the output of the $$S$$-Box is exactly the same).

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 ciphertexts for 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, wherever $$P_1$$ has a $$0$$ bit, $$P_2$$ has a $$1$$ bit, or in other words, $$\overline{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_{\overline{k'}}(\overline{P_1})} = \overline{E_k(P_2)} = \overline{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.

• A rather extensive edit has been proposed for this text. Poncho, could you have a look at it instead of letting the community decide? I see value in it, but it also removes an entire sentence from the answer, which makes it hard for me to accept the edit (from the review queue). Aug 21, 2019 at 11:09

I would like to add my own view/explanation on that problem based on the textbook you provided. We will follow the provided explanation:
Reminder $$\overline{DES_k(P_1)} = DES_\bar{k}(\overline{P_1})$$

For all {k'} such that $$k\in$$ {all Keys with last bit is 0}
1.if $$DES_{k'}(P_1) = C_1$$ we have the k
2.if $$DES_{k'}(\bar{P_1}) = \overline{C_1}$$ we have the coplement key i.e the real key is the opposite

We are iterating on all domain of keys with last bit 0.
The key can have 1 or 0 as the last bit.
if the real key has 0 at the end we must find it in first condition (we check all domain)
if the real key has 1 at the end we must find it in the second condition because the complementary of such key must have 0 at the end and we are iterating on all domain.