国際会議

LimitedBirthday Distinguishers for Hash Functions—Collisions beyond the Birthday Bound Can Be Meaningful
 著者
 M. Iwamoto, T. Peyrin, and Y. Sasaki
 会議名
 ASIACRYPT 2013
 巻
 LNCS 8269
 ページ
 505–523
 発行年
 2013
Abstract
In this article, we investigate the use of limitedbirthday distinguishers to the context of hash functions. We first provide a proper understanding of the limitedbirthday 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 limitedbirthday 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 limitedbirthday 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 semifreestart 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 semifreestart 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 RIPEMD128, SHA256, Whirlpool, etc.