Cryptology ePrint Archive: Report 2020/346

Algebraic Attacks on Round-Reduced Keccak/Xoodoo

Fukang Liu and Takanori Isobe and Willi Meier and Zhonghao Yang

Abstract: Since Keccak was selected as the SHA-3 standard, both its hash mode and keyed mode have attracted lots of third-party cryptanalysis. Especially in recent years, there is progress in analyzing the collision resistance and preimage resistance of round-reduced Keccak. However, for the preimage attacks on round-reduced Keccak-384/512, we found that the linear relations leaked by the hash value are not well exploited when utilizing the current linear structures. To make full use of the $320+64\times2=448$ and 320 linear relations leaked by the hash value of Keccak-512 and Keccak-384, respectively, we propose a dedicated algebraic attack by expressing the output as a quadratic Boolean equation system in terms of the input. Such a quadratic Boolean equation system can be efficiently solved with linearization techniques. Consequently, we successfully improved the preimage attacks on 2/3/4 rounds of Keccak-384 and 2/3 rounds of Keccak-512. Since similar $\theta$ and $\chi$ operations exist in the round function of Xoodoo, we make a study of the permutation and construct a practical zero-sum distinguisher for 12-round Xoodoo. Although 12-round Xoodoo is the underlying permutation used in Xoodyak, which has been selected by NIST for the second round in the Lightweight Cryptography Standardization process, such a distinguisher will not lead to an attack on Xoodyak.

Category / Keywords: secret-key cryptography / hash function, Keccak, Xoodoo, algebraic attack, zero-sum

Date: received 23 Mar 2020, last revised 4 Jul 2020

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

Available format(s): PDF | BibTeX Citation

Version: 20200704:065304 (All versions of this report)

Short URL: ia.cr/2020/346


[ Cryptology ePrint archive ]