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 .

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Generic Attacks on Contracting Feistel Ciphers

  • Jacques Patarin,
  • Emmanuel Volte,
  • Benoît Cogliati

摘要

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 .