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_{4P}$ construction and not worry too much about the rather remote possibility that the resulting combined function may not preserve 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...).

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_{\circ}(x) = H_0(H_1(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_0(x) | H_1(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_{\oplus}(x) = H_0(x) \oplus H_1(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_{4P}$ construction and not worry too much about the rather remote possibility that the resulting combined function may not preserve 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_1, H_2)$ that is stronger at collision-resistance than the strength of $H_1$ plus the strength of $H_2$ (she answers in the affirmative) and whether the way that SSL and TLS combined SHA1 and MD5 was secure (answer: sort of...).

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

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_{4P}$ construction and not worry too much about the rather remote possibility that the resulting combined function may not preserve 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...).