Working through the exercises in Cryptography Engineering (Schneier, Ferguson & Kohno) I have stalled on the following exercise:
Consider a new block cipher, DES2, that consists only of two rounds of the DES block cipher. DES2 has the same block and key size as DES. For this question you should consider the DES F function as a black box that takes two inputs, a 32-bit data segment and a 48-bit round key, and that produces a 32-bit output.
Suppose you have a large number of plaintext-ciphertext pairs for DES2 under a single, unknown key. Give an algorithm for recovering the 48-bit round key for round 1 and the 48-bit round key for round 2. Your algorithm should have fewer operations than an exhaustive search for an entire 56-bit DES key. Can your algorithm be converted into a distinguishing attack against DES2?
With regards to the first sub-exercise ("Give an algorithm…"), I have proceeded in the following way:
If I assume an initial input of 64 bits giving us two 32-bit blocks $L_0$ and $R_0$, I know that after the first round we have
$L_1 = R_0$
$R_1 = L_0 \oplus F(R_0, K_0)$
Then, after the second round, we have:
$L_2 = R_1 = L_0 \oplus F(R_0, K_0)$
$R_2 = L_1 \oplus F(R_1, K_1) = L_1 ⊕ F(L_0 ⊕ F(R_0, K_0), K_1)$
My thought was that I could then XOR $L_2$ with $L_0$ which is the output of $F(R_0, K_0)$ and then use $R_0$ to retrieve $K_0$. But I'm not sure how to do that… and not at all sure whether I am on the right path.
Any thoughts would be greatly appreciated.
Tylo has pointed out that the $F$ function is to be treated as a black box.
I’m afraid that I have come so close but can’t seem to get any further. I can get the output of $F(R_0, K_0)$ and I know $R_0$. But I just don’t know how, since I can’t call $F$ directly I don’t know how to get the 48-bit $K_0$.
Can anyone help?