9
$\begingroup$

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: Visualization

Here is the algorithm:
Algorithm to attack

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 :)

$\endgroup$
1
  • $\begingroup$ Correction: space is $O(2^n)$ as well. In general, the space used by an algorithm is bounded by the time used (as it requires a unit of time to use a unit of space, hence if we use $k$ units of time, we can use at most $k$ units of space. $\endgroup$
    – poncho
    Commented Dec 21, 2016 at 18:07

1 Answer 1

7
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Thank you for the answer. Why is it actually $O(2^k)$ and not $O(2^{k+1})$? $O(2^{k+1})$ is 2 times more operations than $O{2^{k}}$. Why would I split it up like you did? $\endgroup$
    – Donut
    Commented Dec 17, 2016 at 10:20
  • $\begingroup$ $f(n)$ is $O(g(n))$ if it obeys $f(n)\leq c g(n)$ for some positive constant $c$ and all large enough $n$. $\endgroup$
    – kodlu
    Commented Dec 18, 2016 at 3:40
  • $\begingroup$ Thank you for the clarification. I am still not sure about the solution because I see the following problem. What if the $P_{k1}=DEC_{k1}(A)$ does not hit any of the plaintext in table 1 for all $k1$ ? $\endgroup$
    – Donut
    Commented Dec 18, 2016 at 22:19
  • $\begingroup$ Good observation, this is exactly why I said you might need to try another $A$. $\endgroup$
    – kodlu
    Commented Dec 18, 2016 at 22:36
  • $\begingroup$ Alright, thank you very much. In about 2 days I know the expected solution and I will post it then here. I guess it will be for everyone nice to see. $\endgroup$
    – Donut
    Commented Dec 18, 2016 at 23:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.