1. IntroductionHash
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
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
|
|