Non-full-active Super-Sbox Analysis: Applications to ECHO and Gr0stl

摘要

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 Grostl. 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 2512 × 2512. 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 Grostl-256 permutation with a practical complexity, and finally show that our approach improves a semi-free-start collision attack on the 7-round Grostl-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.