# One-round feistel network (DES) attack

I can't find out how to break 1 round of feistel network (obtaining the key).

I understand why this equation takes place:

$$R_1 \oplus L_0 = f(R_0, k_1)$$

EDIT: The function f looks like this:

But how can i find the key ($$k_1$$) from it?

I saw it's possible in a few references:

Thanks!

• did you try the brute force? Jan 4, 2019 at 16:03
• There are several definitions of breaking a cipher. Obtaining the key is only one, and often is inappropriate. Others include ability to decipher any ciphertext, breaking indistinguishability of ciphertext from random for chosen plaintext..
– fgrieu
Jan 4, 2019 at 16:11
• In general you cannot. Let f be a constant function then the output is independent of the key. So you need to make assumptions about the function f if you want to extract the key. Jan 4, 2019 at 17:07
• @kelalaka - you can always brute force, im looking for a smart solution. fgrieu - as i said, i want a smart way to obtain the key Maeher - i know there is a solution :) Jan 4, 2019 at 18:54
• your question is fully answered in Biham's slides. Jan 4, 2019 at 21:42

## 1 Answer

Since

$$X' = F(X, k) = P(S(E(X) \oplus k ))$$

the value of key $$K$$ is an element of the set

$$\{V \oplus E(R_0): V \in S^{-1}(P^{-1}(Z)) \}$$

where

$$Z = R_1 \oplus L_0$$

and

$$S^{-1}(P^{-1}(Z))$$ is the set of possible inverse images of the parallel map of the Sboxes $$S$$ which is not one to one.

Total number of possible keys is $$2^{16}$$ because Sboxes are not bijective, there are $$4$$ possible inputs leading to same output.

• Do you have some particular reason for assuming that the OP's function $f$ would be of this form? Jan 4, 2019 at 17:59
• S, E and P are known to the attacker? only the key is secret? Jan 4, 2019 at 18:45
• @khan - if what you are saying is true, we can break a 16 rounds des also. according to the references that i mentioned in my edit, the number of possibilities is 2^16 Jan 4, 2019 at 19:06
• no you cant, because normally you know plaintext and ciphertext, not the intermediate states after every single round so you can not break 16 rounds of DES this way. Jan 4, 2019 at 19:12
• @khan - if im getting you right, it's because if i have L16 and R16 i can't find K16 because i don't know R15 and L15? Jan 4, 2019 at 19:17