# 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 H1, H2 ... Hn, 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: H1(m) || H2(m) || ... || Hn(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: H1(H2(...(Hn(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.

-
IMO, this is a bad idea. You have no rational basis to believe that your resulting function is any more secure than any other unbroken hash function that produces an output of the same length. Say, for example, you XOR two hash functions together. How do you know that some future researcher won't find some correlation between the bits of the two hash functions making the XOR weaker than either one alone? – David Schwartz Aug 23 '11 at 12:28
I'm aware of this, which is why I didn't include XOR in my list of proposals. I'm searching other ideas on how to make it safe. (Also, I'm not constrained on "same size".) – Paŭlo Ebermann Aug 23 '11 at 12:34
I'm just using XOR as an example. There is nothing special about XOR. My point is, whatever operation you use to combine them could add its own vulnerabilities. – David Schwartz Aug 23 '11 at 12:40

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 SHB-256(m) = SHA-256(m) XOR 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 2144 resistance, but Joux's result implies that you will not go beyond about 287.

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).

-
 Thanks. H1(m) XOR H2(m) was my next idea. – Paŭlo Ebermann♦ Jul 29 '11 at 17:53 I edited the question a bit - getting only the strength of the hardest of both is enough, even for using more space. I just want to make sure that I don't somehow get less than the security of the hardest (without knowing which is harder). (I'll still have to read most of your links.) – Paŭlo Ebermann♦ Jul 29 '11 at 19:08 @Paulo: getting both preimage resistance and collision resistance looks like an interesting problem. I am not aware of any existing research on the subject. For second-preimage, this is easy: resistance to second preimages it at least equal to resistance to collisions (we usually want it to be higher, but that's already something). – Thomas Pornin Jul 30 '11 at 2:42

You were right with your ideas in the the original question. If what you want to protect against is pre-images then chaining hash functions produces a function at least as strong as the strongest of its two components:

H∘(x) = H₀(H₁(x))

If what you want to protect against is collisions, then concatenation is at least as strong as the strongest of its two components:

H|(x) = H₀(x) | H₁(x)

There are several other properties that you might want from your combined function, such as pseudorandomness. For pseudorandomness, you could combine two hash functions like this:

H⊕(x) = H₀(x) ⊕ H₁(x)

The tricky part (as you observed) is if you want to have more than one of these properties. The best research about this that I'm aware of so far is Anja Lehmann's dissertation. (You can find discussion of this and related topics on the "One Hundred Year Cryptography" wiki at the Tahoe-LAFS project.)

If I needed more than one property from a secure hash function, and didn't mind extra CPU cycles, and didn't mind double the output size, then I would probably use Lehmann's Comb₄ₚ construction and not worry too much about the rather remote possibility that the resulting combined function is vulnerable (second) pre-image resistance.

If you're sure that you only need one property (careful here—think very carefully about this and write down explicitly what property or properties you rely on, and what an attacker can do if each possible property doesn't hold), then you can safely use one of the combiners above.

By the way, that dissertation also includes very interesting results on two other topics that have been discussed in this thread: whether you can have a combined function C(H₁, H₂) that is stronger at collision-resistance than the strength of H₁ plus the strength of H₂ (she answers in the affirmative) and whether the way that SSL and TLS combined SHA1 and MD5 was secure (answer: sort of...).

-
I always feel nervous directly feeding the result of one hash function into another. I know that theoretically it's supposed to be just fine, but somehow it seems like maybe my output range will in actuality be smaller than the full possible output range. Of course, if I just fed it in concatenated with itself I'd feel better about it, but that's probably also a bit silly. – Omnifarious Aug 4 '11 at 23:12
@Omnifarious: I think this is the reason one usually uses H₀(H₁(x)|X) or such instead of directly H₀(H₁(x)) - to have the improved preimage resistance, while still not having more collisions than with only one hash. – Paŭlo Ebermann Aug 5 '11 at 0:35
@Zooko: Thanks, I'll have a look at this dissertation you linked. – Paŭlo Ebermann Aug 5 '11 at 0:36

I'm sure @Thomas will give a thorough answer. In the interm, I'll just point out that the collision resistance of your first construction, H1(m)||H2(M) is surprisingly not that much better than just H1(M). See section 4 of this paper:

http://web.cecs.pdx.edu/~teshrim/spring06/papers/general-attacks/multi-joux.pdf

-
Thanks, I'm just now reading this. – Paŭlo Ebermann Jul 29 '11 at 17:28
In fact, I was content of having resistance(combination) = max(resistance(H1), resistance(H2)), for all useful values of resistance (preimage, collision, second-preimage). – Paŭlo Ebermann Jul 29 '11 at 17:56
It looks like the attacks described here all work from a collision in the compressing function to generate multi-attacks on long messages by selecting the right blocks for individual messages. They don't really apply on short messages (about hash output size or such), or messages of some fixed format (without enough space to insert random collisions), I think. – Paŭlo Ebermann Jul 29 '11 at 18:07

Well, I see two clean ways of having practical resistance to these vulnerabilities.

If you want to use two hash functions, make sure you feed back the original data in a HMAC to the second function:

hash = algo1(data)
hash = hmac(algo2, data, hash)


The benefit here is that any collisions for algo1 will not automatically become collisions for algo2 due to the MAC. So for a collision attack to work, the attacker would have to find a collision for both functions using the same source data. This should in practice be significantly more difficult than attacking either function independently (it will be at least as difficult as attacking the strongest of the two functions).

The other method would be to simply iterate a single hash function (with feedback). This looks similar to the previous algorithm.

hash = hmac(algo1, pack('N', 1), data)
for (i = 0 ... n)
hash ^= hmac(algo1, hash, data)


Where n is greater than or equal to 0. The larger it is, the slower it will be to compute. Note that this is basically just PBKDF2 with an empty salt and the length parameter set to the output size of the hash.

The benefit to "stretching" is that it protects against both preimage and collision attacks since even if the attacker was able to find a preimage for the first round, that still leaves them multiple rounds to attack. And considering the feedback, the data necessary to attack a specific round is destroyed on the next one. So even if the attacker did manage to get one round of a preimage attack done, it would be very difficult (if not impossible) to attack the other rounds.

-
 I don't see the point. Sure, collisions for algo1 won't automatically become collisions for algo2. But your overall algorithm could have collisions that none of the the underlying algorithms have. I see no rational basis to think that the new collisions created aren't likely to be worse than the possible collisions in the underlying hash functions. On the bright side, this will probably be no weaker than the stronger of the two hash functions. So you're probably okay if one of them is broken but not both of them. – David Schwartz Aug 23 '11 at 12:30 @David: Well, nothing's going to help you if both of them are broken... The point was to be as secure as the most secure function (if not better)... – ircmaxell Aug 23 '11 at 15:18

There is a research paper explaining why chain hashes do not provide better security in the sense of indifferentiability from random oracles

-
But this question isn't really about H(H(x)) with H being the same hash in both cases. – CodesInChaos Feb 6 at 15:21
Thanks for the link, but the paper doesn't really apply to my case of different hash functions. – Paŭlo Ebermann Feb 6 at 18:52
It was my misunderstanding of your question.I didn't check thoroughly the case of different hash functions. – curious Feb 6 at 19:42