Guarding against cryptanalytic breakthroughs: combining multiple hash functions Assume I want to design a protocol (or data format or similar) including some cryptographic hash, and want it to be as future-proof as possible, i.e. I want to avoid that breakthroughs in cryptography make my old data insecure.

If I use only one hash algorithm, I can have bad luck to pick just the one which will be broken after some years.

For example, MD4 (published 1990) had first collision attacks in 1995, and as of 2007 these are even cheaper than calculating the hash itself.

So, the idea would be to combine multiple such algorithms in a way that breaking just one (or some) of them does not compromise the security of the combined construct - breaking all of them would be necessary.

I do not care about efficiency loss from calculating multiple hashes instead of one, I just want to be sure against better cryptanalysis.

So, if I have hash functions $H_1$, $H_2$, ..., $H_n$. How to combine them to form a hash function which is as secure as any of them?

Two basic ideas, which do not work as intended:


simple concatenate the outputs:  $H_1(m) || H_2(m) || ... || H_n(m)$.

This should be quite secure against collision attacks, but is only as
secure to preimage attacks as the weakest of them (and the other ones
then can be used to check if I found the right preimage).
chaining the functions: $H_1(H_2(...(H_n(m)...))$

For preimage attacks, you would now need to break all of them. But a
collision in Hn trivially leads to a collision in the result, too.
(Collisions in the others are less easy to exploit, as you then need
to have to get preimages in the previous ones.)


Any better ways of combining them? Or is this a stupid idea at all?



To clarify: I do not really need more security than the hardest of the component functions, but I want at least that much. (And using more space is not really a problem here.)

And for preimages, I'm now mainly concerned about someone finding the original preimage (which is around the size of the hashes output),  and it looks like this will be at most as difficult as for the weakest hash, in the case of simple concatenation.
I'm not so much concerned about someone constructing a new one - this sounds quite difficult, but is not so much, if the size of the message can grow as needed (one block per bit of hash or such) and we have collision attacks on the compression function, as Joux shows.
Combining is what SSL/TLS does with MD5 and SHA-1, in its definition of its internal "PRF" (which is actually a Key Derivation Function). For a given hash function, TLS defines a KDF which relies on HMAC which relies on the hash function. Then the KDF is invoked twice, once with MD5 and once with SHA-1, and the results are XORed together. The idea was to resist cryptanalytic breaks in either MD5 or SHA-1. Note that XORing the outputs of two hash functions relies on subtle assumptions. For instance, if I define $\mathrm{SHB-}256(m) = \mathrm{SHA-}256(m) \oplus C$, for a fixed constant $C$, then SHB-256 is as good a hash function as SHA-256; but the XOR of both always yields $C$, which is not good at all for hashing purposes. Hence, the construction in TLS in not really sanctioned by the authority of science (it just happens not to have been broken). TLS-1.2 does not use that combination anymore; it relies on the KDF with a single, configurable hash function, often SHA-256 (which is, in 2011, a smart choice).

As @PulpSpy points out, concatenation is not a good generic way of building hash functions. This was published by Joux in 2004 and then generalized by Hoch and Shamir in 2006, for a large class of construction involving iterations and concatenations. But mind the fine print: this is not really about surviving weaknesses in hash functions, but about getting your money worth. Namely, if you take a hash function with a 128-bit output and another with a 160-bit output, and concatenate the results, then collision resistance will be no worse than the strongest of the two; what Joux showed is that it will not be much better either. With $128+160 = 288$ bits of output, you could aim at $2^{144}$ resistance, but Joux's result implies that you will not go beyond about $2^{87}$.

So the question becomes: is there a way, if possible an efficient way, to combine two hash functions such that the result is as collision-resistant as the strongest of the two, but without incurring the output enlargement of concatenation ? In 2006, Boneh and Boyen have published a result which simply states that the answer is no, subject to the condition of evaluating each hash function only once. 

Edit: Pietrzak lifted the latter condition in 2007 (i.e. invoking each hash function several times does not help).