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 H1 and H2 in parallel. Then, the former XORs their outputs, H1(M)⊕H2(M) and 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


H1(M)⊕H2(M)

2.2 Concatenation Combiner


H1(M)∥H2(M)

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


References

[ABDK09]. Elena Andreeva, Charles Bouillaguet, Orr Dunkelman, and John Kelsey. Herding, Second Preimage and Trojan Message Attacks Beyond Merkle-Damgård. In SAC 2009.

[BDG+19]. Zhenzhen Bao, Itai Dinur, Jian Guo, Gaëtan Leurent, and Lei Wang. Generic Attacks on Hash Combiners. Journal of Cryptology, 2019.

[BWGG17]. Zhenzhen Bao, Lei Wang, Jian Guo, and Dawu Gu. Functional Graph Revisited: Updates on (Second) Preimage Attacks on Hash Combiners. In CRYPTO 2017.

[Din16]. Itai Dinur. New Attacks on the Concatenation and XOR Hash Combiners. In EUROCRYPT 2016.

[HS08]. Jonathan J. Hoch and Adi Shamir. On the Strength of the Concatenated Hash Combiner When All the Hash Functions Are Weak. In ICALP 2008.

[KS05]. John Kelsey and Bruce Schneier. Second Preimages on n-bit Hash Functions for Much Less Than 2n work. In EUROCRYPT 2005.

[Lis06]. Moses Liskov. Constructing an Ideal Hash Function from Weak Ideal Compression Functions. In  SAC 2006.

[LW15]. Gaëtan Leurent and Lei Wang. The Sum Can Be Weaker Than Each Part. In EUROCRYPT 2015.