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.