Towards Secure and Fast Hash Functions

Takashi SATOH  Mio HAGA  Kaoru KUROSAWA  

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

Full Text: PDF>>
Buy this Article

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.