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 r1/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 r1/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).