Welcome to the resource topic for 2021/255
Title:
Low-Memory Algebraic Attacks on Round-Reduced LowMC
Authors: Fukang Liu, Takanori Isobe, 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.
ePrint: https://eprint.iacr.org/2021/255
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .