Paper 2003/173

Domain Extender for Collision Resistant Hash Functions: Improving Upon Merkle-Damgaard Iteration

Palash Sarkar

Abstract

We study the problem of securely extending the domain of a collision resistant compression function. A new construction based on directed acyclic graphs is described. This generalizes the usual iterated hashing constructions. Our main contribution is to introduce a new technique for hashing arbitrary length strings. Combined with DAG based hashing, this technique gives a new hashing algorithm. The amount of padding and the number of invocations of the compression function required by the new algorithm is smaller than the general \MD algorithm. Lastly, we describe the design of a new parallel hash algorithm.

Note: Added a section indicating the non-triviality of domain extension to arbitrary length messages under the assumption that the compression function is only collision resistant.