# Proving DES complementation property: y = DES(k,x) ⟹ /y = DES(/k, /x)

Below is my proof for this. I was not sure if this is correct and was also a little confused regarding the complementarity property of DES. Does this property mean there is a serious vulnerability in the use of triple-DES as a pseudorandom permutation?

Let $$F$$ be DES mangler. Need to show $$\overline{F(k, x)} = F(\overline k, \overline x)$$

Let $$E$$ be the expansion function, meaning the input to the S-boxes equals $$E(x) \oplus k$$.

Due to the fact that $$E$$ duplicates half of its input bits, $$E(\overline x) \oplus \bar k = \overline{E(x)} \oplus \overline k = E(x) \oplus k$$

Since this doesn't change the S-box input, its S-box output is also the same. The mixing permutation can't change the output.

Inputting $$L_0$$, $$R_0$$, and $$k$$, we get $$L_1=R_0$$ and $$R_1 = \overline{L_0} \oplus F(\overline k, \overline{R_0})$$.

After round $$i$$, the result will be $$\overline{L_i}$$ and $$\overline{R_i}$$ when the input was $$\overline{L_{i-1}}$$ and $$\overline{R_{i-1}}$$ and using $$\overline{k}$$: \begin{align} L_i &= R_{i-1} \implies \overline{L_i} = \overline{R_{i-1}}\\ \overline{R_i} &= \overline{L_{i-1}} \oplus \overline{F(k_i, R_{i-1})} = \overline{L_{i-1}} \oplus F(k_i, R_{i-1}) =\overline{L_{i-1} \oplus F(k_i, R_{i-1}))} \end{align}

Therefore, $$\overline{F(k, R)} = F(k, R)$$ since the complement of expansion $$R$$ and $$\overline{k}$$ are XORed to eliminate the complement.

The, the final result will be $$\overline{y}$$ using $$\overline{m}$$ as input and $$\overline{k}$$ as key, without being changed by permutation.

Hence, $$y = \operatorname{DES}(k, x) \implies y' =\operatorname{DES}(k', x')$$

END OF PROOF

I am not sure if this is correct. If it isn't can you show me what would be correct?

• Please check the edit for correctness. Commented Apr 13 at 7:28

Remarks on the proposed proof that outgrew a comment:

1. The notation $$F$$ is used for the whole DES encryption, and for some other internal function, confusing the reader. Please use $$\operatorname{DES}$$ instead of $$F$$ when applicable (rather than "mangler"; or define that, if it's a different thing, e.g. $$\operatorname{DES}$$ less input permutations and output permutation).
2. The statement « the input to the S-boxes equals $$E(x)\oplus k$$ » does not use $$k$$ or $$x$$ with the same meaning as in the line just above, also confusing the reader.
3. The statement « $$E$$ duplicates half of its input bits » at least does not use the standard definition of $$E$$.
4. In the above considerations, it's disregarded DES's $$\operatorname{PC1}$$, key rotations, and $$\operatorname{PC2}$$.
5. With the text « Inputting $$L_0$$, $$R_0$$, and $$k$$ » it looks like we compute $$\operatorname{DES}(k,x)$$. Fine if we managed to prove that's $$\overline{\operatorname{DES}(\overline k,\overline x)}$$, and then concluded. But that conclusion step is missing. Or perhaps we are computing $$\operatorname{DES}(\overline k,\overline x)$$ (that's how the end of the proof given goes)?
6. In the above considerations, it's disregarded DES's initial and final permutations $$\operatorname{IP}$$ and $$\operatorname{FP}=\operatorname{IP}^{-1}$$.
7. Whatever non-degenerate $$F$$, the statement « $$\overline{F(k, R)} = F(k, R)$$ » can't be right.
8. For the part involving rounds, the formal way would use induction, which is suggested but not detailed (probably acceptable). Another way would be making the computation for the first round then « similarly for the next 15 rounds » and give the result after the last round.

Possible proof sketch:

• Let $$k$$ be a DES key and $$x$$ be a DES block. Let $$k'=\overline k$$ and $$x'=\overline x$$. We'll compares values occurring while computing $$y'=\operatorname{DES}(k',x')$$ to that occurring while computing $$y=\operatorname{DES}(k,x)$$.
• $$\forall i\in\{1,2,\ldots,16\}$$ the subkeys $$k'_i$$ verify $$k'_i=\overline k_i$$ (involves $$\operatorname{PC1}$$, values of $$C$$ and $$D$$ registers, $$\operatorname{PC2}$$)
• $$\forall i\in\{0,1,\ldots,16\}$$ the left and right blocks verify $$L'_i=\overline L_i$$ and $$R'_i=\overline R_i$$ (proof by induction; initialization involves $$\operatorname{IP}$$, induction involves some of the calculations in the existing proof)
• Thus $$y'=\overline y$$ (involves $$\operatorname{FP}$$).

Does this property mean there is a serious vulnerability in the use of triple-DES as a pseudorandom permutation?

The property given can be extended to triple-DES. Proof is left as an easy exercise.

When using DES (or triple-DES) with independent random keys, that so-called complementation property is not much of a security issue, because the probability of accidentally generating two keys with one the complement of the other is so low. The worst it goes is that it can be used to halve the key search space in a key enumeration attack (e.g. in a chosen plaintext scenario), reducing the effective key size by 1 bit. Detailing how is left as an exercise.