Title: Challenging the Increased Resistance of Regular Hash Functions Against Birthday Attacks
Authors: Mouha, Nicky
Sekar, Gautham
Preneel, Bart #
Issue Date: 20-May-2011
Host Document: pages:1-18
Conference: ECRYPT II Hash Workshop edition:2011 location:Tallinn, Estonia date:19-20 May 2011
Abstract: At EUROCRYPT 2004, Bellare and Kohno presented the concept of a regular hash function. For a hash function to be regular, every hash value must have the same number of preimages in the domain. The findings of their paper remained unchallenged for over six years, and made their way into several research papers and textbooks. In their paper, Bellare and Kohno claim that regular hash functions are more resistant against the birthday attack than random hash functions. We counter their arguments, by showing that the success probability of the birthday attack against a regular hash function can be made arbitrarily close to that of a random hash function (for the same number of trials). Our analysis uses the fact that the choices of the attacker can be limited to any subset of the domain. Furthermore, we prove that it is not possible to construct a hash function that is regular for only a small fraction of subsets of the domain. In order to avoid these problems, we propose to model hash functions as random functions. Compared to regular functions, we argue that the statistics of random functions are more similar to hash functions used in practice, regardless of how the attacker chooses the domain points.
Publication status: published
KU Leuven publication type: IC
Appears in Collections:ESAT - STADIUS, Stadius Centre for Dynamical Systems, Signal Processing and Data Analytics
Electrical Engineering - miscellaneous
# (joint) last author

Files in This Item:
File Description Status SizeFormat
article-2044.pdf Published 207KbAdobe PDFView/Open


All items in Lirias are protected by copyright, with all rights reserved.