Feistel Ciphers

In this chapter, we present the general concept of cryptography and introduce the notation and definitions used throughout this book.

Feistel ciphers are named after Horst Feistel who studied these schemes in the 1960s. In this chapter, we will only present classical Feistel ciphers, i.e. balanced Feistel ciphers with the ⊕ group law (Xor). In Chaps. 8, 9 and 10, we will see that there are many variants of these ciphers.

The “H-coefficient technique” was introduced in 1990 and 1991 in Patarin (Pseudorandom permutations based on the DES scheme, Springer, Heidelberg, 1990, pp. 193–204; Étude des Générateurs de Permutations Pseudo-aléatoires basés sur le schéma du D.E.S., PhD, November 1991). Since then, it has been used many times to prove various results on pseudo-random functions and pseudo-random permutations (Chen et al., Minimizing the Two-round Even-Mansour Cipher Advances in Cryptology – CRYPTO 2014, vol. 8616, Springer, Heidelberg, 2014, pp. 39–56; Gilbert and Minier, New results on the pseudorandomness of some blockcipher constructions, Springer, Heidelberg, 2001, pp. 248–266; Pieprzyk, How to construct pseudorandom permutations from single pseudorandom functions, Springer, Heidelberg, 1991, pp. 140–150; Yun et al., Des. Codes Cryptography 58:45–72, 2011). Recently, it has also been used on key-alternating ciphers (Even-Mansour), cf. (Chen and Steinberger, Tight security bounds for key-alternating ciphers, Springer, Heidelberg, 2014, pp. 327–350) for example. We will use this technique in Chap. 4 for the specific cases of Ψ ³, Ψ ⁴, and then in many proofs of security of this book. In this chapter, in Sect. 3.1, we will present the “H-coefficient technique”, in a general way (not only for Ψ ^k ), with different formulations when we study different cryptographic attacks (known-plaintext attacks, chosen-plaintext attacks, etc.). In Sect. 3.4, we will present an example with the exact values of the H coefficient on Ψ ^k with q = 2 plaintext/ciphertext pairs. Finally, in Sect. 3.5, we will present two simple and powerful composition theorems based on H-coefficient method in CCA.

In this chapter we will give complete proofs of the two results of Michael Luby and Charles Rackoff published in their important paper of 1988 (Luby and Rackoff, SIAM J. Comput. 17:373–386, 1988). These two results are:

Different kinds of proofs exist for these famous theorems. We will give here Jacques Patarin’s proof of 1990 (Patarin, Pseudorandom permutations based on the DES Scheme, Springer, 1990) based on “H-properties”; i.e. counting arguments on the keys. This proof technique is called the “H-coefficient technique” and was presented in Chap. 3.

In this chapter, we describe the method that we will use in most of attacks used in this book. We call it the variance method. For the attacks, we determine conditions that have to be satisfied by inputs and outputs. The conditions appear at random but with a cipher, well chosen differential characteristics can lead to the conditions on the outputs. This is due to the structure of the cipher. Then one has to compare the number of plaintext/ciphertext verifying the conditions. The variance method is a tool that allow to measure efficiently if the difference between the number obtained with a random permutation and the number obtained with a cipher is significant.

In this chapter, we will give a complete description of best known attacks on classical Feistel ciphers.

In this chapter, generic attacks on Feistel networks with internal permutations, instead of Feistel networks with internal functions as designed originally are studied. As always in generic attacks, the internal permutations are supposed to be random. However, as we will see, Feistel networks with internal permutations do not always behave like the original Feistel networks with roundfunctions.

This chapter deals with generic attacks on unbalanced Feistel ciphers with contracting functions. These ciphers are used to construct pseudo-random permutations from kn bits to kn bits by using r pseudo-random functions from (k − 1)n bits to n bits. The study concerns KPA and NCPA against these schemes with less than 2 ^kn plaintext/ciphertext pairs and complexity strictly less than O(2 ^rn ) for a number of rounds r ≤ 2k − 1. Consequently at least 2r rounds are necessary to avoid generic attacks. For k = 3, there exists attacks up to 6 rounds, so 7 rounds are required. When k ≥ 2k, it is possible to attack permutation generators instead of one permutation. Some results on contracting Feistel schemes or on small transformations of these schemes can be found in (Lucks, Faster Luby-Rackoff ciphers, Springer, Heidelberg, 1996, pp. 189–203; Naor and Reingold, J. Cryptology 12:29–66, 1999, Extended abstract in: Proc. 29th Ann. ACM Symp. on Theory of Computing, pp. 189–199, 1997). In Naor and Reingold (J. Cryptology 12:29–66, 1999, Extended abstract in: Proc. 29th Ann. ACM Symp. on Theory of Computing, pp. 189–199, 1997), Naor and Reingold studied the security of contracting Feistel schemes that begin and end with pairwise independent permutations. They provide lower bounds for the security of such schemes. Lucks (Faster Luby-Rackoff ciphers, Springer, Heidelberg, 1996, pp. 189–203) gives some security results on contracting Feistel schemes built with hash functions. Birthday bound security results are given in Yun et al. (Des. Codes Crypt. 58:45–72, 2011), first results above the birthday bound are proved in Patarin (Security of balanced and unbalanced Feistel schemes with linear non equalities, in Cryptology ePrint Archive: Report 2010/293). Security results based on the coupling method are given in Hoang and Rogaway (On generalized Feistel networks, Springer, Heidelberg, 2010, pp. 613–630). Generic attacks on contracting Feistel ciphers are studied in Patarin et al. (Generic attacks on unbalanced Feistel schemes with contracting functions, Springer, Heidelberg, 2006, pp. 396–411). A large number of attacks use the variance method described in Chap. 5.

