Non-full-active Super-Sbox Analysis: Applications to ECHO and Grøstl

In this paper, we present

non-full-active Super-Sbox analysis

which can detect non-ideal properties of a class of AES-based permutations with a low complexity. We apply this framework to SHA-3 round-2 candidates ECHO and Grøstl. The first application is for the full-round (8-round) ECHO permutation, which is a building block for 256-bit and 224-bit output sizes. By combining several observations specific to ECHO, our attack detects a non-ideal property with a time complexity of 2

182

and 2

37

amount of memory. The complexity, especially in terms of the product of time and memory, is drastically reduced from the previous best attack which required 2

512

×2

512

. Note that this result does not impact the security of the ECHO compression function nor the overall hash function. We also show that our method can detect non-ideal properties of the 8-round Grøstl-256 permutation with a practical complexity, and finally show that our approach improves a semi-free-start collision attack on the 7-round Grøstl-512 compression function. Our approach is based on a series of attacks on AES-based hash functions such as rebound attack and Super-Sbox analysis. The core idea is using a new differential path consisting of only non-full-active states.