Paper 2006/135

The Design Principle of Hash Function with Merkle-Damgård Construction

Duo Lei, Da Lin, Li Chao, Keqin Feng, and Longjiang Qu


The paper discusses the security of hash function with Merkle-Damgå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å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.

Note: The paper has not been submited. The result of the paper is different from traditional understading of compression function of hash function. We expect any comment on the paper.

Available format(s)
Secret-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Hash functionsBlock cipherscomplexity theory
Contact author(s)
duoduolei @ 163 com
2006-05-12: last of 7 revisions
2006-04-09: received
See all versions
Short URL
Creative Commons Attribution


      author = {Duo Lei and Da Lin and Li Chao and Keqin Feng and Longjiang Qu},
      title = {The Design Principle of Hash Function with Merkle-Damgård Construction},
      howpublished = {Cryptology ePrint Archive, Paper 2006/135},
      year = {2006},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.