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

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
hash functionsSHA-3 competitionECHOcryptanalysistruncated differential pathrebound attackcollision attack
Contact author(s)
martin schlaeffer @ iaik tugraz at
History
2010-11-23: last of 2 revisions
2010-11-20: received
See all versions
Short URL
https://ia.cr/2010/588
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2010/588,
      author = {Martin Schläffer},
      title = {Improved Collisions for Reduced ECHO-256},
      howpublished = {Cryptology ePrint Archive, Paper 2010/588},
      year = {2010},
      note = {\url{https://eprint.iacr.org/2010/588}},
      url = {https://eprint.iacr.org/2010/588}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.