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 quite 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, 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, and the expected number of trials to find a collision, as a function of the balance of the hash function being attacked. In particular, we will see that the number of trials 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.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Bellare, M., Kohno, T.: Hash function balance and its impact on birthday attacks. IACR ePrint archive, http://eprint.iacr.org/2003/065/ Full version of this paper
Damgård, I.: A design principle for hash functions. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 416–427. Springer, Heidelberg (1990)
Dobbertin, H., Bosselaers, A., Preneel, B.: RIPEMD-160, a strengthened version of RIPEMD. In: Gollmann, D. (ed.) FSE 1996. LNCS, vol. 1039, Springer, Heidelberg (1996)
Menezes, A., van Oorschot, P., Vanstone, S.: Handbook of applied cryptography. CRC Press, Boca Raton (1997)
Merkle, R.: One way hash functions and DES. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 428–446. Springer, Heidelberg (1990)
National Institute of Standards. FIPS 180-2, Secure hash standard. August 1 (2000)
Rivest, R.: The MD5 message-digest algorithm. IETF RFC 1321 (April 1992)
Stinson, D.: Cryptography theory and practice, 1st edn. CRC Press, Boca Raton (1995)
van Oorschot, P., Wiener, M.: Parallel collision search with cryptanalytic applications. Journal of Cryptology 12(1), 1–28 (1999)
Yuval, G.: How to swindle Rabin. Cryptologia (3), 187–190 (1979)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bellare, M., Kohno, T. (2004). Hash Function Balance and Its Impact on Birthday Attacks. In: Cachin, C., Camenisch, J.L. (eds) Advances in Cryptology - EUROCRYPT 2004. EUROCRYPT 2004. Lecture Notes in Computer Science, vol 3027. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-24676-3_24
Download citation
DOI: https://doi.org/10.1007/978-3-540-24676-3_24
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-21935-4
Online ISBN: 978-3-540-24676-3
eBook Packages: Springer Book Archive