Paper 2009/525

On Quantifying the Resistance of Concrete Hash Functions to Generic Multi-Collision Attacks

Somindu C. Ramanna and Palash Sarkar

Abstract

Bellare and Kohno (2004) introduced the notion of balance to quantify the resistance of a hash function h to a generic collision attack. Motivated by their work, we consider the problem of quantifying the resistance of h to a generic multi-collision attack. To this end, we introduce the notion of r-balance μr(h) of h and obtain bounds on the success probability of finding an -collision in terms of . These bounds show that for a hash function with image points, if the number of trials is , then it is possible to find -collisions with a significant probability of success. The behaviour of random functions and the expected number of trials to obtain an -collision is studied. These results extend and complete the earlier results obtained by Bellare and Kohno (2004) for collisions (i.e., ). Going beyond their work, we provide a new design criteria to provide quantifiable resistance to generic multi- collision attacks. Further, we make a detailed probabilistic investigation of the variation of -balance over the set of all functions and obtain support for the view that most functions have -balance close to one.

Metadata
Available format(s)
PDF PS
Category
Foundations
Publication info
Published elsewhere. Unknown where it was published
Keywords
hash functionsmulti-collisionsbirthday attacks
Contact author(s)
somindu cr @ gmail com
History
2010-06-14: last of 3 revisions
2009-11-02: received
See all versions
Short URL
https://ia.cr/2009/525
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2009/525,
      author = {Somindu C.  Ramanna and Palash Sarkar},
      title = {On Quantifying the Resistance of Concrete Hash Functions  to Generic Multi-Collision Attacks},
      howpublished = {Cryptology {ePrint} Archive, Paper 2009/525},
      year = {2009},
      url = {https://eprint.iacr.org/2009/525}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.