[Resource Topic] 2003/065: Hash Function Balance and its Impact on Birthday Attacks

Welcome to the resource topic for 2003/065

Hash Function Balance and its Impact on Birthday Attacks

Authors: Mihir Bellare, Tadayoshi Kohno


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.

ePrint: https://eprint.iacr.org/2003/065

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .