Search

A usual way to construct block ciphers is to apply several rounds of a given structure. Many kinds of attacks are mounted against block ciphers. Among them, differential and linear attacks are widely used. Vaudenay showed that ciphers achieving perfect pairwise decorrelation are secure against linear and differential attacks. It is possible to obtain such schemes by introducing at least one random affine permutation as a round function in the design of the scheme. In this paper, we study attacks on schemes based on classical Feistel schemes where we introduce one or two affine permutations. Since these schemes resist against linear and differential attacks, we will study attacks based on specific equations on 4-tuples of plaintext/ciphertext messages. We show that these schemes are stronger than classical Feistel schemes.

National audience; Nous proposons une analyse critique de l’ensemble des exercices de l’épreuve de mathématiques 2017 du brevet ayant trait au thème « Algorithmique et programmation » du programme de cycle 4. Certains de ces exercices ne mettent en jeu que de manière très superficielle des compétences spécifiquement informatiques, mais portent plutôt sur des compétences mathématiques « traditionnelles », liées par exemple à l’algèbre ou la géométrie. Notre analyse met en regard ces différentes compétences, et propose des adaptations de certains énoncés afin d’en permettre une exploitation plus riche.

In SAC 2013, Berger et al. defined Extended Generalized Feistel Networks (EGFN) and analyzed their security. Later, they proposed a cipher based on this structure: \( LILLIPUT \). Impossible differential attacks and integral attacks have been mounted on \( LILLIPUT \). We propose a tool which has found some classical, impossible and improbable differential attacks by using the variance method. It has highlighted unusual differential conditions which lead to efficient attacks according to the complexity. Moreover, it is the first time we apply the generic variance method to a concrete cipher.

“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).

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.

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 paper, we use a tool that computes exact values for expectations and standard deviations of random variables involved in generic attacks on various Feistel-type schemes in order to get a better study of these attacks. This leads to the improvement of previous attacks complexities: either we need less messages than expected or we can attack more rounds. These improvements are given for different sizes of the inputs. We also show that for rectangle attacks, there are more differential paths than presented in previous attacks and this strengthens the attacks.

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

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 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 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 Ψ4 in KPA, for Ψ5 in CPA and CCA, and for Ψ6 in CCA, when q ≪ 2 n . We will also see what kind of bound we obtain from the results on Ψ6 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.

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.

In this chapter, we will describe briefly the DES schemes and its main variants. Then we will present the known cryptanalysis results on these 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.

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; Etude des Generateurs de Permutations Pseudo-aleatoires bases sur le schema 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 Ψ3, Ψ4, 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: 1. A three (or more) rounds Feistel scheme with random round functions (or with pseudo-random round functions) will give us an invertible pseudo-random permutation generator. This means that we have a cryptosystem which is secure against chosen plaintext attacks. 2. A four (or more) rounds Feistel scheme with random round functions (or with pseudo-random round functions) will give us an invertible super pseudo-random permutation generator. This means that we have a cryptosystem which is secure against chosen plaintext and chosen ciphertext attacks.

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.

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 − 3512. 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 SAC 2013, Berger et al. defined Extended Generalized Feistel Networks (EGFN) and analyzed their security. They proposed designs with 8 or 16 branches. This class of schemes is well-suited for cryptographic applications. Using the minimal number of active S-boxes, the authors showed that for 64-bits messages divided into 8 branches, at least seven rounds are needed for security against differential and linear cyptanalysis. They proved that 10 rounds are required against integral attacks and 9 rounds against impossible differential attacks. In this paper, we propose a method that allows to attack up to 18 rounds the design with 8 branches. We also mention the results for the 16-branch design.

International audience; While generic attacks on classical Feistel schemes and unbalanced Feistel schemes have been studied a lot, generic attacks on several generalized Feistel schemes like type-1, type-2 and type-3 and alternating Feistel schemes, as defined in [8], have not been systematically investigated. 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), MARS (type-3) 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 - 3512.In this paper, we give our best Known Plaintext Attacks and non-adaptive Chosen Plaintext Attacks on these schemes. We determine the maximal number of rounds that we can attack when we want to distinguish a permutation produced by the scheme from a permutation chosen randomly in the set of permutations. © Springer International Publishing 2013.

International audience; The factorization problem in non-abelian groups is still an open and a difficult problem [12]. The hardness of the problem is illustrated by the moves of the Rubik's cube.We will define a public key identification scheme based on this problem, in the case of the Rubik's cube, when the number of moves is fixed to a given value. Our scheme consists of an interactive protocol which is zero-knowledge argument of knowledge under the assumption of the existence of a commitment scheme. We will see that our scheme works with any non-abelian groups with a set of authorized moves that has a specific property. Then we will generalize the scheme for larger Rubik's cubes and for any groups. © Springer International Publishing 2013.

“Generic” Unbalanced Feistel Schemes with Expanding Functions are Unbalanced Feistel Schemes 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 (example: CRUNCH cf [6]). Attacks on these generic schemes were studied in [7] and [18]. As pointed in [7] and [18], there are surprisingly much more possibilities for these attacks than for generic balanced Feistel schemes or generic unbalanced Feistel schemes with contracting functions. In fact, this large number of attack possibilities makes the analysis difficult. In this paper, we shall methodically analyze again these attacks. We have created a computer program that systematically analyze all the possible attacks and detect the most efficient ones. We have detected a condition on the internal variables that was not clearly analyzed in [18], and we have found many new improved attacks by a systematic study of all the “rectangle attacks” when k ≤ 7, and then we have generalized these improved attacks for all k. Many simulations on our improved attacks have also been done and they confirm our theoretical analysis.