Paper 2009/325

Characterizing Padding Rules of MD Hash Functions Preserving Collision Security

Mridul Nandi


This paper characterizes collision preserving padding rules and provides variants of \MD (MD) which are having less or no overhead costs due to length. We first show that suffix-free property of padding rule is necessary as well as sufficient to preserve the collision security of MD hash function for an arbitrary domain $\s^*$. Knowing this, we propose a simple suffix-free padding rule padding only $\log |M|$ bits for a message $M$, which is less than that of Damg\aa rd's and Sarkar's padding rules. We also prove that the length-padding is not absolutely necessary. We show that a simple variant of MD with $10^d$-padding (or any injective padding) is collision resistant provided that the underlying compression function is collision resistant after chopping the last-bit. Finally, we design another variant of MD hash function preserving all three basic security notions of hash functions, namely collision and (2nd) preimage. This is an improvement over a recently designed (SAC-08) three-property preserving hash function in terms of both salt size and efficiency.

Note: This is the full version of ACISP 2009 paper. The previous paper contains an error. This version has fixed the error.

Available format(s)
Publication info
Published elsewhere. ACISP 2009
MD hash functionpadding rulesuffix-freecollision resistant.
Contact author(s)
mridul nandi @ gmail com
2009-07-08: revised
2009-07-07: received
See all versions
Short URL
Creative Commons Attribution


      author = {Mridul Nandi},
      title = {Characterizing Padding Rules of MD Hash Functions Preserving Collision Security},
      howpublished = {Cryptology ePrint Archive, Paper 2009/325},
      year = {2009},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.