Paper 2009/210

Sufficient conditions for sound tree and sequential hashing modes

Guido Bertoni and Joan Daemen and Michael Peeters and Gilles Van Assche

Abstract

While sequential hashing is often used in practice and requires relatively less memory than tree hashing, the latter has several advantages such as parallelism and a lower cost of hash value recomputation when only a small part of the input changes. In this paper we consider the general case of tree hashing modes that make use of an underlying (sequential) hash function. We formulate a set of four simple conditions, which are easy to implement and to verify, for such a (either sequential or tree) hashing mode to be sound. We provide a proof that for any hashing mode satisfying these four conditions, the advantage in differentiating it from an ideal monolithic hash function is upper bounded by $q^2/2^{n+1}$ with $q$ the number of queries to the underlying hash function and $n$ the length of the chaining values. We show how to apply tree hashing modes to sequential hash functions in an optimal way, demonstrate the applicability of our conditions with two efficient and simple tree hashing modes and provide a simple method to take the union of tree hashing modes that preserves soundness. It turns out that sequential hashing modes using a compression function (i.e., a hash function with fixed input length) can be considered as particular cases and, as a by-product, our results also apply to them. For three of the four conditions (parameter-completeness is trivial for sequential modes), we discuss the different techniques for satisfying them, thereby shedding a new light on several published modes.

Note: Changes detailed in Appendix A.