Paper 2022/788

Improved Preimage Attacks on Round-Reduced Keccak-384/512 via Restricted Linear Structures

Le He, Tsinghua University
Xiaoen Lin, Tsinghua University
Hongbo Yu, Tsinghua University
Abstract

This paper provides improved preimage analysis on round-reduced Keccak-384/512. Unlike low-capacity versions, Keccak-384/512 outputs from two planes of its inner state: an entire 320-bit plane and a second plane containing 64/192 bits. Due to lack of degrees of freedom, most existing preimage analysis can only control the 320-bit plane and cannot achieve good results. In this paper, we find out a method to construct linear relations between corresponding bits from the two planes, which means attacker can control two output planes simultaneously with degrees of freedom much less than 320. Besides, we design several linear structures for each different version with additional restrictions that can leave more degrees of freedom. As a result, the complexity of preimage attacks on 2-round Keccak-384/512 and 3-round Keccak-384/512 can be decreased to $2^{28}$/$2^{252}$ and $2^{271}$/$2^{426}$ respectively, which are all the best known results so far. To support the analysis, this paper also provides the first preimage of all `0' digest for 2-round Keccak-384, which can be obtained in hours level by a personal computer. It is worth noting that although our structures contain non-linear parts, the attack algorithms only involve the solution of linear equation systems.

Metadata
Available format(s)
PDF
Category
Attacks and cryptanalysis
Publication info
Preprint.
Keywords
Keccak Preimage attack Linear relation
Contact author(s)
he-l17 @ mails tsinghua edu cn
yuhongbo @ mail tsinghua edu cn
History
2022-06-20: approved
2022-06-19: received
See all versions
Short URL
https://ia.cr/2022/788
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/788,
      author = {Le He and Xiaoen Lin and Hongbo Yu},
      title = {Improved Preimage Attacks on Round-Reduced Keccak-384/512 via Restricted Linear Structures},
      howpublished = {Cryptology ePrint Archive, Paper 2022/788},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/788}},
      url = {https://eprint.iacr.org/2022/788}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.