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 ?


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.


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 1, 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.

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

  • 1
    $\begingroup$ Let me help you over that 3k border :) $\endgroup$ – Maarten Bodewes Nov 17 '18 at 12:30

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.