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.'"
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.
Sorry but you are wrong. The attack uses two md5 inputs which collide to construct two programs which are otherwise identical. The program can then be contrived to exhibit different behaviour depending on which of the two colliding inputs was used. This is nothing to do with the birthday paradox (except that it may have been used to find the collisions in the first place). Otherwise you description of the attack is accurate.
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.
No, this is different. In the case of the colliding webpages, bit level inspection immediately reveals what's going on: both "good" and "bad" version are included in the webpages, with an if-statement to choose which one to display.
When you inspect these binaries at bit level, they contain only the "good" or the "bad" version, and some random data appended to it to make the MD5 hash of the files collide. This technique thus also works for file formats which don't have control statements such as "if" or "file starts at offset". See also: http://www.win.tue.nl/hashclash/Nostradamus/, scroll down to: "Didn't Daum and Lucks do something like this in 2005?"
Marc Stevens already constructed these "chosen-prefix" collisions for X.509 Certificates, see the HashClash project page. What's new in these results, is that it did not require massively distributed computing efforts, only one Playstation 3 and less than two days of computation. There is no paper available yet as to how he achieved this major optimization, but his MSc thesis gives a clue: see "future work" at the end of section 7.4.
This is a different kind of attack: the "old" collision prefix attack had two blocks X and Y with the same hash that allowed one to create two programs:
X; if (X) then GOOD else EVIL
and
Y; if (X) then GOOD else EVIL
but the evil code would be in the signed good program, it would not be run.
The new attack is different: it is a method to generate blocks GX and EX for two random files such that the files GOOD+GX and EVIL+EX hash to the same checksum.
extern warranty;
main()
{
(void)warranty;
}
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.