Generic Attacks on Contracting Feistel Ciphers
摘要
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 d 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^{kn})\) for a number of rounds \(d \le 2k -1\) . Consequently at least 2k rounds are necessary to avoid generic attacks. For \(k=3\) , there exists attacks up to 6 rounds, so 7 rounds are required. When \(r \ge 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 (1996), Naor and Reingold (1999). In Naor and Reingold (1999), 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 (1996) gives some security results on contracting Feistel schemes built with hash functions. Birthday bound security results are given in Yun et al. (2011), first results above the birthday bound are proved in Patarin (2010). Security results based on the coupling method are given in Hoang and Rogaway (2010). Generic attacks on contracting Feistel ciphers are studied in Patarin et al. (2006). A large number of attacks use the variance method described in Chap. 5 .