Paper 2003/065
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.
Metadata
- Available format(s)
-
PDF
PS
- Publication info
- Published elsewhere. A preliminary version of this paper appeared in Eurocrypt 2004. This is a significantly revised and expanded full version.
- Keywords
- hash functionsbirthday attacks
- Contact author(s)
- mihir @ cs ucsd edu
- History
- 2004-11-27: last of 6 revisions
- 2003-04-08: received
- See all versions
- Short URL
- https://ia.cr/2003/065
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2003/065,
author = {Mihir Bellare and Tadayoshi Kohno},
title = {Hash Function Balance and its Impact on Birthday Attacks},
howpublished = {Cryptology ePrint Archive, Paper 2003/065},
year = {2003},
note = {\url{https://eprint.iacr.org/2003/065}},
url = {https://eprint.iacr.org/2003/065}
}
