Welcome to the resource topic for
**2003/065**

**Title:**

Hash Function Balance and its Impact on Birthday Attacks

**Authors:**
Mihir Bellare, 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.

**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 .