Paper 2013/611

Limited-birthday Distinguishers for Hash Functions - Collisions Beyond the Birthday Bound can be Meaningful

Mitsugu Iwamoto, Thomas Peyrin, and Yu Sasaki

Abstract

In this article, we investigate the use of limited-birthday distinguishers to the context of hash functions. We first provide a proper understanding of the limited-birthday problem and demonstrate its soundness by using a new security notion Differential Target Collision Resistance (dTCR) that is related to the classical Target Collision Resistance (TCR) notion. We then solve an open problem and close the existing security gap by proving that the best known generic attack proposed at FSE 2010 for the limited-birthday problem is indeed the best possible method. 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.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published by the IACR in ASIACRYPT 2013
Keywords
hash functioncompression functiondistinguisherlimited-birthdaysemi-free-start collisiondifferential target collision resistance
Contact author(s)
thomas peyrin @ gmail com
History
2013-09-25: revised
2013-09-23: received
See all versions
Short URL
https://ia.cr/2013/611
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2013/611,
      author = {Mitsugu Iwamoto and Thomas Peyrin and Yu Sasaki},
      title = {Limited-birthday Distinguishers for Hash Functions - Collisions Beyond the Birthday Bound can be Meaningful},
      howpublished = {Cryptology ePrint Archive, Paper 2013/611},
      year = {2013},
      note = {\url{https://eprint.iacr.org/2013/611}},
      url = {https://eprint.iacr.org/2013/611}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.