Paper 2020/346

Algebraic Attacks on Round-Reduced Keccak/Xoodoo

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

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
hash functionKeccakXoodooalgebraic attackzero-sum
Contact author(s)
liufukangs @ 163 com
takanori isobe @ ai u-hyogo ac jp
willimeier48 @ gmail com
ashzhonghao @ gmail com
History
2020-07-04: last of 3 revisions
2020-03-26: received
See all versions
Short URL
https://ia.cr/2020/346
License
Creative Commons Attribution
CC BY

BibTeX

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