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.

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

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

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.

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