24

Is it more secure in practice to use the output of multiple hash algorithms instead of a single one (assuming that the output size is the same)?

By secure, in this context, I mean protecting against both collisions and function reversibility.

One particular example would be using 128 bits from SHA-512 plus 128 bits from MD5 instead of using 256 bits from SHA-512.

My intuition is that, theoretically, this would weaken the function, because there are known attacks against MD5 which, effectively, would reduce the output size of the combined function. However, in practice, is it more difficult to find a collision/inversion for both algorithms at the same time - because it'll involve additional theoretical work as opposed to using existing (or upcoming) published ones?

EDIT:

To clarify, I'm simply asking about the basic properties of irreversibility and collision resistance - not about any particular use of hash functions, such as key derivation from passwords (there's excellent coverage about that in other questions) or using the output as unique identifiers.

Another way to phrase this would be "is a hash function defined as the concatenation of two other hash functions better than those?". Also, I'm (somewhat) aware that, information theoretically, it can't possibly be.

  • "Is using multiple hash algorithms more secure?" you ask. Use them for what purpose?, I ask. – a CVn Mar 16 '15 at 14:03
  • @MichaelKjörling for the purposes of hash function reversibility and collision resistance only. See my edit. – goncalopp Mar 16 '15 at 14:22
  • 2
    It may be noted that the term "concatenate", as applied to hash functions, has two meanings: the concatenation of H1(x) and H2(x) may be defined as either H1(x)+H2(x), or H2(H1(x)). The former is a bad idea, since it weakens what is typically the weakest aspect of a password hash to match the strength of the weaker constituent. The latter, however, may be good. – supercat Mar 16 '15 at 16:52
  • Rather than combining the two hashes in a manner that weakens either of them, how about using the MD5 hash as salt for the SHA-512 hash? That way the combination is at least as strong as the stronger of the two. – user70542 Mar 17 '15 at 16:07
  • 6
    @supercat H2(H1(x)) is called composition, not concatenation. I've never heard it referred to as concatenation either. – Thomas Mar 17 '15 at 16:12
18

From the standpoint of collision-resistance (finding two colliding messages) and second-preimage-resistance (finding a different message colliding with a given one), the concatenation of multiple hashes is at least as secure as the strongest of the hashes (Proof: for any of the two properties, any attack that breaks the concatenation can be turned into an attack that breaks each hash. For example, hypothetical colliding messages for the 640-bit MD5||SHA-512 also collide for SHA-512, thus if SHA-512 is collision-resistant, then MD5||SHA-512 is collision-resistant).

From the standpoint of finding a message hashing to a given value ([first-]preimage resistance), or finding an unknown (possibly short or low-entropy) message known to hash to a given value (the situation in password hashing), it is prudent to consider that the concatenation of multiple hashes is insecure (possibly much worse than any of the hashes). We can construct hashes so that each is individually resistant to finding an unknown message (chosen randomly in some set too large to explore) from its hash, but the concatenation is totally weak against that.

For many iterated hashes including all Merkle-Damgård hashes (thus MD5, SHA-1, the various SHA-2), using the concept of multicollisions, it can be shown that the concatenation of multiple hashes is not much more secure against collisions than the strongest of the hashes. See Antoine Joux: Multicollisions in Iterated Hash Functions. Application to Cascaded Constructions, in proceeding of Crypto 2004.

