Preimage Attacks on the Round-reduced Keccak with Cross-linear Structures

  • Ting Li State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences; School of Cyber Security, University of Chinese Academy of Sciences, Beijing
  • Yao Sun State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing
  • Maodong Liao Key Laboratory of Mathematics Mechanization, Academy of Mathematics and Systems Science; School of Mathematical Sciences, University of Chinese Academy of Sciences, Beijing
  • Dingkang Wang Key Laboratory of Mathematics Mechanization, Academy of Mathematics and Systems Science; School of Mathematical Sciences, University of Chinese Academy of Sciences, Beijing
Keywords: Cryptanalysis, SHA-3, Keccak, Preimage attacks

Abstract

In this paper, based on the work pioneered by Aumasson and Meier, Dinur et al., and Guo et al., we construct some new delicate structures from the roundreduced versions of Keccakhash function family. The new constructed structures are called cross-linear structures, because linear polynomials appear across in different equations of these structures. And we apply cross-linear structures to do preimage attacks on some instances of the round-reduced Keccak. There are three main contributions in this paper. First, we construct a kind of cross-linear structures by setting the statuses carefully. With these cross-linear structures, guessing the value of one linear polynomial could lead to three linear equations (including the guessed one). Second, for some special cases, e.g. the 3-round Keccakchallenge instance Keccak[r=240, c=160, nr=3], a more special kind of cross-linear structures is constructed, and these structures can be used to obtain seven linear equations (including the guessed) if the values of two linear polynomials are guessed. Third, as applications of the cross-linear structures, we practically found a preimage for the 3-round KeccakChallenge instance Keccak[r=240, c=160, nr=3]. Besides, by constructing similar cross-linear structures, the complexity of the preimage attack on 3-round Keccak-256/SHA3-256/SHAKE256 can be lowered to 2150/2151/2153 operations, while the previous best known result on Keccak-256 is 2192.
Published
2017-12-15
How to Cite
Li, T., Sun, Y., Liao, M., & Wang, D. (2017). Preimage Attacks on the Round-reduced Keccak with Cross-linear Structures. IACR Transactions on Symmetric Cryptology, 2017(4), 39-57. https://doi.org/10.13154/tosc.v2017.i4.39-57
Section
Articles