Cryptology ePrint Archive: Report 2009/325
Characterizing Padding Rules of MD Hash Functions Preserving Collision Security
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.
Category / Keywords: foundations / MD hash function, padding rule, suffix-free, collision resistant.
Publication Info: ACISP 2009
Date: received 1 Jul 2009, last revised 8 Jul 2009
Contact author: mridul nandi at gmail com
Available format(s): PDF | BibTeX Citation
Note: This is the full version of ACISP 2009 paper. The previous paper contains an error. This version has fixed the error.
Version: 20090708:125142 (All versions of this report)
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]