Slashdot Mirror
MD5 Proven Ineffective for App Signatures
prostoalex writes "Marc Stevens, Arjen K. Lenstra, and Benne de Weger have released their paper 'Vulnerability of software integrity and code signing applications to chosen-prefix collisions for MD5'. It describes a reproducible attack on MD5 algorithms to fake software signatures. Researchers start off with two simplistic Windows applications — HelloWorld.exe and GoodbyeWorld.exe, and apply a known prefix attack that makes md5() signatures for both of the applications identical. Researchers point out: 'For abusing a chosen-prefix collision on a software integrity protection or a code signing scheme, the attacker should be able to manipulate the files before they are being hashed and/or signed. This may mean that the attacker needs insider access to the party operating the trusted software integrity protection or code signing process.'"
Unless I am missing something this is really nothing new. The same has been demonstrated with a webpage and javascript years ago, i.e. two different webpages producing the same MD5, doing it again with an .exe doesn't really sound all that interesting, especially since the attacker still needs to manipulate both the good .exe and the evil .exe and when he has access to the good .exe you are toast anyway.
This of course doesn't mean we should continue to use MD5, but the attack is really of rather theoretical nature.
An attack that requires insider access? Well colour me frightened!
Or don't. That's more accurate anyhow.
The problem has nothing to do with salt, and can be certainly temporarily "fixed" switching to SHA-1 or, even better, SHA-2. But the real root of the problem here is that, for the attack to work, someone signed as trusted a binary file that contained malicious code in the first place, even if in a disable form.
Let me explain that. First, this is very old news: we know since 2004 that collision can be found in MD5 hashes (two different files with the same md5sum), and there now are tools that can generate collisions in seconds. All you need is a common prefix and suffix for both files and two block of 128 bytes that are generated automatically and you can insert between the prefix and the suffix to create the two files.
Applying this to pretty much any file type that can contain binary data (even XML 1.1!) is trivial. For an executable file you can simply insert code in your prefix/suffix that looks at the pseudo-random 128 bytes and does radically different things depending on it. This as already been demonstrated for HTML+JS and even for postscript files.
Bottom line: if you have an executable file from an untrusted source it may contain bad things (the attack described requires that both the original signed file and the file that you are actually executing are generated by the same hostile source).
There's a hidden treasure in Python 3.x: __prepare__()
MD5 collision attacks aren't really new, although this is a powerful example. An equally meaningful example of a collision attack on the algorithm, in the form of two different PostScript files with the same MD5 hash, was provided at least two years ago (IIRC).
The key to understanding the limits of this demonstration's significance is to realize that a collision attack is quite different from a prefix attack. These researchers were able to create a pair of executables having the same hash value by specially constructing them as such; crafting a new executable to match a specific hash value corresponding to some other party's executable is vastly more difficult to achieve.
So while this demonstrates MD5 to be useless for uses where the purported signatory is to be included in our threat analysis -- as has already been demonstrated to us by other researchers -- the algorithm is still relatively safe if our only goal is to ensure that a given executable almost certainly came from a specific party (rather than showing that it is a specific executable from said party). In other words, one could conceivably use MD5 to verify that the Ubuntu packages on that FTP server were in fact produced by Canonical. So no, demonstration does not mark MD5 as completely useless for code signing; the most common applications of code signing are entirely unconcerned with collisions in the hash function.
In conclusion: the title is terribly misleading, or possibly just misinformed. Boo! Hiss!
This is an example of a Birthday Attack. 1. Attacker generates Good.exe and Evil.exe which hashes to the same MD5 2. Attacker passes Good.exe to the key owner to sign 3. Key owner signs and release Good.exe and Good.exe.MD5 4. Attacker releases Evil.exe as Good.exe This of course, requires some serious social engineering to work. MD5 is outdated, yes, but at the moment it is still resilient against a normal attack where an attacker has to generate an Evil.exe to hash to the same MD5 as an already-available Good.exe
The particular scenario they describe is irrelevant; MD5 checksums aren't intended to protect against that. If the attacker can manipulate the original file, he can usually simply alter it to become malicious itself.
The case that matters is producing a program with the same checksum as a given program, without the ability to manipulate the correct program beforehand. That's still hard.
Nevertheless, code signing mechanisms in general should probably be prepared for flaws in hash functions. It might be best always to use two hash functions and to have some strategy of migrating. That way, if one hash function gets compromised, there is still another one in place and can be used until the original one has been replaced.
OK, it's pretty damn cool to see people 'round here referencing my work on Javascript MD5 collisions :)
...and the original paper:
The relevant links are:
http://www.doxpara.com/research/md5/t1.html
http://www.doxpara.com/research/md5/t2.html
http://www.doxpara.com/research/md5/md5_someday.pdf
I'm pretty sure I talked about third party attestation in that paper.
A more interesting point was made to me just the other day, which is that there's always enough ambient entropy in any real world system to deviate between trusted and untrusted behavior. In other words, for a turing complete app, you *can't* create a meaningful hash, because you aren't capturing all bits that will drive the execution flow. So, getting code signed really doesn't assert anything other than a business relationship. App signatures don't actually work, for any arbitrarily good hash.
If you'd read the article, you'd see that one of the (prominent) possible attack scenarios listed is that of software distribution: distribute a good file, with the intent of replacing it later. For example, in debian, even with MD5 checksums on all your data, and tools reporting what's changed during the software update, this would still allow downloading infected files, without noticing.
It's a danger both from malicious distributors, and from hacked distribution sites.
As many projects have done for years. md5 sums as crypto-protection are more or less a historic way to do it.
Most ACs are not even worth the keystrokes to insult them. Be generically insulted by this and ignored otherwise.
Real life scenario :
developper A produce software X(for example openssh), calculate hash of program X and sign the hash with his PGP key.
He then put all these files on mirrors servers on Internet (but not his private PGP key !)
One mirror is hijacked by B.
B wan't to replace X by X' with the same hash than X
This article doesn't provide anything as it says MD5(X+a)=MD5(Y+a), which imply you have to change A in the first place which can't be done easily (and if you can change the original program, then what's the point ?)
TFA points out specifically that no one knows how to target a specific hash code. All they can do is make two files converge on the same hash code by inserting data into *each* of them.
As always, all IMO. Insert "I think" everywhere grammatically possible.