# Can insecure algorithms be combined to form a secure algorithm?

This is hypothetical as I can't think of any reason to do this, but out of curiosity...

Could I, for example, take the MD5 digest of a message and concatenate it with the SHA-1 digest (not quite broken, but getting close), to form a secure concatenated digest? Intuitively, I would think the chances of finding a collision that crossed the two algorithms would be low enough to make this secure, but I'm not sure how to verify that.

-
is this edit the correct interpretation of your question? if so then it would be a duplicate – figlesquidge Dec 6 '13 at 10:02
@figlesquidge You are correct, that edit completely changed the content of the question... rolled back to the original question that OP posted. – e-sushi Dec 6 '13 at 17:31

At the time of answering, the question was can insecure algorithms be combined to form a secure algorithm?

Yes: Think of any secure round-based block cipher. The independent rounds are not secure, but put together the overall cipher is. I think my favourite example is (currently) the Even Mansour cipher, which combines two xor operations and one unkeyed permutation to form a secure cipher.

nb: I know this isn't a direct link, but its the best introduction I know of

For a good discussion of the hash example in your question, read this question.

-
Thanks for the link to the other question. I didn't even think of pre-image resistance (I guess that's why I don't design hashes). So concatenation is out. – ConditionRacer Dec 4 '13 at 17:09
@downvote: What do you suggest would improve this answer? – figlesquidge Dec 6 '13 at 11:05

Combining two hash functions is exactly what the PRF does in the original TLS 1.1 specification.

Half of the message (secret) is put through MD5 while the other half is put through SHA-1, and the two outputs are XOR'd together:

$PRF(secret, label, seed) = P_{MD5}(S1, label + seed) \; \otimes \; P_{SHA-1}(S2, label + seed);$

TLS's PRF is created by splitting the secret into two halves and using one half to generate data with P_MD5 and the other half to generate data with P_SHA-1, then exclusive-ORing the outputs of these two expansion functions together.

With the assumption that

TLS uses hash functions very conservatively. Where possible, both MD5 and SHA are used in tandem to ensure that non-catastrophic flaws in one algorithm will not break the overall protocol.

So it appears that the designers believed this to be safe. However, this has been updated in TLS 1.2, and the PRF hash function is no longer fixed to use MD5 or SHA-1.

-
But they aim at pseudo-randomness, not collision resistance and they xor the hashes instead of concatenating them. – CodesInChaos Dec 6 '13 at 12:46
Also, they are hoping it will be safe, but there is no proof that this is safe. – D.W. Dec 6 '13 at 18:52
This thesis by Anja Lehmann: On the Security of Hash function combiners contains good amount of investigation on this and various other similar constructs. – user4982 Dec 6 '13 at 19:25
@CodesInChaos In SSL they were concatenated if I'm not mistaken, for the same reason. – Maarten Bodewes Jan 21 '14 at 0:39

Maybe. If the algorithms are individually broken, and your design is open (i.e. no “security” by obscurity), then chances are your scheme will also be broken more easily.

In the case of hash algorithms, “broken” usually means finding collisions or second preimages, which will differ between algorithms, so yes, this will work. With the caveat above, of course ;-)

-