eprint.iacr.org will be offline for approximately an hour for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between April 12 and April 14, and some authors have been notified that they need to resubmit their papers.

Paper 2010/602

An Improved Algebraic Attack on Hamsi-256

Itai Dinur and Adi Shamir


Hamsi is one of the $14$ second-stage candidates in NIST's SHA-3 competition. The only previous attack on this hash function was a very marginal attack on its 256-bit version published by Thomas Fuhr at Asiacrypt $2010$, which is better than generic attacks only for very short messages of fewer than $100$ 32-bit blocks, and is only $26$ times faster than a straightforward exhaustive search attack. In this paper we describe a different algebraic attack which is less marginal: It is better than the best known generic attack for all practical message sizes (up to $4$ gigabytes), and it outperforms exhaustive search by a factor of at least $512$. The attack is based on the observation that in order to discard a possible second preimage, it suffices to show that one of its hashed output bits is wrong. Since the output bits of the compression function of Hamsi-256 can be described by low degree polynomials, it is actually faster to compute a small number of output bits by a fast polynomial evaluation technique rather than via the official algorithm.

Note: Updated according to comments by anonymous referees

Available format(s)
Secret-key cryptography
Publication info
Published elsewhere. Extended version of the paper that appears in FSE 2011
Algebraic attackssecond preimageshash functionsHamsi
Contact author(s)
itai dinur @ weizmann ac il
2011-03-20: revised
2010-11-25: received
See all versions
Short URL
Creative Commons Attribution


      author = {Itai Dinur and Adi Shamir},
      title = {An Improved Algebraic Attack on Hamsi-256},
      howpublished = {Cryptology ePrint Archive, Paper 2010/602},
      year = {2010},
      note = {\url{https://eprint.iacr.org/2010/602}},
      url = {https://eprint.iacr.org/2010/602}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.