How can I attack a Triple-Block cipher with 2 keys (like 3DES) with a cost of ≤ 2⁵⁶

Question

I am trying to solve something and I have but I have no idea anymore. Maybe anyone of you has an idea/solution/hint.

Given is a block cipher $F$ with key length $n$. It looks like this: $$c = ENC_{k1}(DEC_{k2}(ENC_{k1}(m)))$$ with key length $2n$. I have to figure out a key recovery attack with $O(2^n)$. There is an additional information that a few plaintext/ciphertext are enough to verify the found keys.

I’ve already been reading some papers like On the security of 2-key triple DES, which describes the van Oorschot-Wiener attack and a generalized method. But even after reading the paper, it seems that the complexity is still larger than $O(2^n)$.

I even had a look for questions which are similar to mine and which might have described better attacks than the van Oorschot-Wiener attack I’m currently fiddling with, but none of them offers a usable answer to what I’m trying to find. For example, in the Q&A “Why is triple-DES using three different keys vulnerable to a meet-in-the-middle-attack?” they are doing a meet-on-the-middle which costs $2^{112}$ operations, which would be $2*keylength$.

The van Oorschot-Wiener attack I’m trying obviously has a lower attack cost. Here it seems that the cost can be reduced to $2^{56}$ but I have no clue how; meaning: even when I use the van Oorschot-Wiener attack and calculate the attack costs for 3DES, I get $2^{57}$ and not $2^{56}$ as expected.

Am I simply missing something somewhere (like: is the $2^{57}$ I’m getting actually correct)? How can the cost of the attack be reduced to $2^{56}$? Or does something better than van Oorschot-Wiener’s attack exist, which enanbles us to attack this scheme with an attack cost $\le 2^{56}$?

What I did so far:

1. I have a couple plaintext/ciphertext pairs. I put them into table 1 and sorted it by the plaintext.
2. For $k1 = 1, ... , 2^{56}-1$ :
   $P_{k1} = DEC_{k1}(A)$ where $A$ is a fixed value.
   Lookup $P_{k1}$ in table 1 and if it is in, take the corresponding C and compute $B=DEC_{k1}(C)$.
   Store $B$ with $k1$ in table 2.
3. For $k2 = 1, ... , 2^{56}-1$ :
   $B_{k2} = DEC_{k2}(A)$
   Lookup $B_{k2}$ in table 2. If it is in, $k2$ and $k1$ are possible candidates.

Step 2 and 3 need each $2^{56}$ computations and if I am not mistaken, this would be $O(2^{57})$. This does not consider the search in the table.

---

Here is the answer to this question. There is an attack based on the following paper: http://cs.jhu.edu/~sdoshi/crypto/papers/p465-merkle.pdf

Here is a visualization on what happens:

Here is the algorithm:

Two things happen in step 1 (a). The decrypted value of 0 is interpreted once a M2 with the key $k_{2}$ and once as $P_{0}$ for the key $k_{1}$. This means with just one operation we get 2 values!

In step 1 (b) the value gets saved in a table with $i$ which represents the key $k_2$, and a label middle. This table will be used for a table look up (TLU) later on.

In step 1 (c) you see there is an $ENC(S^{-1}_{i}(0))$ where $S^{-1}_{i}(0) = M2$ from step 1 (a). This is a CPA request. We ask the algorithm to encrypt the value from the first step. This goes into another decryption $S^{-1}_{i}$, where $i$ represents $k_{1}$.

The value from the previous step is saved in the table with $i$ ($i$ = $k_{1}$) and a label ends.

The last steps should be self explanatory.

The question is: Why is it working? Let's have a look at step 1 (c) again:

$S^{-1}_{i}(Enc(S^{-1}_i(0))) = S^{-1}_{i}(S_{k1}(S^{-1}_{k2}(S_{k1}(S^{-1}_i(0)))))$

You see, that if $i = k1$ we get the following:

$S^{-1}_{i}(Enc(S^{-1}_i(0))) = S^{-1}_{k2}(0)$

This is saved in the table and that is the reason why we look for adjacent entries in the table with the labels.

Complexity:

1. The for loop goes from 1 to n: $O(2^n)$
2. Within the loop we have $2^n$ CPA requests
3. Space: When I am not mistaken: $O(2^{2n})$

I hope it helps some people :)

Answer 1

As far as I know your attack is the best attack known, unless something better has very recently been published.

Please note that for DES as the basic cipher the chosen $A$ may not work, but you can choose another $A$ and try again

Also, for a generic cipher with $k$ bit key, the complexity is $$2^{k+1}=2\times 2^k=O(2^k),$$ as $k$ increases.