**Hash Function Balance and its Impact on Birthday Attacks**

*Mihir Bellare and Tadayoshi 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, \textit{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-Damgård) transform, from the
point of view of balance preservation, and to mount experiments to determine
the balance of popular hash functions.

**Category / Keywords: **hash functions, birthday attacks

**Publication Info: **A preliminary version of this paper appeared in Eurocrypt 2004. This is a significantly revised and expanded full version.

**Date: **received 8 Apr 2003, last revised 27 Nov 2004

**Contact author: **mihir at cs ucsd edu

**Available format(s): **Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

**Version: **20041127:182311 (All versions of this report)

**Short URL: **ia.cr/2003/065

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]