The above article strongly suggests that among using 128 bits from SHA-512 plus 128 bits from MD5 (or) using 256 bits from SHA-512, the later is much safer. The only assurance we have about the former is that it is not worse than SHA-512 truncated to 128 bits, which can be attacked in about 264 hashes, when we expect the later to require about 2128 hashes to attack.

  • 2
    "the concatenation of multiple hashes is at least as secure as the strongest of the hashes" --> Did you meant "is at the most"? Or you meant that "the concatenation of multiple hashes is at least as secure as the weakest of the hashes"? – Ismael Miguel Mar 17 '15 at 16:56
  • @Ismael Miguel: I did mean at least as secure in the first paragraph. As in: the concatenation of MD5 and (full) SHA-512 is at least as secure as (full) SHA-512, WRT collision-resistance (also second-preimage-resistance). Proof: hypothetical colliding messages for the 640-bit MD5||SHA-512 also collide for SHA-512, thus if SHA-512 is secure, then MD5||SHA-512 is secure. – fgrieu Mar 17 '15 at 17:18
  • A "Yes, I meant that" would be enough. But you are right about that. That should be added to the answer itself. – Ismael Miguel Mar 17 '15 at 20:15
  • @Ismael Miguel: good suggestion, done. – fgrieu Mar 17 '15 at 20:28
  • 1
    This may be technically correct, but for cracking passwords it's highly misleading. Concatenating hashes without any obfuscation is essentially giving an attacker more information and more options. – Patrick M Mar 18 '15 at 7:58
26

You don't mention what you're using the hashes for, but it appears likely that your intent is to use if for password verification.

So, the first issue to clear up is the concern that a given algorithm might be found to be susceptible to collisions. Collisions are not a threat to password hashes, and even if an algorithm were susceptible to collisions, that doesn't weaken it for the purpose of password hashing. For password hashing, we're worried about pre-image attacks instead...Being able to find the input that was used to create a given hash.

Today, the primary mechanism to attack password hashes is a dictionary-based brute-force attack. You hashes as many possible inputs you can, as quickly as you can, to determine which input results in the hash you're trying to match. Thus, the most desirable feature of password hashing function is slowness. You want to ensure that it takes as long as possible for an attacker to test the inputs required to find the correct one.

So, now that we understand what we're looking for, let's take a look at your proposal.

If you hash the password twice, with SHA-512 and MD-5, and truncate to 128 bits of each, and concatenate them together, for all intents and purposes, you're giving the attacker two hashes to work with. In many cases, the security of a hash isn't terribly reduced by truncation, as long as the resulting length is reasonable, which 128 bits likely is.

This means that you're taking two fast hash functions (SHA-512 and MD-5 are both far too fast to be effective password hash algorithms) and offering the attacker the opportunity to choose which one they would like to use to crack your hash. In this case, they're certainly choose MD-5, and feed inputs into it, truncate the hash to 128 bits, and match it to the MD-5 portion of your hash, and as soon as they have the match, there's near 100% certainty that they also have the value they need to compute the SHA-512 portion of the hash on a single try.

So, not only does this specific construction not improve security, but it actually rather significantly cripples it instead. While there are other potential constructions that could prove to increase security, it's not a simple matter to get it right, so if you really want a reasonable assurance of security, use a proven construction like bcrypt with a reasonable work factor.

  • 1
    @BenVoigt Free free to read the literature on hash truncation. There's quite a bit of it out there, and it's generally accepted that reasonable truncation is safe in most cases. Here's a crypto.SE answer to get you started. – Xander Mar 16 '15 at 15:11
  • 1
    @BenVoigt Again, read the supporting materials, and perhaps a bit on how attacks against hash functions work. Specifically, you'll find out that attacks that cause collisions give the attacker the greatest amount of leeway. This is why hash functions that are broken in regards to collisions, are not necessarily broken for pre-image resistance. So, if truncation can safely protection against collisions, it cannot be less safe against pre-image attacks. – Xander Mar 16 '15 at 15:25
  • 1
    @Xander: Sure, but finding a collision on one hash in no way implies a collision on the other. – Ben Voigt Mar 16 '15 at 16:22
  • 1
    This answer is oriented toward password hashes, and does not apply well to the question as it stands after edit. – fgrieu Mar 17 '15 at 14:56
  • 2
    @fgrieu While this might not answer the question directly, I think it is a useful addition to your answer, since readers might want to use such a construction for password hashes, and now know not to do so. – Paŭlo Ebermann Mar 17 '15 at 21:00
