##
Hash function balance and its impact on birthday attacks

** Authors: M. Bellare and T. Kohno
**
** Abstract: ** Textbooks tell us that a birthday attack on a hash function
h with range size r requires r^{1/2} trials (hash computations) to find
a collision. But this is misleading, being true only if h is regular, meaning
all points in the range have the same number of pre-images under h; if h is not
regular, * fewer * trials may be required. But how much fewer? This paper
addresses this question by introducing a measure of the ``amount of
regularity'' of a hash function that we call its balance, and then providing
estimates of the success-rate of the birthday attack as a function of the
balance of the hash function being attacked. In particular, we will see that
the number of trials to find a collision can be significantly less than
r^{1/2} for hash functions of low balance. This leads us to examine
popular design principles, such as the MD (Merkle-Damgard) transform, from the
point of view of balance preservation, and to mount experiments to determine
the balance of popular hash functions.

** Ref:** An extended abstract of this paper appeared in Advances in
Cryptology - Eurocrypt 2004 Proceedings, Lecture Notes in Computer Science
Vol. 3027, C. Cachin and J. Camenisch eds, Springer-Verlag, 2004.
Full paper available below.

** Full paper: ** Available as
compressed postscript, postscript, or pdf. ( Help if this
doesn't work).