Paper 2021/255

Low-Memory Algebraic Attacks on Round-Reduced LowMC

Fukang Liu, 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.

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

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint. Minor revision.
Keywords
LowMClinearizationkey recoveryalgebraic attackXL
Contact author(s)
liufukangs @ 163 com
takanori isobe @ ai u-hyogo ac jp
willimeier48 @ gmail com
History
2021-12-26: last of 3 revisions
2021-03-03: received
See all versions
Short URL
https://ia.cr/2021/255
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/255,
      author = {Fukang Liu and Takanori Isobe and Willi Meier},
      title = {Low-Memory Algebraic Attacks on Round-Reduced LowMC},
      howpublished = {Cryptology ePrint Archive, Paper 2021/255},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/255}},
      url = {https://eprint.iacr.org/2021/255}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.