Cryptology ePrint Archive: Report 2019/248

Preimage Attacks on Round-reduced Keccak-224/256 via an Allocating Approach

Ting Li and Yao Sun

Abstract: We present new preimage attacks on standard Keccak-224 and Keccak-256 that are reduced to 3 and 4 rounds. An allocating approach is used in the attacks, and the whole complexity is allocated to two stages, such that fewer constraints are considered and the complexity is lowered in each stage. Specifically, we are trying to find a 2-block preimage, instead of a 1-block one, for a given hash value, and the first and second message blocks are found in two stages, respectively. Both the message blocks are constrained by a set of newly proposed conditions on the middle state, which are weaker than those brought by the initial values and the hash values. Thus, the complexities in the two stages are both lower than that of finding a 1-block preimage directly. Together with the basic allocating approach, an improved method is given to balance the complexities of two stages, and hence, obtains the optimal attacks. As a result, we present the best theoretical preimage attacks on Keccak-224 and Keccak-256 that are reduced to 3 and 4 rounds. Moreover, we practically found a (second) preimage for 3-round Keccak-224 with a complexity of 2^{39.39}.

Category / Keywords: Cryptanalysis, Keccak, SHA-3, Preimage attack

Original Publication (in the same form): IACR-EUROCRYPT-2019

Date: received 28 Feb 2019, last revised 12 Mar 2019

Contact author: sunyao at iie ac cn

Available format(s): PDF | BibTeX Citation

Note: Thank Prof. Dr. Willi Meier for pointing out the mistake in Figure 9. This mistake has been fixed in this revised version.

Version: 20190312:072045 (All versions of this report)

Short URL: ia.cr/2019/248


[ Cryptology ePrint archive ]