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

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, n_r=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, n_r=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 2¹⁵⁰/2¹⁵¹/2¹⁵³ operations, while the previous best known result on Keccak-256 is 2¹⁹²