“Generic” Unbalanced Feistel Ciphers with Expanding Functions are Unbalanced Feistel Ciphers with truly random internal round functions from n bits to (k − 1)n bits with k ≥ 3. From a practical point of view, an interesting property of these schemes is that since n < (k − 1)n and n can be small (8 bits for example), it is often possible to store these truly random functions in order to design efficient schemes. This was done in the construction of the hash function CRUNCH (Goubin et al., CRUNCH, Submission to NIST, October 2008) for example. Attacks on Unbalanced Feistel Ciphers with expanding functions have been first studied by Jutla (Generalized birthday attacks on unbalanced Feistel networks, Springer, Heidelberg, 1998, pp. 186–199). Then these attacks were improved and generalized in Patarin et al. (Generic attacks on unbalanced Feistel schemes with expanding functions, Springer, Heidelberg, 2007, pp. 325–341). However, in Patarin et al. (Generic attacks on unbalanced Feistel schemes with expanding functions, Springer, Heidelberg, 2007, pp. 325–341), some attacks were working only with particular functions (weak keys). This was due to bottlenecks in equalities as explained in Sect. 9.3.2. This issue has been addressed in Volte et al. (Improved generic attacks on unbalanced Feistel schemes with expanding functions, Springer, Heidelberg, 2010, pp. 94–111) where the authors created a computer program that systematically analyzes all the possible attacks, reject attacks with bottlenecks and detect the most efficient ones. This led to many new improved attacks by a systematic study of all 2-point and rectangle attacks when k ≤ 7. The generalization of these improved attacks was done for all k. This chapter is devoted to present the best attacks (KPA and NCPA) on Unbalanced Feistel Ciphers with Expanding Functions. According to the number of rounds, these attacks will be either 2-point attacks or different type of rectangle attacks. As pointed in Jutla (Generalized birthday attacks on unbalanced Feistel networks, Springer, Heidelberg, 1998, pp. 186–199) and (Patarin et al., Generic attacks on unbalanced Feistel schemes with expanding functions, Springer, Heidelberg, 2007, pp. 325–341; Volte et al., Improved generic attacks on unbalanced Feistel schemes with expanding functions, Springer, Heidelberg, 2010, pp. 94–111), there are surprisingly much more possibilities for these attacks than for generic balanced Feistel ciphers, generic unbalanced Feistel ciphers with contracting functions, or generalized Feistel ciphers. In fact, this large number of attack possibilities makes the analysis difficult. Many simulations on the attacks are also given, which confirm the theoretical analysis. Security results using the coupling method are given in Hoang and Rogaway (On generalized Feistel networks, Springer, Heidelberg, 2010, pp. 613–630).

Type-1, type-2 and type-3 and alternating Feistel schemes, are described by Zhen, Matsumoto, and Imai (On the construction of block ciphers provably secure and not relying on any unproved hypotheses, Springer, Heidelberg, 1990, pp. 461–480) (see also Hoang and Rogaway, On generalized Feistel networks, Springer, Heidelberg, 2010, pp. 613–630). These generalized Feistel schemes are used in well known block cipher networks that use generalized Feistel schemes: CAST-256 (type-1), RC-6 (type-2), and BEAR/LION (alternating). Also, type-1 and type-2 Feistel schemes are respectively used in the construction of the hash functions Lesamnta and SHAvite − 3₅₁₂. There exist many kind of attacks on these schemes: impossible differential attacks (Bouillaguet et al., New insights on impossible differential cryptanalysis, Springer, Heidelberg, 2012, pp. 243–259; Luo et al., Inform. Sci. 263:211–220, 2014), boomerang attacks (Choy and Yap, Impossible boomerang attacks for block cipher structures, Springer, Heidelberg, 2009, pp. 22–37) and differential attacks (Nachef et al., Differential attacks on generalized Feistel schemes, Springer, Heidelberg, 2013, pp. 1–19). However, the attacks we are going to describe in this chapter generally allow to attack more rounds (or at least the same number of rounds) than for example impossible differential attacks. Moreover in the presented attacks, there is no restriction on the round function, unlike for some impossible differential attacks where it is supposed to be bijective. Security results are given in Hoang and Rogaway (On generalized Feistel networks, Springer, Heidelberg, 2010, pp. 613–630).

