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

Abstract

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

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

BibTeX

@misc{cryptoeprint:2010/602,
      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.