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 ${\mu }_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.