**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.

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

**Date: **received 2 Mar 2021, last revised 4 Mar 2021

**Contact author: **liufukangs at 163 com,takanori isobe@ai u-hyogo ac jp,willimeier48@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: **20210304:115637 (All versions of this report)

**Short URL: **ia.cr/2021/255

[ Cryptology ePrint archive ]