2DES and 3DES against a DES build with complimentary

Question

I saw this complicated question and I am not really sure about it, would appreciate your view on it.

Is the following build stronger than 2DES or 3DES with 2 different keys (or even normal DES)?

$DES(DES(x,k),\overline{k})$

what I think is that in regards to a $2^{56}$ key space, we need to perform the following:

• regular DES: we need to schedule the key $k$, and then test $E(k,m),k'$;

• regarding 2DES/3DES with two different keys: unsure, but I think that in this case we need to schedule $k_1 = k$ and $k_2 = \overline{k}$. I would appreciate seeing how to properly decide if it makes it a stronger build than those (2DES,3DES - both with two different keys).

For simplicity sake (and question sake) assume that the adversary has a small amount of known plaintext:ciphertext pairs.

Answer 1

Is the following build stronger than 2DES or 3DES with 2 different keys (or even normal DES)?

$DES(DES(x,k),\overline{k})$

It is only slightly stronger than DES; it is considerably easier to attack than 2DES or 3DES.

The most practical attack against DES is brute force; simply try the various possible keys until you stumble on the correct one. With a known plaintext/ciphertext pair, this takes an expected $2^{55}$ DES evaluations.

Against your design, because the key is still only 56 bits, this brute force method is still practical. In your case, this takes an expected $2^{56}$ DES evaluations.

We generally don't know the attacker's capability to that much precision, a factor of 2 increase in the work effort is well below our uncertainly (and hence are effectively the same).

In contrast, 2DES can be attacked with the same approximate work effort; however the algorithms that do that require a significant amount of memory, and are harder to parallelize (and hence are, in practice, more difficult to do).

Also, if you think that your design forces two DES key schedules for every DES key tested, that turns out not to be the case. Because of the DES key complementation property, we have:

$$DES(DES(x,k),\overline{k}) = \overline{ DES( \overline{ DES(x, k) }, k)}$$

Hence, a key can be tested by performing two DES evaluations on the same key, and an intermediate complementation.