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:
- I have a couple plaintext/ciphertext pairs. I put them into table 1 and sorted it by the plaintext.
- 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. - 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:
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:
- The for loop goes from 1 to n: $O(2^n)$
- Within the loop we have $2^n$ CPA requests
- Space: When I am not mistaken: $O(2^{2n})$
I hope it helps some people :)