Paper 2010/588 Original: eprint.iacr.org/2010/588 ↗

Improved Collisions for Reduced ECHO-256

Abstract

In this work, we present a collision attack on 5 out of 8 rounds of the ECHO-256 hash function with a complexity of $2^{112}$ in time and $2^{85.3}$ memory. In this work, we further show that the merge inbound phase can still be solved in the case of hash function attacks on ECHO. As correctly observed by Jean et al., the merge inbound phase of previous hash function attacks succeeds only with a probability of $2^{-128}$. The main reason for this behavior is the low rank of the linear SuperMixColumns transformation. However, since there is enough freedom in ECHO we can solve the resulting linear equations with a complexity much lower than $2^{128}$. On the other hand, also this low rank of the linear SuperMixColumns transformation allows us to extend the collision attack on the reduced hash function from 4 to 5 rounds. Additionally, we present a collision attack on 6 rounds of the compression function of ECHO-256 and show that a subspace distinguisher is still possible for 7 out of 8 rounds of the compression function of ECHO-256. Both compression function attacks have a complexity of $2^{160}$ with memory requirements of $2^{128}$ and chosen salt.