Cryptology ePrint Archive: Report 2021/255

A Simple Algebraic Attack on 3-Round LowMC

Fukang Liu and Takanori Isobe and Willi Meier

Abstract: With the proposal of Picnic3, it has become interesting to investigate the security of LowMC with a full S-box layer. To significantly improve the efficiency of the Picnic signature, the designers of Picnic3 recommended to use the 4-round LowMC as the underlying block cipher, which has been shown to be insecure with 2 chosen plaintexts by Liu-Isobe-Meier. However, the attack scenario is very different and constrained in Picnic as the attacker is only allowed to know one single plaintext-ciphertext pair under the same key for LowMC. Recently, Banik et al. proposed guess-and-determine attacks on reduced LowMC in the Picnic setting. A major finding in their attacks is that the 3-bit S-box of LowMC can be linearized by guessing a quadratic equation. Notably, the attack on 2-round LowMC with a full S-box layer can be achieved with time complexity $2^{2m}$ where $m$ is the number of S-boxes in each round. As $k=3m$, their attacks can not reach 3 rounds where $k$ is the length of the key in bits. Although Banik et al. have improved the attacks with the meet-in-the-middle strategies, its memory complexity is rather high, which is $m\times 2^m$ bits of memory. In this note, we aim at low-memory key-recovery attacks as it is more fair to compare it with a pure exhaustive search. Specifically, we will describe improved algebraic attacks on 2-round LowMC by expressing the 3-bit S-box as 14 linearly independent quadratic boolean equations, which is inspired by the unsuccessful algebraic attacks on AES. As a result, the algebraic attacks on 2-round LowMC with key sizes of 129/192/255 bits can be improved by a factor of $2^{4}/2^{6.3}/2^{7.6}$, respectively. It seems that our attacks imply the attacks on 3-round LowMC. However, by taking the cost of gaussian elimination into account, the derived attacks on 3-round LowMC with key sizes of 192 and 255 bits are only about $2^{2.3}$ and $2^{3.7}$ times faster than the brute force. Our techniques are further applied to the instances with a partial S-box layer and significantly improve previous attacks with negligible memory complexity.

Category / Keywords: secret-key cryptography / LowMC, linearization, key recovery, algebraic attack, XL

Date: received 2 Mar 2021, last revised 7 Oct 2021

Contact author: liufukangs at 163 com, takanori isobe at ai u-hyogo ac jp, willimeier48 at gmail com

Available format(s): PDF | BibTeX Citation

Note: Further apply our techniques to instances with a partial S-box layer and solve the LowMC challenges with r=floor(n/s).

Version: 20211007:212023 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]