3
$\begingroup$

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.

enter image description here

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – otus Sep 21 '14 at 14:11
  • $\begingroup$ yeah, its a typo. I will correct $\endgroup$ – codeomnitrix Sep 22 '14 at 14:34
5
$\begingroup$

This is known as the "key 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 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.

$\endgroup$
0
$\begingroup$

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.

$\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.