Characterizing Padding Rules of MD Hash Functions Preserving Collision Security

Published

June 29, 2009

Author(s)

Mridul Nandi

Abstract

This paper characterizes collision preserving padding rules and provides variants of Merkle-Damgaard (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 {0,1}*. 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 Damgard'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, which is an improvement over a recently designed (SAC-08) three-property preserving hash function.

Proceedings Title

Information Security and Privacy (Lecture Notes in Computer Science)

Volume

5594

Conference Dates

July 1-3, 2009

Conference Location

Brisbane

Conference Title

14th Australasian Conference on Information Security and Privacy (ACISP 2009)

Pub Type

Conferences

Download Paper

https://doi.org/10.1007/978-3-642-02620-1_12

Keywords

collision resistant, MD hash function, padding rule, suffix-free

Citation

Nandi, M. (2009), Characterizing Padding Rules of MD Hash Functions Preserving Collision Security, Information Security and Privacy (Lecture Notes in Computer Science), Brisbane, -1, [online], https://doi.org/10.1007/978-3-642-02620-1_12 (Accessed May 13, 2026)

Additional citation formats