International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: The Design Principle of Hash Function with Merkle-Damg{\aa}rd Construction

Duo Lei
Da Lin
Li Chao
Keqin Feng
Longjiang Qu
Search ePrint
Search Google
Abstract: The paper discusses the security of hash function with Merkle-Damg{\aa}rd construction and provides the complexity bound of finding a collision and primage of hash function based on the condition probability of compression function $y=F(x,k)$. we make a conclusion that in Merkle-Damma{\aa}rd construction, the requirement of free start collision resistant and free start collision resistant on compression function is not necessary and it is enough if the compression function with properties of fix start collision resistant and fix start preimage resistant. However, the condition probability $P_{Y|X=x}(y)$ and $P_{Y|K=k}(y)$ of compression function $y=F(x,k)$ have much influence on the security of the hash function. The best design of compression function should have properties of that $P_{Y|X=x}(y)$ and $P_{Y|K=k}(y)$ are both uniformly distributed for all $x$ and $k$. At the end of the paper, we discussed the block cipher based hash function, point out among the the 20 schemes, selected by PGV\cite{Re:Preneel} and BPS\cite{Re:JBlack}, the best scheme is block cipher itself, if the block cipher with perfect security and perfect key distribution.
  title={The Design Principle of Hash Function with Merkle-Damg{\aa}rd Construction},
  booktitle={IACR Eprint archive},
  keywords={secret-key cryptography / Hash functions, Block ciphers, complexity theory},
  note={ 13280 received 5 Apr 2006, last revised 11 May 2006},
  author={Duo Lei and Da Lin and Li Chao and Keqin Feng and Longjiang Qu},