Cryptology ePrint Archive: Report 2020/1034

Cryptanalysis of Full LowMC and LowMC-M with Algebraic Techniques

Fukang Liu and Takanori Isobe and Willi Meier

Abstract: In this paper, we revisit the difference enumeration techniques for LowMC and develop new algebraic techniques to achieve efficient key-recovery attacks with negligible memory complexity. \mbox{Benefiting} from our technique to reduce the memory complexity, we could significantly improve the attacks on LowMC when the block size is much larger than the key size and even break LowMC with such a kind of parameter. On the other hand, with our new key-recovery technique, we could significantly improve the time to retrieve the full key if given only a single pair of input and output messages together with the difference trail that they take, which was stated as an interesting question by Rechberger et al. in ToSC 2018. Combining both the techniques, with only 2 chosen plaintexts, we could break 4 rounds of LowMC adopting a full S-Box layer with block size of 129, 192 and 255 bits, respectively, which are the 3 recommended parameters for Picnic3, an alternative \mbox{third-round} candidate in NIST's Post-Quantum Cryptography competition. We have to emphasize that our attacks do not indicate that Picnic3 is broken as the Picnic use-case is very different and an attacker cannot even freely choose 2 plaintexts to encrypt for a LowMC instantiation. However, such parameters are deemed as secure in the latest LowMC. Moreover, much more rounds of seven instances of the backdoor ciphers \mbox{LowMC-M} as proposed by Peyrin and Wang in CRYPTO 2020 can be broken without finding the backdoor by making full use of the allowed $2^{64}$ data. The above mentioned attacks are all achieved with negligible memory.

Category / Keywords: secret-key cryptography / LowMC, LowMC-M, linearization, key recovery, negligible memory

Date: received 27 Aug 2020, last revised 19 Sep 2020

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

Available format(s): PDF | BibTeX Citation

Note: Fix some editorial mistakes in Table 1.

Version: 20200919:103859 (All versions of this report)

Short URL: ia.cr/2020/1034


[ Cryptology ePrint archive ]