One-round feistel network (DES) attack

Question

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!

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. — Maeher, 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 :) — user3343396, Jan 4, 2019 at 18:54

crypt · Accepted Answer · 2019-01-05 07:15:07Z

1

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.

answered Jan 4, 2019 at 16:13

crypt

2,39717 silver badges31 bronze badges

1

$\begingroup$ Do you have some particular reason for assuming that the OP's function $f$ would be of this form? $\endgroup$
– Ilmari Karonen
Jan 4, 2019 at 17:59
$\begingroup$ S, E and P are known to the attacker? only the key is secret? $\endgroup$
– user3343396
Jan 4, 2019 at 18:45
$\begingroup$ @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 $\endgroup$
– user3343396
Jan 4, 2019 at 19:06
1

$\begingroup$ 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. $\endgroup$
– crypt
Jan 4, 2019 at 19:12
$\begingroup$ @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? $\endgroup$
– user3343396
Jan 4, 2019 at 19:17

| Show 8 more comments

1 Answer 1