# 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 complementation property of $$DES$$; I had thought that it actually predated Biham and Shamir's work.

In any case, your questions:

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). – Maarten Bodewes Aug 21 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.