15
$\begingroup$

Looking at the design for Feistel ciphers, they use a list of round keys which are generated from the main key using the key schedule of the associated block cipher. Some block ciphers need this as to prevent repetition, but why does a Feistel network need it?

Feistel Network

If $F$ is a good PRF, then the output should be indistinguishable from random after the first few rounds. Under the random oracle model, one would expect that $L_0$ is made pseudorandom after the first round, then $R_0$ is made pseudorandom right after that. Continuing this should never return you back to the plaintext in a reasonable amount of time.

So my question is why are round keys used in the Feistel network as opposed to making all the round keys the same? Did I get anything wrong in my reasoning?

Improve this question
$\endgroup$
1
  • 9
    $\begingroup$ Because a square key won't fit the keyhole. *baddum-tsh* $\endgroup$
    – David Richerby
    Commented Jun 20, 2017 at 18:42

3 Answers 3

Reset to default
13
$\begingroup$

Iterated ciphers need variability between rounds to resist so callad Slide attacks. One common way to thwart this attack is with a key schedule generating different round keys for each round.

Slide attacks exploit the repeating rounds of the cipher by finding a collision between one input plaintext and the intermediate value after one round of encryption of some other plaintext. This collision gives a "slid pair" and gives the attacker two known input/output pairs of the round function which in many cases is enough to recover at least parts of the key.

In the question we have a balanced Feistel cipher where every round uses the same round function and key. Due to the birthday paradox we expect to find a slid pair with on the order of $2^{n/4}$ chosen plaintexts or $2^{n/2}$ known plaintexts, breaking the cipher.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ It might be good to specify that n is the block length (versus the number of rounds), so for a cipher that operates on 128-bit blocks, about 4 billion chosen plaintexts would suffice. Another issue is that in any given round, there will often be some keys where repeated iterations of the Feistel network will yield a rather short cycle of values. If every round does something different with keys, some rounds may have weak keys but there will still be a useful number of rounds with strong keys. $\endgroup$
    – supercat
    Commented Jun 20, 2017 at 22:03
12
$\begingroup$

This is due to Luby and Rackoff's proof about Feistel networks. The proof assumes the PRFs are independent. See sections 4.5 and 5 of How to Construct Pseudorandom Permutations from Pseudorandom Functions (paywall).

Simply using the same key for four rounds is not secure, but there are other ways to key with fewer than four round keys which are secure, see e.g. How to Construct Pseudorandom Permutations from Single Pseudorandom Functions or The Characterization of Luby-Rackoff and Its Optimum Single-Key Variants (the latter paywalled).

Improve this answer
$\endgroup$
2
  • 3
    $\begingroup$ Is using the same key proved not secure, or not proved secure? $\endgroup$
    – OrangeDog
    Commented Jun 20, 2017 at 11:02
  • 4
    $\begingroup$ @OrangeDog, proved insecure. I think a proof is in the second reference above. $\endgroup$
    – otus
    Commented Jun 20, 2017 at 11:45
6
$\begingroup$

It does not make sense to say that any fixed function $F$ "is a good PRF". A distribution on functions can, however, be pseudorandom (indistinguishable from the uniform distribution over the set of all functions).

Therefore, it makes sense to consider keyed functions to emulate a random oracle.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I think the question is why do we a different key for each round instead of the same key for each round. $\endgroup$
    – Paŭlo Ebermann
    Commented Jun 20, 2017 at 19:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.