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 .