12

Referring to the first few paragraphs in this article: https://crackstation.net/hashing-security.htm

If you are thinking of writing your own password hashing code, please don't!

I understand that you don't consider writing your own hashing code, but rather use multiple of standardised ones to seamingly increase security. This will, however, give you no or little advantage.

Ratchet Freak (https://softwareengineering.stackexchange.com/questions/115406/is-it-more-secure-to-hash-a-password-multiple-times) points out that your hash function would only be as secure as your weakest function in the chain. Weaker algorithms are also known to collide more often, and thus potentially increasing the risk of collitions - making your overall security less.

Furthermore, this will as mentioned decrease entropy instead of increasing it.

There is also no reason why you would rather go ahead and implement two different methods and combine them - in practice there will be none or very little gain. 256 bit SHA-512 will be stronger than two merged 128 bit hashes - since the entropy is increased and overall stronger. MD5 will contain a lower entropy and therefore decreasing the security.

EDIT

To clarify the answer:

SHA-512 is stronger than MD5 (for the bit count that was mentioned, 256 and 128) for the mentioned case. MD5 is more likely to result in collisions. (https://stackoverflow.com/questions/2117732/reasons-why-sha512-is-superior-to-md5)

128 bit MD5 and 128 bit SHA512 vill only be as collision-resistant as the weaker of the two - the 128 bit MD5. (https://stackoverflow.com/questions/7407835/512-bit-hash-vs-4-128bit-hash)

EDIT

As pointed out by fgrieu down in the comments, this turns out to be not true.

As an illustration, we can find new MD5 collisions at high rate, but there is no known collision for SHA512 truncated to 128 bits, thus no known collision for the 256-bit concatenation of MD5 and SHA512 truncated to 128 bits. -fgrieu

The only way I could see this being beneficial is protection against Rainbow Tables, which probably wouldn't be prepared for your hash concentration. Instead of concentrating the hashes, salts should be used. But since you were not interested in the password security side of things ("I don't have any particular intent, and I was hoping to treat it as simply another hash function")

Points brought up in the comments.

  • To reduce collisions, concatenation is better (because you need collisions on both hashes simultaneously). To reduce preimage attacks, chaining is better (because you need to reverse both hashes in sequence). - Ben Voigt
  • The answer you linked to concerns function chaining, not concatenation, and only addresses collision resistance. "256 bit SHA-512 will be stronger than two merged 128 bit hashes" was the answer I was hoping for, but do you have a reference you're drawing from? – goncalopp Mar 16 '15 at 14:27
  • @BenVoigt: Even if one had a preimage attack that could, for any has value, quickly yield a 40-byte string whose hash would match it, I see no way one could use that to crack the described scheme. I see it as being excessively-susceptible to brute-force attacks (and would recommend against it for that reason), but I don't see how the ability to generate preimages for one of the hashes would buy an attacker anything. – supercat Mar 16 '15 at 17:04
  • @supercat: That's exactly the point I've been trying to make in comments to Xander's answer. – Ben Voigt Mar 16 '15 at 17:06
  • The answer has been updated to improve the main point and sources has been added. I also included @BenVoigt's first comment since it was something I did not think about the first time. – Alex Mar 16 '15 at 18:26
  • @supercat: a break of MD5 might still buy you a little bit, though. If you have an MD5 pre-image attack that generates lots of pre-images, then the questioner's scheme might compare poorly to SHA-512 alone, since he's replaced the problem of finding a pre-image to a 256-bit SHA-512 with the problem of finding a pre-image to a 128-bit partial SHA-512 from among the outputs of your MD5-cracker. This may or may not be easier, I don't think it's certain either way. If no attacks are known on SHA-512 then it reduces the brute force search, but 128 bits is still large :-) – Steve Jessop Mar 17 '15 at 11:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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