International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Generic Collision Attacks on Narrow-pipe Hash Functions Faster than Birthday Paradox, Applicable to MDx, SHA-1, SHA-2, and SHA-3 Narrow-pipe Candidates

Authors:
Vlastimil Klima
Danilo Gligoroski
Download:
URL: http://eprint.iacr.org/2010/430
Search ePrint
Search Google
Abstract: In this note we show a consequence of the recent observation that narrow-pipe hash designs manifest an abberation from ideal random functions for finding collisions for those functions with complexities much lower than the so called generic birthday paradox lower bound. The problem is generic for narrow-pipe designs including classic Merkle-Damgard designs but also recent narrow-pipe SHA-3 candidates. Our finding does not reduces the generic collision security of n/2 bits that narrow-pipe functions are declaring, but it clearly shows that narrow-pipe designs have a property when we count the calls to the hash function as a whole, the birthday paradox bound of 2^{n/2} calls to the hash function is clearly broken. This is yet another property in a series of similar non-ideal random properties (like HMAC or PRF constructions) that narrow-pipe hash function manifest and that are described in [1] and [2].
BibTeX
@misc{eprint-2010-23331,
  title={Generic Collision Attacks on Narrow-pipe Hash Functions Faster than Birthday Paradox, Applicable to MDx, SHA-1, SHA-2, and SHA-3 Narrow-pipe Candidates},
  booktitle={IACR Eprint archive},
  keywords={secret-key cryptography / hash functions, collisions, generic attack, narrow-pipe design},
  url={http://eprint.iacr.org/2010/430},
  note={ v.klima@volny.cz 14825 received 4 Aug 2010},
  author={Vlastimil Klima and Danilo Gligoroski},
  year=2010
}