4
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ is this edit the correct interpretation of your question? if so then it would be a duplicate $\endgroup$
    – Cryptographeur
    Commented Dec 6, 2013 at 10:02
  • $\begingroup$ @figlesquidge You are correct, that edit completely changed the content of the question... rolled back to the original question that OP posted. $\endgroup$
    – e-sushi
    Commented Dec 6, 2013 at 17:31

3 Answers 3

Reset to default
7
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – ConditionRacer
    Commented Dec 4, 2013 at 17:09
  • 2
    $\begingroup$ @downvote: What do you suggest would improve this answer? $\endgroup$
    – Cryptographeur
    Commented Dec 6, 2013 at 11:05
3
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • 3
    $\begingroup$ But they aim at pseudo-randomness, not collision resistance and they xor the hashes instead of concatenating them. $\endgroup$
    – CodesInChaos
    Commented Dec 6, 2013 at 12:46
  • 1
    $\begingroup$ Also, they are hoping it will be safe, but there is no proof that this is safe. $\endgroup$
    – D.W.
    Commented Dec 6, 2013 at 18:52
  • 3
    $\begingroup$ This thesis by Anja Lehmann: On the Security of Hash function combiners contains good amount of investigation on this and various other similar constructs. $\endgroup$
    – user4982
    Commented Dec 6, 2013 at 19:25
  • 1
    $\begingroup$ @CodesInChaos In SSL they were concatenated if I'm not mistaken, for the same reason. $\endgroup$
    – Maarten Bodewes ♦
    Commented Jan 21, 2014 at 0:39
  • $\begingroup$ @MaartenBodewes the results are x-ored according to this answer by Pornin. $\endgroup$
    – kelalaka
    Commented Apr 15, 2020 at 19:51
0
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.