2
$\begingroup$

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.

Added

Tylo has pointed out that the $F$ function is to be treated as a black box.

Updated

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?

Improve this question
$\endgroup$
7
  • 2
    $\begingroup$ "[I'm] not at all sure whether I am on the right path"; you are on the right path. If you know $F(R_0, K_0)$ and $R_0$, how can you recover $K_0$? Hint: look at the details of $F$. $\endgroup$
    – poncho
    Feb 18, 2014 at 14:50
  • $\begingroup$ Try multiple inputs with the same $R_0$ or $L_0$ and looking for a pattern. $\endgroup$
    – David Cash
    Feb 18, 2014 at 14:50
  • 2
    $\begingroup$ Also, you have a number of plaintext/ciphertext pairs (and hence multiple $F(R_0, K_0)$, $R_0$ pairs. How can you use these multiple sets to make recovering $K_0$ even easier? $\endgroup$
    – poncho
    Feb 18, 2014 at 15:10
  • $\begingroup$ @Poncho: "Look at the details of F": Do you mean the 4-stage process of expansion, key mixing, substution, and permutation in the Feistel function? $\endgroup$
    – David Brower
    Feb 18, 2014 at 15:30
  • 1
    $\begingroup$ You might want to read the exercise carefully enough, I think they are looking for a different solution: " ... consider the DES F function as a black box that takes two inputs" and "... converted into a distinguishing attack ..." $\endgroup$
    – tylo
    Feb 18, 2014 at 17:10

1 Answer 1

Reset to default
2
$\begingroup$

Your Formulas are alright, but there is some additional information from the exercise/setup:

The exercise states, that $F$ should be considered as a blackbox (otherwise you could use the internal stages of $F$, as poncho already suggested). However, as I understand it you can stil evaluate $F$ on any input of your choice.

At this point, you can do a couple of things. First, you're already done without knowing it. As a hint: Read the goal of the exercise and compare the complexity with a brute force on your formulas. You only need 1 ciphertext/plaintext pair.

A more complex idea: If you have a lot of ciphertext/plaintext pairs, and you just want to distinguish the permutation from a random oracle, then you can do the following: Look for two plaintexts, where $R_0$ (32 bit) is equal. What happens then to the output? And what would happen in a truly random permutation? This is a distinguishing criteria.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Presumably I am not able to run an exhaustive search on all possible 48-bit keys since I am not able to call F directly? I'm only about 6 weeks into learning about encryption and am still taking baby steps. $\endgroup$
    – David Brower
    Feb 19, 2014 at 16:42
  • $\begingroup$ Usually black box means, that you have no idea about the internal algorithm (and therefore can't exploit one of its weaknesses), but it does not mean you can't evaluate the function. So yeah, as I understand it, exhaustive search on the 48 bits of $K_0$ and afterwards on the 48 bits of $K_1$ should give you the key in $2 \cdot 2^{47}$ steps (lower than brute force on 56 bit DES). In order to make this an distinguishing attack, you can break the key of one text pair, and try to encrypt other plaintexts with this key. If the results are equal to the according ciphertexts, you got the cipher. $\endgroup$
    – tylo
    Feb 19, 2014 at 17:13
  • $\begingroup$ But probably the preferred solution is the other attack from my second hint. It has much less complexity than $2^{48}$, too. $\endgroup$
    – tylo
    Feb 19, 2014 at 17:15
  • $\begingroup$ I'm afraid I've come to a dead end. $\endgroup$
    – David Brower
    Feb 20, 2014 at 16:49
  • 1
    $\begingroup$ Try to think differently, no need to call $F$ directly, if you have many pairs of ciphertext/plaintext. If you have $x$ of these pairs, then there are $x(x-1)/2$ ways to compare two of those. So if $x(x-1)/2$ is greater than $2^{32}$, there should be two plaintexts, which share the same $R_0$. And with this, you can distinguish between this cipher and a truly random permutation. $\endgroup$
    – tylo
    Feb 20, 2014 at 19:09

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.