Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

Characterizing Padding Rules of MD Hash Functions Preserving Collision Security

Published

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)

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 March 1, 2024)
Created June 29, 2009, Updated November 10, 2018