Towards Secure and Fast Hash Functions

Takashi SATOH  Mio HAGA  Kaoru KUROSAWA 

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences  Vol.E82-A  No.1  pp.55-62
Publication Date: 1999/01/20
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
Category: 
Keyword: 
cryptanalysis,  hash function,  block cipher,  meet-in-the-middle attack,  birthday attack, 

Full Text: PDF(168.3KB)

Summary: 
We analyze the security of iterated 2m-bit hash functions with rate 1 whose round functions use a block cipher with an m-bit input (output) and a 2m-bit key. We first show a preimage attack with O(2m) complexity on Yi and Lam's hash function of this type. This means that their claim is wrong and it is less secure than MDC-2. Next, it is shown that a very wide class of such functions is also less secure than MDC-2. More precisely, we prove that there exist a preimage attack and a 2nd preimage attack with O(2m) complexity and a collision attack with O(23m/4) complexity, respectively. Finally, we suggest a class of hash functions with a 2m-bit hashed value which seem to be as secure as MDC-2.