Cryptology ePrint Archive: Report 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.

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 ]