Cryptology ePrint Archive: Report 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.

Category / Keywords: secret-key cryptography / Block cipher, Cryptanalysis, Interpolation attack, MiMC

Original Publication (in the same form): SAC 2019

Date: received 13 Jul 2019, last revised 18 Sep 2019

Contact author: chaoyun li at esat kuleuven be

Available format(s): PDF | BibTeX Citation

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

Short URL: ia.cr/2019/812

[ Cryptology ePrint archive ]