Functional Graph and Hash Combiners

1. Introduction

Hash combiners are a practical way to make cryptographic hash functions more tolerant of future attacks and compatible with existing infrastructure. A combiner combines two or more hash functions in a way that is hopefully more secure than each of the underlying hash functions, or at least remains secure as long as one of them is secure. 

This webpage will present the security stature of some hash combiners, specifically on the security upper bound obtained by devising the best-known generic attacks. The results show that the security of most of the combiners is not as high as commonly believed. Some crucial and interesting techniques, such as the Interchange Structure and the Random Functional Graph are exploited.

2. Hash Combiners

Two classical hash combiners are the exclusive-or (XOR) combiner H1(M)H2(M) and the concatenation combiner H1(M)H2(M). Both of them process the same message using two (independent) hash functions Hand Hin parallel. Then, the former XORs their outputsH1(M)H2(Mand the latter concatenates them H1(M)H2(M).

More generally, cryptographers have also studied cascade constructions of two (or more) hash functions, that is, to compute  H1  and H2  in sequential order. Examples are Hash-Twice H2(H1(IV, M)M), which processes the same message twice using a single hash function (the original specification processes using a single hash function as shown in [ABDK09]), and the Zipper hash H2(H1(IV, M)M*), where M* is the message with the same blocks but in reversed order [Lis06] (such kinds of cascade constructions are not strictly black-box hash combiners compared with the XOR combiner and the concatenated combiner)

2.1 XOR Combiner


2.2 Concatenation Combiner


2.3 Zipper Hash

H2(H1(IV, M)M*)

2.4 Hash-Twice

H2(H1(IV, M)M)

3. Security Status of Various Combiners of Two Narrow-Pipe Hashes

3.1 Trade-offs curves on the complexity of attacks on parallel combiners

3.2 Trade-offs curves on the complexity of attacks on cascade combiners

3.3 Security status of various combiners of two narrow-pipe hashes