Paper 2009/325 Original: eprint.iacr.org/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.