2
$\begingroup$

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

enter image description here

I understand why this equation takes place:

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

EDIT: The function f looks like this: enter image description here

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

I saw it's possible in a few references:

http://www.cs.technion.ac.il/~cs236506/04/slides/crypto-slides-05-bc-tutor.4x2.pdf http://people.scs.carleton.ca/~maheshwa/courses/4109/Seminar11/atttack%20on%20DES.pdf https://www.icg.isy.liu.se/courses/tsit03/forelasningar/cryptolecture04.pdf KPA on Feistel cipher?

Thanks!

$\endgroup$
6
  • $\begingroup$ did you try the brute force? $\endgroup$
    – kelalaka
    Jan 4, 2019 at 16:03
  • 1
    $\begingroup$ 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.. $\endgroup$
    – fgrieu
    Jan 4, 2019 at 16:11
  • 1
    $\begingroup$ 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. $\endgroup$
    – Maeher
    Jan 4, 2019 at 17:07
  • $\begingroup$ @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 :) $\endgroup$ Jan 4, 2019 at 18:54
  • $\begingroup$ your question is fully answered in Biham's slides. $\endgroup$
    – kodlu
    Jan 4, 2019 at 21:42

1 Answer 1

1
$\begingroup$

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.

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

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.