Domain extender for collision resistant hash functions: Improving upon Merkle–Damgård iteration

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 yields 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 Merkle–Damgård algorithm.