Generic Attacks on Expanding Feistel Ciphers
摘要
“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 \ge 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. 2008) for example. Attacks on Unbalanced Feistel Ciphers with expanding functions have been first studied by Jutla (1998). Then these attacks were improved and generalized in Patarin et al. (2007). However, in Patarin et al. (2007), some attacks were working only with particular functions (weak keys). This was due to bottleneck in equalities as explained in Sect. 9.3.2. This issue has been addressed in Volte et al. (2010) 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 \le 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 (1998) and Patarin et al. (2007), Volte et al. (2010), 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 (2010).