Paper 2019/812

Improved Interpolation Attacks on Cryptographic Primitives of Low Algebraic Degree

Chaoyun Li and Bart Preneel

Abstract

Symmetric cryptographic primitives with low multiplicative complexity have been proposed to improve the performance of emerging applications such as secure Multi-Party Computation. However, primitives composed of round functions with low algebraic degree require a careful evaluation to assess their security against algebraic cryptanalysis, and in particular interpolation attacks. This paper proposes new low-memory interpolation attacks on symmetric key primitives of low degree. Moreover, we present generic attacks on block ciphers with a simple key schedule; our attacks require either constant memory or constant data complexity. The improved attack is applied to the block cipher MiMC which aims to minimize the number of multiplications in large finite fields. As a result, we can break MiMC-$129/129$ with $38$ rounds with time and data complexity $2^{65.5}$ and $2^{60.2}$ respectively and with negligible memory; this attack invalidates one of the security claims of the designers. Our attack indicates that for MiMC-$129/129$ the full $82$ rounds are necessary even with restrictions on the memory available to the attacker. For variants of MiMC with larger keys, we present new attacks with reduced complexity. Our results do not affect the security claims of the full round MiMC.

Note: Improved attacks on larger key versions of MiMC in updated Section 4.1.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. SAC 2019
Keywords
Block cipherCryptanalysisInterpolation attackMiMC
Contact author(s)
chaoyun li @ esat kuleuven be
History
2019-09-18: revised
2019-07-14: received
See all versions
Short URL
https://ia.cr/2019/812
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/812,
      author = {Chaoyun Li and Bart Preneel},
      title = {Improved Interpolation Attacks on Cryptographic Primitives of Low Algebraic Degree},
      howpublished = {Cryptology ePrint Archive, Paper 2019/812},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/812}},
      url = {https://eprint.iacr.org/2019/812}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.