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$
  • $\begingroup$ did you try the brute force? $\endgroup$ – kelalaka Jan 4 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 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 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$ – user3343396 Jan 4 at 18:54
  • $\begingroup$ your question is fully answered in Biham's slides. $\endgroup$ – kodlu Jan 4 at 21:42
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$
  • 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 at 17:59
  • $\begingroup$ S, E and P are known to the attacker? only the key is secret? $\endgroup$ – user3343396 Jan 4 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 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$ – khan Jan 4 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 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.