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.'"

Well everyone's boned then

[tietokone-olmi]

[...] This may mean that the attacker needs insider access to the party operating the trusted software integrity protection or code signing process.

An attack that requires insider access? Well colour me frightened!

Or don't. That's more accurate anyhow.

Re:Well everyone's boned then

[Anonymous Coward]

Perhaps you should read this article [linuxworld.com] with particular reference to the table 'Stages in the life cycle of cryptographic hash functions'. By the way you are one or two stages behind.

Re:Nothing new

[Bert64]

If he has access to the good exe *before* it's signed, why not simply replace it with the malicious one so that the malicious one gets signed and distributed instead of the good one...

Ah yes, this again

[Effugas]

OK, it's pretty damn cool to see people 'round here referencing my work on Javascript MD5 collisions :)

The relevant links are:

http://www.doxpara.com/research/md5/t1.html [doxpara.com]
http://www.doxpara.com/research/md5/t2.html [doxpara.com] ...and the original paper:

http://www.doxpara.com/research/md5/md5_someday.pdf [doxpara.com]

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.

ONE block, surely

[CarpetShark]

Surely the point is that, if you can generate two blocks that do this, then you can generate one block to pair with a previously known block -- such as something in open source code.

what it really means ..

[rs232]

"if you can change the original program, then what's the point ?)"

Well, what it means is that an evil software megacorporation could publish a digitally signed app that could be replaced with another presumably nefarious prog later on ..

Re:Not a real life scenario...

Re:Nothing new

[kasperd]

After having read the actual article I realize that there in fact is something new in it. The slashdot story put all the focus on software signing, which is not the interesting part of the article. The interesting part of the article is, that they have found a new and stronger way to produce collisions. For one thing it is going to be a lot less obvious that a file is crafted. The original attack required all the colliding files to contain all the meaningful content with some psuedorandom content to select between them. The new attack doesn't require this, in fact you could even produce collisions beteween files of different formats. Like a jpg file and an exe file with the same md5 hash. But still it is just a collision attack, it produces collisions between two crafted files. They don't produce collisions between a collision between an arbitrary original file and one crafted file.

Re:use two hash functions

[mollymoo]

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 problem as I see is that the harmless version can be released and gain trust. That version can be tested and inspected, even checking the binary wouldn't reveal malicious code because there wouldn't be any malicious code to find - no dodgy looking system calls, for example. Just a chunk of seemingly random data, which could be disguised as a lookup table, compressed image or whatever. At some later point, after the harmless version has gained trust, its use has become more widespread and the rate of downloads has increased correspondingly, it can be replaced by the malicious version. So while you could initially release a malicious version, being able to first release a harmless version can widen the impact of an attack.

Re:Nothing new

[Kjella]

Sneaking it past security control perhaps? Here's good.exe, run it in a sandbox all you like and it won't do anything funny. Then mark this MD5-sum as good and add it to the list of trusted installers, while I'll replace it with evil.exe before distribution/installation in the production environment.

For a pracical example:
1. Become a kernel contributor on some obscure driver.
2. Add a magic number somewhere, which is the good twin.
3. Wait for this to flow upstream to Linus, then downstream to all the distros.
4. Find a way to hack a mirror of your distro of choice
5. Replace the signed kernel with your trojaned kernel, that'll still be signed
6. Wait for people to install trojaned systems (enterprise systems!)
7. Profit (there is no ???)

Of course, this assumes you can use it knowing just the little magic bits. If you need to be the one compiling both good and evil using the exact same source, then it's very limited.