In this chapter, we present concrete ciphers based on the constructions studied previously. We provide examples of balanced, unbalanced and generalized Feistel ciphers. For each of them, we give the description and a survey of attacks performed on these ciphers.

The coupling technique originates from the theory of Markov chains, and allows to upper bound the rate at which a Markov chain approaches its stationary distribution. Recasting the encryption process of a tuple of plaintexts through an iterative block cipher as a Markov chain, it is possible to use this tool to upper bound the advantage of a distinguisher against various kinds of Feistel schemes.

“Mirror Theory” is the theory that evaluates the number of solutions of affine systems of equalities ( = ) and non equalities ( ≠ ) in finite groups. It is deeply related to the security and attacks of many generic cryptographic secret-key schemes, like random Feistel schemes (balanced or unbalanced), Misty schemes, Xor of two pseudo-random bijections to generate a pseudo-random function etc. In this chapter we will assume that the groups are abelian. Most of the time in cryptography the group is \(((\mathbb{Z}/2\mathbb{Z})^{n},\oplus )\) and this chapter concentrates on these cases. We present here general definitions, some theorems, and many examples and computer simulations.

In this chapter, we will study and prove the so-called “P _i ⊕ P _j Theorem” of Patarin (On linear systems of equations with distinct variables and small block size, Springer, 2005). More precisely, we will study here the case ξ _max  = 2 (ξ _max will be defined below) and in Chap. 16 we will study the cases for any ξ _max . Then, in Chap. 17, we will use these “P _i ⊕ P _j Theorems” to prove some very strong security bound on generic Feistel ciphers.It is useful to first study the case ξ _max  = 2, since this case is simpler but contains all the difficulties of the general case, so Chap. 16 will be just a generalization of this Chap. 15. Moreover the case ξ _max  = 2 has its own interest from a cryptographic point of view since, as we will see, it is closely related to the problem of distinguishing f(x ∥ 0) ⊕ f(x ∥ 1) where f is a random permutation on n bits from a random function. The proofs of this chapter use many pages, but we will proceed progressively, with a very regular progression on the security bounds obtained. Theorem P _i ⊕ P _j can be seen as part of “Mirror Theory” (see Chap. 14). In fact the proof technique that we will present and use here (with differentials on “orange” and “purple” equations) can be used on many other “mirror systems” and variants and generalizations of “P _i ⊕ P _j Theorem”.

In this chapter, we will study and prove the “P _i ⊕ P _j Theorem” of Patarin (On linear systems of equations with distinct variables and small block size, Springer, 2005) on “standard systems” and the “P _i ⊕ P _j Theorem” with any ξ _max . Then, in Chap. 17, we will use these “P _i ⊕ P _j Theorems” (essentially on standard systems) to obtain tight security results on classical Feistel ciphers. “Standard systems” and ξ _max will be defined in Sect. 16.1. This chapter is essentially a generalization of what we did in Chap. 15. Moreover, since we will use the same proof technique (orange equation and then differentials on purple equations) it is recommended to read Chap. 15 before, or in parallel of this chapter.

In this chapter, we will use the results obtained in Chaps. 15 and 16 in order to prove some security results on Generic balanced Feistel ciphers Ψ ^k . The main results will be the proof of security for Ψ ⁴ in KPA, for Ψ ⁵ in CPA and CCA, and for Ψ ⁶ in CCA, when q ≪ 2 ⁿ . We will also see what kind of bound we obtain from the results on Ψ ⁶ for Ψ ^k , k ≥ 6, by using some compositions theorem. Finally, at the end of this chapter, we will compare the results obtained with proofs from Mirror theory and H-coefficient technique from the results obtained in Chap. 13 with the coupling technique.

Indifferentiability is a stronger notion than indistinguishability which considers the case where the adversary has oracle access to the inner round functions. It allows to rigorously formalize the fact that a block cipher “behaves” as an ideal cipher. It is known that at least six rounds of balanced Feistel ciphers are necessary to achieve this security notion. Currently, the lowest number of rounds known to be sufficient to achieve the notion is eight.