Moreover, we show that almost all known collision attacks are in fact more than just a collision finding algorithm, since the difference mask for the message input is usually fixed. A direct and surprising corollary is that these collision attacks are interesting for cryptanalysis even when their complexity goes beyond the $2^{n/2}$ birthday bound and up to the $2^{n}$ preimage bound, and can be used to derive distinguishers using the limited-birthday problem. Interestingly, cryptanalysts can now search for collision attacks beyond the $2^{n/2}$ birthday bound.
Finally, we describe a generic algorithm that turns a semi-free-start collision attack on a compression function (even if its complexity is beyond the birthday bound) into a distinguisher on the whole hash function when its internal state is not too wide. To the best of our knowledge, this is the first result that exploits classical semi-free-start collisions on the compression function to exhibit a weakness on the whole hash function. As an application of our findings, we provide distinguishers on reduced or full version of several hash functions, such as RIPEMD-128, SHA-256, Whirlpool, etc.
Category / Keywords: secret-key cryptography / hash function, compression function, distinguisher, limited-birthday, semi-free-start collision, differential target collision resistance Original Publication (in the same form): IACR-ASIACRYPT-2013 Date: received 21 Sep 2013, last revised 25 Sep 2013 Contact author: thomas peyrin at gmail com Available format(s): PDF | BibTeX Citation Version: 20130925:163120 (All versions of this report) Short URL: ia.cr/2013/611 Discussion forum: Show discussion | Start new discussion