Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I was reading upon Biham and shamir's paper and a fact has been presented over there - if $ P1 = \overline P2$ and I choose a key $K1 = \overline K2$ then in that case $$T1 = DES(P1, K1)$$ $$T2 = DES(P2, K2)$$

then $T1 = \overline T2$ . 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 T2 only if I P2 was inserted with $\overline K$. And clearly I am entering P1 (which is $\overline P2$) hence the output can never be T2. Please correct.

enter image description here Thanks

share|improve this question

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer
    
Thanks Poncho, I was doing it wrongly. –  codeomnitrix Sep 11 at 1:48

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.