Improved Preimage Attacks on 4-Round Keccak-224/256

  • Le He Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China
  • Xiaoen Lin Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China
  • Hongbo Yu Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China
Keywords: Keccak, SHA-3, Preimage attack, Linear structure

Abstract

This paper provides an improved preimage attack method on standard 4-round Keccak-224/256. The method is based on the work pioneered by Li and Sun, who design a linear structure of 2-round Keccak-224/256 with 194 degrees of freedom left. By partially linearizing 17 output bits through the last 2 rounds, they finally reach a complexity of 2207/2239 for searching a 4-round preimage. Yet under their strategy, those 17 bits are regarded as independent bits and the linearization costs a great amount of freedom. Inspired by their thoughts, we improve the partial linearization method where multiple output bits can reuse some common degrees of freedom. As a result, the complexity of preimage attack on 4-round Keccak-224/256 can be decreased to 2192/2218, which are both the best known theoretical preimage cryptanalysis so far. To support the theoretical analysis, we apply our strategy to a 64-bit partial preimage attack within practical complexity. It is remarkable that this partial linearization method can be directly applied if a better linear structure with more freedom left is proposed.

Published
2021-03-19
How to Cite
He, L., Lin, X., & Yu, H. (2021). Improved Preimage Attacks on 4-Round Keccak-224/256. IACR Transactions on Symmetric Cryptology, 2021(1), 217-238. https://doi.org/10.46586/tosc.v2021.i1.217-238
Section
Articles