Crypto collision used to hijack Windows Update goes mainstream

The cryptographic hash collision attack used by cyberspies to subvert Microsoft's Windows Update has gone mainstream, revealing that MD5 is hopelessly broken.

Security researcher Nat McHugh created two images of different rock 'n' roll icons - James Brown and Barry White - with the same MD5 hash. "The images were just two I lifted from the web ... in fact I could have chosen any image or indeed any arbitrary data and created a collision with it," McHugh reports.

The process of computing padding data to produce the collision between two dissimilar images files was carried out on a mainstream cloud computing instance in a matter of hours at a cost estimated by McHugh as being less than a dollar.

Brute force attempts to find cryptographic hash collisions – where two dissimilar files give the same hash value – are still impractical for anyone without access to a supercomputer.

What McHugh was able to do was to add binary data to the end of two different JPEG images such that the two modified files gave the same hash value. Chosen prefix collisions for MD5 of this type were first successfully demonstrated in 2007.

In a chosen prefix collision, the data preceding the specially crafted collision blocks can be completely different, as is the case of the images of the Godfather of Soul and the Walrus of Love.

In a blog post, McHugh explains how he was able to work out what binary data to add to the end of the two image files.

The chosen prefix collision attack works by repeatedly adding 'near collision' blocks which gradually work to eliminate the differences in the internal MD5 state until they are the same. Before this can be done the files must be of equal length and the bit differences must be of a particular form. This requires a brute force 'birthday' attack which tries random values until two are found that work. [I]t does however have a much lower complexity than a complete brute force attack.

Another researcher, Marc Stevens, has created framework for automated finding of differential paths and using them to create chosen pre-fix collisions. https://code.google.com/p/hashclash/ . McHugh chose to run Stevens's HashClash research tool on Linux, using a bash script to automate the repetitive steps needed, on an AWS GPU instance. "I found that I was able to run the algorithm in about 10 hours on an AWS large GPU instance" at a cost of around $0.65 plus tax per crack, according to McHugh.

McHugh concludes that his exercise proves MD5 is hopelessly weak, outdated and no longer fit for purpose.

MD5 is well and truly broken. Whilst the two images have not shown a break in the pre-image resistance or second pre-image resistance, I cannot think of a single case where the use of a broken cryptographic hash function is an appropriate choice.

It was a chosen prefix collision attack similar to this that was used to produce a counterfeit SSL certificate used to sign the Flame malware as Microsoft and pass itself off as a Windows update.

Other security experts were inclined to agree with McHugh's conclusion that MD5 is a dead duck.

"If you can't even distinguish between Barry White and James Brown, it's time to send MD5 to hashing algorithm heaven," said Martijn Grooten, editor of Virus Bulletin and sometime security researcher, in a Twitter update.

A cryptographic hash algorithm such as MD5 converts data into a shortened "message digest" from which it ought to be impossible to recover the original information. This one-way technique is used to generate digital signatures for software downloads, among other functions.

Bootnote

Flame used a chosen-prefix collision attack against MD5 in order to generate a rogue CA certificate. The sophisticated malware, discovered in 2012 but probably circulating since 2010, was used in a cyber-espionage attack against Middle Eastern countries. Most of the infected systems were located in Iran.

The Washington Post claimed in June 2012 that Flame had been jointly developed by the NSA and Israel’s military as part of the same Olympic Games operation that spawned Stuxnet. Put very simply, Flame carried out surveillance and mapped networks while Stuxnet sabotaged the control systems of nuclear processing centrifuges.