Cryptology ePrint Archive: Report 2010/588

Improved Collisions for Reduced ECHO-256

Martin Schläffer

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.

Category / Keywords: secret-key cryptography / hash functions, SHA-3 competition, ECHO, cryptanalysis, truncated differential path, rebound attack, collision attack

Date: received 18 Nov 2010, last revised 23 Nov 2010

Contact author: martin schlaeffer at iaik tugraz at

Available format(s): PDF | BibTeX Citation

Version: 20101123:080839 (All versions of this report)

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]