COSIC seminar "Interpolation Cryptanalysis of Unbalanced Feistel Networks with..." (Ferdinand Sauer)

COSIC seminar – Interpolation Cryptanalysis of Unbalanced Feistel Networks with Low Degree Round Functions – Ferdinand Sauer (KU Leuven & Karlsruhe Institute of Technology) A new type of block ciphers and hash functions (e.g. MiMC, GMiMC) that are deisgned over a (large) field have emerged in the past few years. The security of these constructions, particularly over prime fields, are mainly determined by the algebraic cryptanalysis such as Gröbner basis, interpolation attacks etc. Recently, Li and Preneel presented low memory interpolation attacks against such designs, in particular MiMC and Feistel-MiMC. In this work we answer the open question posed by Li and Preenel and show that low memory interpolation attacks can be extended to apply against unbalanced Feistel network (UFN) with low degree functions, and in particular to GMiMC. We develop a low memory interpolation attack that applies to UFNs with expanding and contracting round functions and keyed either via identical (univariate) and distinct (multivariate) round keys. Interpolation attacks do not necessarily yield the best possible attack over binary extension fields. We therefore focus our analysis on prime fields $\Fp$. Furthermore, we come up with an improved technique for more efficient key recovery against UFNs with expanding round function. We also show that the final key recovery step can be reduced not only to the gcd but also to the root finding problem. Despite the theoretical higher complexity of the latter, the approach becomes of particular interest when we consider hash function constructions like GMiMCHash. We thus extend our algebraic analysis to sponge hash functions based on UFNs and for the first time illustrate an attack on the UFN based GMiMCHash functions. We also support our theoretical analysis with small-scale experimental results.