Interpolation Cryptanalysis of UFNs wit...

In recent years a new type of block ciphers and hash functionsover a (large) field, such as MiMC and GMiMC, have been designed. Theirsecurity, particularly over a prime field, is mainly determined by algebraiccryptanalysis techniques, such as Gr ̈obner basis and interpolation attacks.In SAC 2019 Li and Preneel presented low memory interpolation attackagainst the MiMC and Feistel-MiMC designs.

In this work we answer the open question posed in their work and showthat  low  memory  interpolation  attacks  can  be  extended  to  unbalancedFeistel networks (UFN) with low degree functions, and in particular tothe GMiMC design. Our attack applies to UFNs with expanding and con-tracting round functions keyed either via identical (univariate) or distinctround keys (multivariate). Since interpolation attacks do not necessarilyyield the best possible attacks over a binary extension field, we focus ouranalysis on prime fieldsFp.Our next contribution is to develop an improved technique for a more effi-cient key recovery against UFNs with expanding round function. 

We show that the final key recovery step can be reduced not only to the gcd butalso to the root finding problem. Despite its higher theoretical complex-ity, we show that our approach has a particularly interesting applicationon Sponge hash functions based on UFNs, such as GMiMCHash.We illustrate for the first time how our root finding technique can be usedto findcollision,second  preimageandpreimageattacks on members ofthe GMiMCHash family. In addition, we support our theoretical analysiswith small-scale experimental results