3
$\begingroup$

I know that one round of Feistel is not enough for making a PRP (Pseudo Random Permutation) even I know that two round is not enough how about three round of Feistel ? I read a lot but not usefull. here they say becuse of a Luby-Rackoff theorem after three round we have PRP. but here it says that it is not enough?? thank you for answering

$\endgroup$
  • 1
    $\begingroup$ You misread the text you linked. 3 rounds is enough for a PRP, but you need 4 rounds for a strong PRP. $\endgroup$ – CodesInChaos Feb 14 '17 at 19:11
4
$\begingroup$

Wel'll consider a symmetric Feistel cipher with $n$-bit block using ideal independent random functions at each round.

Making it computationally indistinguishable from a random permutation requires some number of rounds depending on the attack model; and on if we are content with asymptotic security for $O(2^{n/2})$ work, or want asymptotic security with more work, or want security for a prescribed small $n$.

Classical results for asymptotic security with $O(2^{n/2})$ work:

  • under random known plaintext, we need 2 rounds;
  • under chosen plaintext (that is, assuming an encryption oracle, the criteria for a so-called weak PRP), we need 3 rounds; see the famous work of Michael Luby and Charles Rackoff, How to Construct Pseudo-random Permutations from Pseudo-random Functions (in SIAM Journal on Computing Vol. 17, No. 2, 1988, initially presented at Crypto 1985);
  • under chosen plaintext and ciphertext (that is, additionally assuming a decryption oracle, the criteria for a so-called strong PRP), we need 4 rounds; for a proof that 3 rounds are not enough, see this answer.

These classical results are nice, and relatively easy to establish, but not directly applied in common practice. First, $O(2^{n/2})$ suggests that for 128-bit security (the current baseline), we'd need a 256-bit block cipher (which is uncommon: 128-bit is mainstream, 64-bit used to be). Also, ideal independent random functions at each round is assumed, but actual round functions are quite far from that.

Things are more complex (and more rounds are needed) for asymptotic security with more work; see Jacques Patarin's Luby-Rackoff: 7 Rounds are Enough for $2^{n(1−\epsilon)}$ Security, with a version in proceedings of Crypto 2003; and a later improvement (not peer-reviewed as far as I know, and far too complex for me).

Even more rounds are needed for prescribed small $n$, and to my knowledge we only have heuristics.

$\endgroup$
  • 1
    $\begingroup$ I'd rephrase the "chosen ciphertext" variant to emphasize that the attacker has access to both an encryption oracle and a decryption oracle. $\endgroup$ – CodesInChaos Feb 14 '17 at 19:20
  • 1
    $\begingroup$ You can drop the $O(\cdot)$; even Luby and Rackoff back in the day provided a concrete bound $Adv_{q} \le 2\binom{q}{2}/2^n \le q^2/2^n$. $\endgroup$ – Samuel Neves Feb 15 '17 at 20:59
  • $\begingroup$ @Samuel Neves: I do see that the Luby/Rackoff proof is quantitative (which is remarkable for 1988), but I do not feel confident enough with that formalism to make the necessary change to my own answer. Fell free to make that, or any other improvement! I made this answer a CW. $\endgroup$ – fgrieu Feb 15 '17 at 23:05

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.