MD5 Weakness Exploited

The first breakthrough (or proof of breakage) came in late 2004, when Xiaoyun Wang, Dengguo Feng, Xuejia Lai, and Hongbo Yu demonstrated a practical way to obtain collisions in the MD5 hash, as well as in a number of other hash functions.An in-depth discussion on the attacks and on why being able to reliably find collisions in MD5 is a BAD_THING(tm) can be found here .

The Cliff Notes version is that if you can reliably produce hash collisions, you can make a file pass for another, as hash functions are used precisely to produce (practically) unique identifiers for files.

Researcher Dan Kaminsky outlined a theoretical attack in early 2005, under the title “MD5 to be considered harmful someday”.

The end of 2008 brought a mixed blessing, in the form of a practical way to exploit the cryptographical vulnerability of MD5. A team composed of Alexander Sotirov, Marc Stevens, Jacob Appelbaum, Arjen Lenstra, David Molnar, Dag Arne Osvik and Benne de Weger announced that the day predicted by Kaminsky had come – they had succeeded in the creation of a rogue Certification Authority certificate, which can in turn be used to make websites siged with it appear as if they have been verified by a certification authority, such as Verisign’s RapidSSL.

Such a certificate enables man-in-the-middle attacks on HTTPS or, in other words, un-detectable tampering and monitoring of HTTPS connections to sites using vulnerable certificates (those created with the help of) MD5.

HTTPS is, of course, the standard used in e-commerce and e-banking.

It can be argued (and in fact Sotirov and co. do argue) that all MD5-based certificates should be revoked or rather, should have been revoked in 2007, when the attack first became possible due to yet another mathematical breakthrough, which made the creation of MD5 collisions not only possible, but also relatively fast.

Sotirov’s team managed to produce a collision a day using “just” 200 PlayStation3s and one huge server and those are the kind of computing resources which might come easily within the reach of a bot herder. The technical know-how would not, however – the team estimated that their efforts could be duplicated in a month by skilled researchers, or much more by people new to the field.

However, it is highly probable that old, vulnerable certificates will not, in fact, be revoked. However, if everyone stops generating new vulnerable ones, the issue will, for most practical purposes, end. That this is not the case already tells much about how practicality can trump security even in the context of companies which are supposed to provide security as a core business – certification authorities.

We leave you to an excerpt from the exploit site which is kind of a
must-read:

“Question: What is the best way to ensure that the attack scenario we developed is not possible in the future? Answer: Stop using MD5 as soon as possible, and migrate to more secure cryptographic hash functions”