SSL certificates and MD5 collisions [LWN.net]

SSL certificates and MD5 collisions

Posted Jan 18, 2009 13:21 UTC (Sun) by djao (subscriber, #4263)
In reply to: SSL certificates and MD5 collisions by jd
Parent article: SSL certificates and MD5 collisions

Just a thought, but would it not make sense to start working on a newer version of the SSL protocol that contains two or more hashes, where those hashes are required to use different algorithms?

The two hash suggestion arises so frequently that Wikipedia contains an extended discussion of it. Basically, it doesn't work, because it provides less security than one long hash. The only advantage of two hashes is redundancy, but even this advantage only matters in the event of a complete break, which is not the case for the vast majority of hash function attacks. (For example, if you read the article, the MD5 attack being discussed here is a 2^51 attack on a 2^64 problem, representing a factor of 2^13 speedup. This is the kind of partial attack that would be easily foiled by a single long hash.)

In short, two hash functions don't improve security with respect to the weakest link in the system, namely resistance to partial attacks, so the proposal is not generally useful.

(Log in to post comments)

SSL certificates and MD5 collisions

Posted Jan 18, 2009 21:26 UTC (Sun) by jd (guest, #26381) [Link]

It's important to note that the Wikipedia page specifically says that using two hash functions in case one is broken is a valid use. It's also important to note that the assumption of a corresponding collision in B if a collision is found in A is most useful if A and B are not orthogonal but have a common basis. For example, using SHA-1 and MD5 is not smart as they have common elements. If A and B are completely orthogonal, then knowing a collision in one should tell you nothing about whether a corresponding collision exists in the other.

The effective strength of two hashes can never be greater than a hash with an equal number of bits to the two combined, assuming all three hashes are orthogonal and have no known weaknesses. One of the problems with simply adding bits to a hash is that doesn't guarantee it will be any stronger. If the bits are poorly generated, it might even weaken it. This could happen if the extended hash is insufficiently close to random and information is exposed.

If, however, you're already working with hashes that are as long as you can usefully generate them, the combined strength of the hashes (again, assuming there are no common elements) must always exceed a hash of twice the length because the algorithms are no longer safe in the extended form, creating an unnecessary weakness in addition to any weakness that might be inherent in the algorithm anyway.

SSL certificates and MD5 collisions

Posted Jan 18, 2009 23:30 UTC (Sun) by djao (subscriber, #4263) [Link]

It's important to note that the Wikipedia page specifically says that using two hash functions in case one is broken is a valid use.

This is true, and I addressed this exact issue in my previous reply, although perhaps the manner in which I addressed it was too oblique.

I will start with your usage of the word "broken". What does it mean for a hash function to be "broken"? The image that frequently comes to mind is that of a total break, the sort of break where one can generate almost arbitrary collisions with trivial effort. If you are worried about your hash functions suffering a total break, then, yes, two hashes have some advantages over one hash.

The problem is that the stereotypical portrayal of a total break is not something that happens very often in real life, at least not with the more popular hash functions. More often, what happens is that a hash function is broken in some sort of incremental manner, in which the hash can be broken marginally more easily than brute force, but the attack is not effective enough to be considered totally trivial. In such a situation, a single long hash provides much much more of a safety margin than two short hashes. It is important to realize that a long hash, like SHA-256 (which is of course 256 bits), has to be much more thoroughly broken than a short hash before attacks on the long hash become practical. To give a concrete example: SHA-1, which is 160 bits, is nowadays considered marginally broken. The best known attack on SHA-1 requires 2^63 computations. This represents a factor of 2^17 speedup compared to brute force, which sounds bad, until you observe that the theoretical optimum for a 128-bit hash function (such as MD5) is 2^64 computations. In other words, even the so-called "broken" SHA-1 still has the same security as what we thought MD5 used to have before MD5 was broken. This is the kind of thing that a longer hash function does for you: it provides a safety margin, just by virtue of being longer.

It is instructive to compare SHA-1 with MD5 and SHA-256. A hypothetical 2^17 speedup in attacking MD5 leads to MD5 being broken (which is in fact more or less what happened to MD5), and a hypothetical 2^17 speedup in attacking SHA-256 would be a purely theoretical result.

The reason I'm replying at length is because people often don't realize that the safety margin provided by simply using a longer hash function is extremely large and very likely to be more valuable than the relatively minor safety margin provided by using two short hashes, due to the observed fact that many many more hash functions suffer partial breaks than total breaks.