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
-
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},
url = {https://eprint.iacr.org/2010/602}
}
