Paper 2021/367

Interpolation Cryptanalysis of Unbalanced Feistel Networks with Low Degree Round Functions

Arnab Roy, Elena Andreeva, and Jan Ferdinand Sauer

Abstract

In recent years a new type of block ciphers and hash functions over a (large) field, such as MiMC and GMiMC, have been designed. Their security, particularly over a prime field, is mainly determined by algebraic cryptanalysis techniques, such as Gröbner basis and interpolation attacks. In SAC 2019, Li and Preneel presented low memory interpolation cryptanalysis against the MiMC and Feistel-MiMC designs. In this work we answer the open question posed in their work and show that low memory interpolation cryptanalysis can be extended to unbalanced Feistel networks (UFN) with low degree functions, and in particular to the GMiMC design. Our attack applies to UFNs with expanding and contracting round functions keyed either via identical (univariate) or distinct round keys (multivariate). Since interpolation attacks do not necessarily yield the best possible attacks over a binary extension field, we focus our analysis on prime fields GF(p). Our next contribution is to develop an improved technique for a more efficient key recovery against UFNs with expanding round function. We show that the final key recovery step can be reduced not only to the gcd but also to the root finding problem. Despite its higher theoretical complexity, we show that our approach has a particularly interesting application on Sponge hash functions based on UFNs, such as GMiMCHash. We illustrate for the first time how our root finding technique can be used to find collision, second preimage and preimage attacks on (reduced round) members of the GMiMCHash family. In addition, we support our theoretical analysis with small-scale experimental results.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. MINOR revision.SAC 2020
Keywords
GMiMCUnbalanced FeistelInterpolation attackLow Memory Interpolation
Contact author(s)
arnab roy @ aau at
History
2021-03-22: received
Short URL
https://ia.cr/2021/367
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/367,
      author = {Arnab Roy and Elena Andreeva and Jan Ferdinand Sauer},
      title = {Interpolation Cryptanalysis of Unbalanced Feistel Networks with Low Degree Round Functions},
      howpublished = {Cryptology ePrint Archive, Paper 2021/367},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/367}},
      url = {https://eprint.iacr.org/2021/367}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.