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

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.