Does any published research indicate that preimage attacks on MD5 are imminent?

Question

I keep on reading on SO that MD5 is broken, bust, obsolete and never to be used. That angers me.

The fact is that collision attacks on MD5 are now fairly easy. Some people have collision attacks down to an art and can even us use them to predict elections.

I find most of the examples MD5 "brokeness" less interesting. Even the famous CA certificate hack was a collision attack meaning that its provable that the party generated the GOOD and EVIL certificates at same time. This means that if the EVIL CA found its way into the wild, it is provable that it leaked from the person who had the good CA and thus was trusted anyway.

What would be a lot more concerning is a preimage or second preimage attack.

How likely is a preimage attack on MD5? Is there any current research to indicate that it is imminent? Is the fact that MD5 is vulnerable to collision attacks make it more likely to suffer a preimage attack?

Answer 1

We don't know.

This kind of advance tends to come 'all of a sudden' - someone makes a theoretical breakthrough, and finds a method that's 2^10 (or whatever) times better than the previous best.

It does seem that preimage attacks might still be a bit far off; a recent paper claims a complexity of 2^96 for a preimage on a reduced, 44-round version of MD5. However, this isn't a question of likelihood but rather whether someone is clever enough to go that final step and bring the complexity for the real deal into a realistic margin.

That said, since collision attacks are very real already (one minute on a typical laptop), and preimage attacks might (or might not) be just around the corner, it's generall considered prudent to switch to something stronger now, before it's too late.

If collisions aren't a problem for you, you might have time to wait for the NIST SHA-3 competition to come up with something new. But if you have the processing power and bits to spare, using SHA-256 or similar is probably a prudent precaution.

Answer 2

In cryptography recommendations are not generally made by predicting the future, as this is impossible to do. Rather cryptographers try to evaluate what is already known and published. To adjust for potential future attacks, cryptosystems are generally designed so that there is some safety margin. E.g. cryptographic keys are generally chosen a little bit longer than absolutely necessary. For the same reason algorithms are avoided once weaknesses are found, even if these weaknesses are just certificational.

In particular, the RSA Labs recommended to abandon MD5 for signatures already in 1996 after Dobbertin found collisions in the compression function. Collisions in the compression function do not imply that collisions in the hash function exist, but we can't find collisions for MD5 unless we can find collisions for its compression function. Thus the RSA Labs decided that they no longer have confidence in MD5s collision resistance.

Today, we are in a similar situation. If we are confident that a hash function is collision resistant then we can also be confident that the hash function is preimage resistant. But MD5 has significant weaknesses. Hence many cryptographers (including people like Arjen Lenstra) think that MD5 no longer has the necessary safety margin to be used even in applications that only rely on preimage resistance and hence recommend to no longer use it. Cryptographers can't predict the future (so don't look for papers doing just that), but they can recommend reasonable precautions against potential attacks. Recommending not to use MD5 anymore is one such reasonable precaution.