Challenging the increased resistance of regular hash functions against birthday attacks

Journal of mathematical cryptology

article

Nicky Mouha¹  Gautham Sekar²  Bart Preneel¹ 

[1] Katholieke Universiteit Leuven;Indian Statistical Institute, Chennai Centre, SETS Campus, CIT Campus

关键词: Hash function;    balance;    regularity;    birthday attack;    (linear) subset regularity;    random function;   

DOI  :  10.1515/jmc-2011-0010

学科分类：社会科学、人文和艺术（综合）

来源: De Gruyter

【 摘 要 】

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.

【 授权许可】

CC BY|CC BY-NC-ND