DES - encrypt 3 times - DES(DES(DES, k), k'), k) - stronger than 2DES with 2 different keys?

Question

What if were to use DES in the following way:

For a given plaintext x and key k we will perform: DES(DES(DES, k), k'), k), where k' is the complementary of k.

If an adversary has a small amount of text and their ciphertexts, would he still have to run 3 * 2^56 encryptions: for each key perform DES(DES(DES, k), k'), k) and therefore this encryption is stronger than 2DES with 2 keys (meet in the middle requires 2^57 runs) but less than real 3DES which is much more than 2^57 ?

Or is there a smarter way ?

Answer 1

As pointed out in the comments two key triple DES (without your complementary key condition) already has efficient attacks against it, going back to the 80's. See for example a detailed analysis in Van Oorschot and Wiener here which converts a chosen plaintext attack by Merkle and Hellman to a known plaintext attack.

Since 2 key 3DES is already weak, trying for sophisticated and complicated improvements based on the complementary key condition is likely not worth the effort.

Answer 2

Let assume that running a single DES key search operation requires 1 key schedule, encryption, and 1 comparison that now we omit.

for key in 2^56
    k = key_schedule(key)  //note to distingush the key schedule has a funtion
    test (E(k,m), c)

Your 3DES requires3 encryptions, only 2 schedule runs if we want to attack brute-force. The key space is still $2^{56}$ since we don't need a sperate key search for the complement $k'$, just complement the current key and run the key schedule.

for k in 2^56
   k1 = key_schedule(k)
   k2 = key_schedule(k')
   test ( E(E(E(m,k1),k2),k1), c)

So in, the total we need at most 3-times single DES operations and 2-times DES key schedules. If we assume that the running time of the key schedule and the encryption are same, then your 3DES is $5/2=2.5$ slower than brute-forcing a single DES.

---

Now, turn into 2DES with two different keys. In the complexity calculations of the meet-in-middle attack the big $\mathcal{O}$ notation hides some details;

1. A memory for a table requirement for storing the encryption with each key; we need to store $6\cdot 2 \cdot 2^{56}$-byte $\approx 1152$ PetaByte. This is still very huge amount to store and process. Google has 15 exabytes = 15000 petabytes.
2. Sorting the table $n \log n$ step, therefor we have $ 56 \cdot 2^{56}$
3. Searching within the table $56$ steps by binary search.

When these values are added ¹, 3DES search will be faster than the 2DES, and can be calculated by using in quite reasonable time if you can access the Titan, you can brute-force in couple hours. The Titan that can reach $2^{60}$ every easily.

---

¹ I would like to note here that, DES encryption and sorting cannot be directly compared. A deeper calculation is required.