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.