Paper 2009/325

Characterizing Padding Rules of MD Hash Functions Preserving Collision Security

Mridul Nandi

Abstract

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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. ACISP 2009
Keywords
MD hash functionpadding rulesuffix-freecollision resistant.
Contact author(s)
mridul nandi @ gmail com
History
2009-07-08: revised
2009-07-07: received
See all versions
Short URL
https://ia.cr/2009/325
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2009/325,
      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{https://eprint.iacr.org/2009/325}},
      url = {https://eprint.iacr.org/2009/325}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.