Preimage Attacks on Round-Reduced KECCAK-224/256 via an Allocating Approach

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).