Beta
×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

MD5 Proven Ineffective for App Signatures

Zonk posted more than 6 years ago | from the needs-a-bit-of-retooling dept.

Security 117

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

Sorry! There are no comments related to the filter you selected.

Hmm... (1)

Char-i-o's (1195873) | more than 6 years ago | (#21550937)

Need more salt.

Perhaps they should consider using something else than SHA-1? SHA-2 anyone?

Well, duh! (4, Insightful)

YA_Python_dev (885173) | more than 6 years ago | (#21550993)

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 [wikipedia.org] 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).

Re:Well, duh! (1)

bhima (46039) | more than 6 years ago | (#21551079)

I thought SHA-1 which similarly compromised and folks were advised to use the SHA-2 variants SHA-256 & SHA-512... with SHA-384 being mostly silly except for very specific applications where key length was limited but computation was not.

Re:Well, duh! (1, Insightful)

cheater512 (783349) | more than 6 years ago | (#21551335)

Well every hash function will eventually have flaws like this.
Its inevitable.

Re:Well, duh! (1)

mlts (1038732) | more than 6 years ago | (#21553949)

Hash functions are a relatively young cryptographic technology, only have been around for about fifteen years in the mainstream. Unfortunately, due to this, there are still a lot of bugs to be ironed out. MD5 is (IIRC) only the second generation of hashes. Bulk cryptography has had far longer to evolve, from enigma-type rotor algorithms, to DES, and finally to AES, where each algorithm has been scrutinized for years for any possible issues.

I commend NIST for having a SHA-3 crypto contest. I'm pretty sure something solid will come of it, and if someone *does* know how to generate collisions with the chosen algorithm, they will keep it to themselves very quietly, and not expose it.

One security precaution I do think people should do is go by not just the MD5/SHA hash, but also sign the size of the file. Its a lot harder to generate an evil.exe when it has to be exactly the same size as the good.exe.

Re:Well, duh! (1)

Garridan (597129) | more than 6 years ago | (#21555279)

Nope. That's really not a problem.

MD5 is what, 64 bytes? Your file will probably be less than a terabyte (2^40 bits), so it'll have a representation of 40 bits, or 5 bytes. So now you have a 71 byte hash. Are you going to tell me that 71 bytes is really "a lot harder" than 64? You're delusional.

The problem is that data is intrinsically incompressible. If you map the space of all finite sized binary words into the space of all binary words of n bits, you have an infinite-to-one map. If you want collisions to be "hard", you increase the size of your target space. If you want 'em to be really hard, you're playing against the future, which is almost always a losing bet.

ONE block, surely (2, Interesting)

CarpetShark (865376) | more than 6 years ago | (#21551123)

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.

Re:ONE block, surely (5, Informative)

jthill (303417) | more than 6 years ago | (#21551273)

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.

Re:ONE block, surely (1)

colmore (56499) | more than 6 years ago | (#21555603)

It's a little obscure in the article (and elsewhere) but you have to generate two executables, both of which are manipulated to hit a common target. Basically some hashcodes are easier to hit than others. You can't hit an arbitrary one.

Anyway, use one of the SHA algorithms

Re:Well, duh! (0)

Anonymous Coward | more than 6 years ago | (#21551265)

This type of attack always seem to depend on adding data to an altered blob so the hash turns equal again (the way I understand it at least). So maybe the problem could be solved by not only storing the hash but also the lenght of the data it was hashed from? I think for example gentoo does this already when checking the SHA1 & MD5 sum of source tarballs.

Re:Well, duh! (0)

Anonymous Coward | more than 6 years ago | (#21552167)

It's not adding data (length) to the blob, it's changing the data bit-by-bit. So the lengths are the same.

Re:Well, duh! (3, Insightful)

hotrodent (1017236) | more than 6 years ago | (#21551413)

Something I've never understood about this problem: Why is the following not an easy "fix"?


1) Generate an MD5 hash for a file.
2) Generate an SHA-2 hash.
3) .. more as needed ...
4) Concatenate the results for a "super hash"
5) Profit?

Surely to manipulate 2 (or more) schemes to ensure the super hash is the same on a tampered file would be _many_ orders of magnitude harder?
Trying to make the SHA-2 match would destroy all the previous work done to make the MD5 match, then fixing the MD5 would change the SHA-2 again.
IANAC (cryptographer) so excuse my ignorance on this if I'm missing something.

Re:Well, duh! (1)

liquidpele (663430) | more than 6 years ago | (#21551465)

Very true, and this is why a lot of programs distribute both Md5 and sha-1, although not concatenated.

Re:Well, duh! (1)

fatphil (181876) | more than 6 years ago | (#21552519)

It has been proven that such concatenation isn't as strong as the sum of the strengths as the two hashes; if you can crack one of the component hashes, then you can generally generate a vast number of collisions to throw at the rest other hash. Sure, it's stronger than the strongest individually, but it's best to just use a single full-width hash.

Re:Well, duh! (1)

mrmeval (662166) | more than 6 years ago | (#21554835)

It's not intuitive but stringing them together doesn't work well. I'd just dump md5 and go with more proven code.

I don't understand why a gnupg digital signature is not used by default.

Mod parent down: first paragraph flat wrong. (0)

Anonymous Coward | more than 6 years ago | (#21551935)

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 disabled form.

Wrong. True of other breaches, not this one.

Re:Well, duh! (1)

fatphil (181876) | more than 6 years ago | (#21552473)

"someone signed as trusted a binary file that contained malicious code in the first place,"

Just plain wrong. Read the article.

Re:Well, duh! (1)

icepick72 (834363) | more than 6 years ago | (#21552777)

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


In other words, it's as easy as accidentally downloading it from the wrong web site. The files will still look right. The malicious web site would have obtained the executable from the originating download site and modified it according. Exceedingly simple and nefarious to attack the unsuspecting.

Re:Well, duh! (1)

grumbel (592662) | more than 6 years ago | (#21553421)

### The malicious web site would have obtained the executable from the originating download site

No, it would have to *modify* the original file on the original server to make this work.

Re:Well, duh! (1)

icepick72 (834363) | more than 6 years ago | (#21554055)

Don't need the original server in this exploit proof [codeproject.com] . If anything you just need source code and your own web page, both easy to obtain (open source), and make the user believe you have a correct version ...


It says: Now, we can publish good.bin in the Internet for people to download it, and later, we can replace it with evil.bin. Now, the users will get infected, without noticing and convinced that there is no tampering, because the MD5 signature is the same for both files, in others words we have MD5(good.bin) == MD5(evil.bin).

Re:Well, duh! (1)

hackstraw (262471) | more than 6 years ago | (#21553583)

irst, 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

OK, that sounds fun. But at least for open source code, the md5checksum is on a compressed archive, not a raw executable. Wouldn't this collision still be practically impossible on an archive?

Nothing new (5, Insightful)

grumbel (592662) | more than 6 years ago | (#21550943)

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.

Re:Nothing new (2, Informative)

Anonymous Coward | more than 6 years ago | (#21550951)

Re:Nothing new (1, Redundant)

Instine (963303) | more than 6 years ago | (#21551051)

Bingo. While it may be of some interest to security freaks, the theoretical nature of this and so many other 'stories' means there's little news in them. Can we have fewer "if the attacker has full access to exe/db/OS/acc/.... they can do terrible things by simply [insert psuedo exploit here]"? We know.

Re:Nothing new (5, Interesting)

Bert64 (520050) | more than 6 years ago | (#21551053)

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

Re:Nothing new (1, Informative)

jthill (303417) | more than 6 years ago | (#21551447)

Because you want an honest party to verify the "good" one, sign its MD5 with their trusted key, and actually distribute the good one.

Then you can in chosen circumstances replace it with the bad one (on, say, specific installs), and an ordinary audit will see the trusted signature on the package you thoughtfully provided on DVD.

Or think contracts: any signed-MD5 signature for a document in a format that ordinarily includes random-looking garbage is now untrustworthy, because what that person signed may have nothing in common with what you're being shown.

Re:Nothing new (2, Interesting)

Kjella (173770) | more than 6 years ago | (#21551583)

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.

Re:Nothing new (1)

norton_I (64015) | more than 6 years ago | (#21551861)

What you describe is not as easy as you make it sound. You can fiddle with the "good" source code so that it passes whatever hash test you want, but even assuming it gets included into the kernel with zero changes, what gets signed by redhat are the binary module or the whole kernel package. Even assuming the source to your module is not changed at all, the binary module is not likely to be the same as the version you compiled. At the very least, redhat includes a build number in every kernel package (also included in each kernel module), and unless you know in advance what the final released build number is going to be, your carefully constructed hashes will be invalidated.

People should stop using MD5 for secure hashes, but this vulnerability is already well known, and really requires signing a binary provided by an untrustworthy source to be effective. It is probably much easier to just get people to trust you (perhaps start a 3rd party RPM repo), then give them bogus binaries.

Re:Nothing new (1)

Red Pointy Tail (127601) | more than 6 years ago | (#21555817)

Your reasoning is correct, but it is flawed because having this MD5-exploit does not make it practically any easier to get away with publishing your exploits.

1) Even without this 'MD5-exploit', if the distributor is malicious from onset, then it is easy to just distribute a driver with a hidden exploit and sign it off as valid. Exploits can be written such that it functions like it is supposed to most of the time but provides a backdoor.

2) If you say that injecting this hidden exploit instantly show up in a code audit so the publisher can't get away with it -- then wouldn't a code audit also detect the verbiage that needs to be tacked on to the good.exe to make the MD5 match with the evil one, and also raise a red flag?

Re:Voting machines (1)

Dare nMc (468959) | more than 6 years ago | (#21552477)

why not simply replace it with the malicious one so that the malicious one gets signed and distributed instead of the good one


Think voting machines. So far that has been the most requested approach, a verified hash code from open source, that is verified on each machine...

Re:Nothing new (5, Informative)

Anonymous Coward | more than 6 years ago | (#21551135)

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/ [win.tue.nl] , 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 [win.tue.nl] 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 [win.tue.nl] gives a clue: see "future work" at the end of section 7.4.

Re:Nothing new (4, Informative)

MathFox (686808) | more than 6 years ago | (#21551151)

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.

Re:Nothing new (1)

Ghubi (1102775) | more than 6 years ago | (#21552841)

Actually isn't it GX + GOOD and EX + EVIL?

Re:Nothing new (2, Informative)

The New Andy (873493) | more than 6 years ago | (#21551153)

This is a different attack. The previous attacks meant that you could make two files with the same MD5 by making them completely identical, except for one small block which was any known collision.

This attack means that you get to choose the two files, and the attack generates two blocks to append to the original files which mean they hash to the same value.

So the exploits before have been:

File 1:

x = [A]
if (x == [A]) {
do one thing
}
else {
do something else
}

File 2:

x = [B]
if (x == [A]) {
do one thing;
}
else {
do something else;
}
Where [A] and [B] are blocks which collide (and they are aligned on block boundaries for calculating the hash).

The new attack is exploited like this::

File 1:
do one thing;
ignore the rest of the file;
[C]

File 2:
do something else;
ignore the rest of the file;
[D]
Where [C] and [D] are generated by this algorithm. This means that on a quick glance, the code doesn't look completely silly and there is no trace of what the hidden content says (just a bit of random stuff at the end of a file which might suggest that it is there)

Re:Nothing new (1)

houghi (78078) | more than 6 years ago | (#21551201)

The attacker does not need access to good.exe. He however can send me evil.exe and tell me to look on for the MD5SUM and verify for myself that said program is valid if I so desire.

Yes, you COULD then download it from the trusted site. However people interested in doing this are not interested in the failed attapts. They are interested in the attapated that worked.

Re:Nothing new (2, Informative)

grumbel (592662) | more than 6 years ago | (#21551281)

### The attacker does not need access to good.exe.

He *does* need access to good.exe. You can't generate a file that matches a given MD5, what you however can is generate two files that have the same MD5 and different content, both good.exe and evil.exe contain appended data to make the sums match. Its still a weakness, but a much less critical one then being able to generate a file for a given MD5.

Re:Nothing new (1)

owlstead (636356) | more than 6 years ago | (#21551429)

At my work I have two bash scripts that do the same. Unfortunately some invalid characters mess up the script. Now it does something useful (it actually prints: "something useful" if I remember correctly), or it crashes. This is because you still have to put some arbitrary data at the end of the script. Some command to make the interpreter stop would probably fix that, but since it was only proof of concept for me, I didn't go that far.

As the article mentions, this could be really bad for third party signing (e.g. MS Authenticode). Since I've seen that they sign practically anything that comes from a "trusted email address" that means practically squat. Of course, it is not fun to test if such an attack is somewhere in a text or binary file. The companies would be better off not using MD5 for such purposes.

Leave MD5 in legacy applications that are not vulnerable. Try and avoid SHA-1 as well. Everybody should upgrade to SHA-256 or SHA-512 for new applications or protocols that can be upgraded. The article is a good read-up for people that have not yet understood the problems with MD5, nothing more, nothing less.

Re:Nothing new (1)

OrangeTide (124937) | more than 6 years ago | (#21552467)

#!/bin/sh
echo Hello World
return
42k k22 452n4 ,mnas,dn a,.sn

Re:Nothing new (1)

fatphil (181876) | more than 6 years ago | (#21551993)

Nope, this attack is new. This is taking fixed prefixes, and appending a suffix to create the collision. Previous attacks required being able to put something _before_ your fixed payloads.

Well everyone's boned then (3, Interesting)

tietokone-olmi (26595) | more than 6 years ago | (#21550969)

[...] 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 (2, Interesting)

Anonymous Coward | more than 6 years ago | (#21551037)

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.

This is a REMOTE attack, and reasonably potent (3, Informative)

CarpetShark (865376) | more than 6 years ago | (#21551107)

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


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.

Re:This is a REMOTE attack, and reasonably potent (4, Funny)

quigonn (80360) | more than 6 years ago | (#21551241)

If you'd read the article,

Reading the article? THIS IS SLASHDOT!!!!!!1!

Haw haw (0)

Anonymous Coward | more than 6 years ago | (#21551597)

Still got him his moderation boosts, tho.

Re:This is a REMOTE attack, and reasonably potent (1)

cloudmaster (10662) | more than 6 years ago | (#21552107)

Yes, you have to be an "insider" to distribute the good file.

Re:This is a REMOTE attack, and reasonably potent (1)

OrangeTide (124937) | more than 6 years ago | (#21552509)

If you're an insider and you tell me that you're updating me to a new version with a completely different MD5 I would probably trust you too. The new version could have any bizarro code in it, because I already trust you. MD5's strength or weakness doesn't matter at that point.

True it is interesting that you can make MD5 do these neat tricks. But as in insider your non-malicious garbage appended exec should likely fail to pass the review process. People will ask "why do you have this funny bit of assembly that appends some hex??". If there is no review process then it doesn't matter and you can drop in your malicious code right away. If you're not inserting the garbage at the source level, and by passing the review. again you could MD5 *anything* anyways. So it doesn't matter.

Right (1)

setrops (101212) | more than 6 years ago | (#21550977)

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

Let's see now, the attacker already has access to the machine and is probably the one creating or comparing the MD5. Is the problem really with MD5?

Not accurate, not new (4, Insightful)

Niten (201835) | more than 6 years ago | (#21551015)

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 [cits.rub.de] , 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!

Re:Not accurate, not new (1)

Niten (201835) | more than 6 years ago | (#21551019)

Err, "prefix attack"? It's too early in the morning for me to be posting to Slashdot...

pretext attack, for the record.

Re:Not accurate, not new (1)

ferespo (899921) | more than 6 years ago | (#21554741)

Totally off topic, but it seems that you know something about the subject and I have a question. When a file is encrypted through a strong algorithm and there are private keys between the parts, it is still necessary to add something like MD5 to preserve integrity? I mean, in this particular case, it appears that confidentiality assures data integrity (in the general case, of course) ? Is it possible in this context to alter an encrypted file without violating confidentiality?
Thanks

Birthday Attack (4, Insightful)

tangent3 (449222) | more than 6 years ago | (#21551043)

This is an example of a Birthday Attack [wikipedia.org] . 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

Re:Birthday Attack (4, Informative)

Anonymous Coward | more than 6 years ago | (#21551087)

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.

Re:Birthday Attack (1)

owlstead (636356) | more than 6 years ago | (#21551387)

Mod parent up. The person is only a A/C, but I cannot see how this is related to the birthday paradox.

Re:Birthday Attack (1, Informative)

Anonymous Coward | more than 6 years ago | (#21552511)

This is nothing to do with the birthday paradox (except that it may have been used to find the collisions in the first place).

That's the whole point of the parent, isn't it? Unless I'm missing something, the collision is generated by a birthday attack approach and the parent was exactly right. It's why the attacker needs to write both GOOD.EXE and EVIL.EXE; if he could generate an arbitrary md5 sum, he could replace any GOOD file and this would be much worse.

IMHO it's still pretty annoying (though not new).

use two hash functions (4, Informative)

m2943 (1140797) | more than 6 years ago | (#21551055)

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.

Re:use two hash functions (3, Interesting)

mollymoo (202721) | more than 6 years ago | (#21551549)

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:use two hash functions (1)

m2943 (1140797) | more than 6 years ago | (#21551997)

Why would you need MD5 forgeries for that? A package maintainer can simply gain trust with a sequence of good binary releases and then, at some point, release a correctly signed bad binary corresponding to a small source code change.

Re:use two hash functions (1)

maxwell demon (590494) | more than 6 years ago | (#21552265)

But if you have built up trust that way, I'm sure simply releasing an "improved version" would also get you installed on a lot of machines, even though the md5sums differ (indeed, it would be very suspicious if the md5sum of the improved version still is the same as of the original one).

Re:use two hash functions (1)

noidentity (188756) | more than 6 years ago | (#21554539)

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.

Isn't using two hash functions the equivalent of using one hash function that is the mathematical equivalent of the two?

Re:use two hash functions (1)

AnyoneEB (574727) | more than 6 years ago | (#21555861)

Well, yes, but it at least gets you more bits. In addition, I think MD5 and SHA1 use sufficiently different mathematics that it would be difficult to come up with an attack technique which was effective on both of them. Instead you would likely have to try to find collisions in the two separately and keep going until they both collide for the same data, which does not help much in finding a collision.

One hash to rule them all--wot? that's all? (1)

slashdotard (835129) | more than 6 years ago | (#21554561)

There seems to a yet another massive explosion of XOR thought that seems to ignore the possibility of using more than one hash to sign an object, whether it be code, text or other data.

It has occurred to a few people--just a few people--to sign objects with both MD5 and SHA-1.

It seems that it is more difficult to get both MD5 and SHA-1 collisions by quite some orders of magnitude. Someday, perhaps, it can be done but not today. Well, no one has said so, at least.

Anyone for some OR thinking?

Ah yes, this again (4, Interesting)

Effugas (2378) | more than 6 years ago | (#21551063)

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.

Re:Ah yes, this again (1)

TorKlingberg (599697) | more than 6 years ago | (#21551423)

With a fairly short hash there will always we several valid codes with the same hash, but doing different things. However if finding such pairs is difficult enough, hash signing works. This difficulty is the whole point of hashes.

Re:Ah yes, this again (0)

Anonymous Coward | more than 6 years ago | (#21551779)

ur face contains ambient entropy

Re:Ah yes, this again (2, Insightful)

Henry V .009 (518000) | more than 6 years ago | (#21552009)

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.
That is simply wrong. For any "arbitrarily good" hash there exist collisions out there between bad_app and good_app. However, if finding bad_app or bad_app2, etc., is computationally impracticable (which is the definition of a good hash), then the hash is quite useful.

Currently md5 is fairly broken, in that a person can specially prepare good_app and bad_app. However, it is not yet completely broken (like CRC, if it were ever used as a secure hash), in that it is not yet possible for someone to take an arbitrary md5-signed file (like the recently released ubuntu iso, to give an example) and generate a collision. The birthday paradox makes the former much easier than the later.

Mod parent down ; missed the point (0)

Anonymous Coward | more than 6 years ago | (#21553413)

The grandparent wasn't trying to say that hashes can't identify applications. Instead it was trying to say that there's no such thing as a good app and a bad app. It's impossible to tell what an app will do in advance since very few apps can be entirely understood without understanding their entire runtime environment which is impossible.

However, the grandparent is still wrong; IMHO. App signing says a) this is the app that I built; you can trust it to behave that way. b) this app was built by XX who's reputation you can check up on. In general, a good application is designed so that it behaves properly independent of the different environmental inputs, within the scope of "normal" computer behavior (radiation attacks, for example, not included). An MD5 sum is not telling you that the formal proof of the application is good (there probably isn't one); instead it is allowing you to predict how the application was designed.

Re:Mod parent down ; missed the point (1)

Henry V .009 (518000) | more than 6 years ago | (#21553791)

I thought he might possibly have meant that. And yes, it's still wrong.

But what of the Crime Wave ?? (-1, Offtopic)

Anonymous Coward | more than 6 years ago | (#21551119)

What of the Crime Wave Thwarted in Second Life ?? Could this nullify the thwartedness of that which thwarted the Crime Wave ?? In Second life? Which begs to question, don't you have to have a life before you can have a second life ?? Damn, so many important considerations to consider thanks to here.

Use GnuPG instead (4, Insightful)

gweihir (88907) | more than 6 years ago | (#21551125)

As many projects have done for years. md5 sums as crypto-protection are more or less a historic way to do it.

Re:Use GnuPG instead (0)

Anonymous Coward | more than 6 years ago | (#21551707)

The default hash algorithm for GPG is SHA1--which is becoming weaker.

Bost projects I've seen.. (1)

Junta (36770) | more than 6 years ago | (#21552465)

Use public-private key signing rather than hashes (a hash is pretty limited, for *every* file to transfer, there must be a checksum in existence on the client side that got there through a 'secure' means. Signing means they just need to be confident they got your public key once and from then on out, your signatures can be proven/disproven on files without need for further guaranteed secure means.

About the only place I see MD5 sums used much is for large iso files, get the md5 sum from the distribution site, then grab the iso from a mirror and make sure it's ok. For apt and yum, where signatures are checked automatically, it's pretty certain they use public-private key signing.

Re:Bost projects I've seen.. (2, Insightful)

gweihir (88907) | more than 6 years ago | (#21553271)

I agree that today basically the only use of md5's is integrity checks against transmission and storage errors. I sometimes use them on backups.

You are quite right, that md5 does not provide and connection to the signer. With a PGP/GPG signature, once I have the correct public key, I can verify all and every signature made with it. And if I do not have the correct key, the first genuine signature will result in an error. Howeber I guess most people do not bother. Even if it is easy. For a kernel download, e.g., it adds about 5 seconds.

Optional Secutity ? tee hee ROF,LMFAO (1)

Grampaw Willie (631616) | more than 6 years ago | (#21552045)

FromMSDN Library:

Use digital signatures WHEN you want to distribute data, and you want to assure recipients that it does indeed come from you. Signing data does not alter it; it simply generates a digital signature string you can bundle with the data.
(emphasis added)

If you want security it has to be in effect 100% of the time. Not just here and there WHEN we have time for it and we don't bypass it to improve performance.

the issue here is not whether MD5 is vulnerable but whether it is being used all the time like it needs to be

anything and everything that is executable needs a signature that can be verified before it is executed and until that standard is made mandatory RATS will continue to have a festival which will only get worse and fast.

NO SIGNATURE? NO EXECUTE.

Cryptography such as these digital signatures is pretty good these days: proper use will render any attack on the cryptography itself a poor choice of options.

But Bruce Schneier notes in is recent book that all too often cryptography is like putting a post in the middle of a field and hoping the attacker runs into it. If there is anyway around the post the attacker will just take the easy way out and never bother the cryptography. He's not playing your game; he's playing a different game and he is governed only by the opportunities left open to him.

Signatures should be required on all eMails as well and any eMail without a signature that you recognize and approve should go into quarantine so you can dispose of it.

Door locks are insecure if you can get a key too! (2, Insightful)

Nezer (92629) | more than 6 years ago | (#21551177)

This may mean that the attacker needs insider access to the party operating the trusted software integrity protection or code signing process.
Isn't this a bit like saying that door locks are insecure although you may need access to a party trusted with the keys in order to exploit? Aren't these "trusted parties" *always* a potential weak-link in the security chain?

So MD5SUM veriefies downloads only (1)

houghi (78078) | more than 6 years ago | (#21551215)

I alsways thought that MD5SUMS where there only to verify wether a download was successfull or not.

Re:So MD5SUM veriefies downloads only (2, Informative)

grumbel (592662) | more than 6 years ago | (#21551297)

An MD5 checksum file alone serves no other purpose then to check that the download is correct, since an attacker that can upload a changed file could also just change the MD5 checksum file. Things look a little different if you get the MD5 from a different trusted source or when the MD5 file is signed by a GPG key.

Not a real life scenario... (3, Insightful)

Matthieu Araman (823) | more than 6 years ago | (#21551217)

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 ?)

what it really means .. (2, Interesting)

rs232 (849320) | more than 6 years ago | (#21551409)

"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:Not a real life scenario... (1)

SagSaw (219314) | more than 6 years ago | (#21552555)

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


True, but imagine that developer A is the attacker. That developer can create two different versions of his program: One benign version to go trough verification, QA testing, and any customer acceptance testing, and a malicious version which is actually distributed. Now developer A can slip in malicious features which would otherwise be discovered during testing.

Also, keep in mind that B might also have access to the signing key. If so, he can create X' and X'' from X which have the same MD5 sum. X', without malicious content, is made available for download. B can then use X'' for whatever he wants. For example, he can arrange that only his target gets X''. Since there have been no reports of problems with X', and the signature on X'' checks out and matches the signature on X', the target may never know that he has received a different version of X than everybody else.

Re:Not a real life scenario... (1)

Matthieu Araman (823) | more than 6 years ago | (#21553609)

If I trust developer A and he include bad thing, he will risk ruining his reputation so that's not a md5 problem.
The problem is also not the same with a binary only exe and some open source programs where you have access to the source and all the change in the repository are signed with a pgp key.
That way, it's easier to verify that a binary is made from a given source.
It's a lot harder to try hiding something like md5 garbage in source form.

Re:Not a real life scenario... (1)

SagSaw (219314) | more than 6 years ago | (#21554375)

If I trust developer A and he include bad thing, he will risk ruining his reputation so that's not a md5 problem.

Yes and no. In some cases, the risk of damage is low enough that it makes sense to trust the developer. In other cases, the risk is great enough that there should be safe-guards in place to ensure that a rogue developer can't insert malicious code. Safe-guards which rely on the MD5 hash should no longer be relied upon to prevent a rogue developer from inserting malicious code.

It's a lot harder to try hiding something like md5 garbage in source form.

Not necessarily. Take an empty line in the source file and add various combinations of tabs and spaces. For some languages, you might be able to add other white space characters as well. Or, you could add 128-bits worth of initialized variables and hide the fact that they do nothing. In any case, creating 128 possible changes to the file should be easy to do in a manner which passes a cursory inspection.

Re:Not a real life scenario... (0)

Anonymous Coward | more than 6 years ago | (#21553637)

But protecting me against attacks from the author is not something any sort of hash/signature system can do anyway. The author could attack a specific host just by checking the IP address (or any other unique attribute) of that host in his code, and executing the malicious version only on a match. Such code would pass the QA tests and would not generate problem reports for testers or other users. And it would work even if you hashed with more than one algorithm and signed with more than one key, because the program itself doesn't need to be changed between the "good" and "bad" versions.

So unless someone can think of an attack that doesn't require the cooperation or compromise of someone already capable of signing the code, I'm not gonna worry about this too much.

A workaround? (1)

finnw (415539) | more than 6 years ago | (#21551319)

Create trusted_program.

Take trusted_program and /bin/false, use this technique to generate trusted_program2 and false2.

Post both trusted_program2 and false2 on your web page along with their shared md5sum and invite the user to download them (presumably the user trusts you and your web server or he wouldn't download them in the first place.)

The user is now confident that you cannot replace trusted_program2 with malicious_program without changing the md5sum, because this technique only works with two prefixes, not three.

Re:A workaround? (1)

sqlrob (173498) | more than 6 years ago | (#21552521)

Here's an example with 12 [win.tue.nl] . Linked to from TFA even.

Nothing new (1)

kasperd (592156) | more than 6 years ago | (#21551453)

As others have pointed out, there is nothing new in this. The same has been demonstrated with other languages before. For example a few years ago it was demonstrated with postscript, and that was as far as I know the first demonstration with meaningful content. While that may have come as a surprise to some people, it was only a minor curiosity to people understanding how md5 works. Doing this thing with exe files is less significant than it was to do it with postscript files for the following reason. You are not likely to sign an exe file from an untrusted source, because there is no way to verify if the content is malicious, and most people know this. In fact that is the very reason for having signatures in the first place. With postscript files it is different, to most people a postscript file is just a document. With a document you can read it, and then you know exactly what the content is. At least I can understand why people would think that way. So less social engineering is required to get your crafted postscript file signed than it would to get a crafted exe file signed. If you can get somebody to sign your carefully crafted exe file, then this attack doesn't matter anyway. Because if you could get your malicious code into the signed executable, there are lots of other ways to trigger it. Having an interchangable piece of pseudorandom binary data in the file itself is a neat way to trigger your code. But it can be based on other external factors such as timing, the IP address of the machine, the existence of certain other files on the system, or just some secret sequence of inputs. It is all just the matter of putting a backdoor into a piece of code, and attacking md5 in this way is not even the most convenient backdoor you could make.

If it was possible to make a crafted file that would match the md5 of some existing file, which you had no control over, then there would be a lot more reason to worry. Luckily that is not the case yet. Still the demonstration of collisions does serve as a warning, that md5 is weak and maybe somebody will be able to completely break it at some point. There has been a reason to worry about that ever since the collisions were first demonstrated. The construction of additional collisions with meaningful content doesn't change that threat in any way. If you were not worried before this news but you are worried afterwards, it is because you didn't understand the threat.

Re:Nothing new (3, Interesting)

kasperd (592156) | more than 6 years ago | (#21551537)

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.

Security hashes (1)

billcopc (196330) | more than 6 years ago | (#21551497)

Okay so someone was a bit late to learn that MD5 collisions are indeed possible. Congrats, you're still retarded!

It's not exactly hard to understand that a 128-bit hash is going to be less unique than a multi-kilobyte executable. I believe 3rd grade math has that covered. With processor speed increasing steadily, these things become easier to break with each passing day.

Re:Security hashes (1)

SagSaw (219314) | more than 6 years ago | (#21552353)

It's not exactly hard to understand that a 128-bit hash is going to be less unique than a multi-kilobyte executable.

In theory, it should require 2^64 attempts to find two identical messages with the same MD5 hash. That should be enough to routine prevent brute-force attacks for the foreseeable future, except possibly for attackers with deep enough pockets to build special MD5 cracking machines. This issue isn't simply that the 128-bit hash is less unique than the multi-kilobyte executable being signed.

What the authors of this paper have done is expanded on a known flaw in the MD5 algorithm to allow them to find two messages with the same signature in 2^50 attempts instead of 2^64 attempts (requiring 1/16384th the time). What should only have been routinely possible for an attacker with the money to build dedicated hardware is now practical for anybody who wants to dedicate a Playstation3 to the task for a couple of days.

Also note that this attack "only" lets the attacker create two files with the same MD5 hash. It does not allow the attacker to create a new file with the same MD5 hash as an existing file. For now, the means the attacker still can't create a malicious executable to replace an existing, benign, executable unless the attacker also has access to the signing key or can change the published MD5 hash of the executable. However, if the attacker has access to the signing key or can change the MD5 hash published for the executable, he can create two versions of the executable. The attacker could submit the benign version verification and QA testing but distribute the malicious version instead.

Re:Security hashes (1)

billcopc (196330) | more than 6 years ago | (#21555689)

I don't trust MD5 hashes anyway. If I can't trust the source, I don't run its code.

Md5 as a signature (1)

Almahtar (991773) | more than 6 years ago | (#21551769)

I see a lot of comments about how, since this attack requires access to the file both before and after signing, this is a non-issue. In most cases you're right, but get creative.

You have a lengthy verification process for new software - you check it over thoroughly to make sure it can be trusted, and after you certify it as trustworthy you sign it and only need to re-certify if the signature changes next time you download it from me.

I deliver a new version of the software to you (the "good" version), you certify and sign it (using MD5, unfortunately for you). I swap out the "evil" one, and next time you download it -- sure enough, the signature verifies it's fine.

What if you even had a virus scanner that used MD5's on executables for lazy re-scanning when they'd been modified?

I'm not sounding the "holy crap we're doomed" alarms, just pointing out that if you can take two different files and get the same "signature" from them, it's not a very good "signature", now is it?

Re:Md5 as a signature (1)

Grampaw Willie (631616) | more than 6 years ago | (#21552175)

I deliver a new version of the software to you (the "good" version), you certify and sign it (using MD5, unfortunately for you). I swap out the "evil" one, and next time you download it -- sure enough, the signature verifies it's fine

That shouldn't work: MD5 requires the recipient to regenerate the HASH and then check the signature. I have no idea why they think this is a performance improvement as you are going to have to scan the entire content of the messsage ( program ) in order to regenerate the hash.

so by checking the signature on the HASH instead of on the whole document all then have done is to weaken PGP signature checking capability. But not much: the odds of two source files producing the same HASH ain't real good (HASH is like a CRC ) .

Use multiple hash functions... (0, Redundant)

Roogna (9643) | more than 6 years ago | (#21552087)

Back in the day I remember always being told that a single hash function was never secure for verifying information... and that for security you should use two -different- algorithms or more. Simply because an attacker can manipulate the data to collide in a single function, it's that much more difficult to manipulate the data to collide in two entirely different hash spaces.

Did this concept change over the years, or is it just me? heh

You could do this... (1)

ultramkancool (827732) | more than 6 years ago | (#21552195)

or you could just crack the MD5 check itself, since you are modifying the program anyways, seems kinda pointless.

MD5+SHA1? (1)

Midnight Thunder (17205) | more than 6 years ago | (#21552731)

Surely a hybrid MD5+SHA1 signature would prove better? You can find weaknesses in each, but putting them together and the likelihood of the both weaknesses appearing at the same time would be greatly diminished. Other than extra CPU requirements, are there any issues with this approach?

Re:MD5+SHA1? (1)

kasperd (592156) | more than 6 years ago | (#21552977)

Other than extra CPU requirements, are there any issues with this approach?
Depends on how you look at it, and what you are trying to protect against. In most cases combining two hashes in that way will produce something that can be attacked faster than brute force. You'd get better security with a hash function that was designed to be 288 bits in the first place. (Or even 256 bits). In fact even if the two hashes had no weaknesses at all, you could still produce a collision for the concatenation slightly slower than an attack against the strongest of the two.

An attack could work the following way. Produce a collision for the first block of sha1 (2^80 work using birthday attack, I think there might be faster ways). Take the output IV and repeat the attack for the next block. You are going to need about 64 blocks in total. That is 2^86 work. Now run through all combinations of your blocks to find a collision for md5 (that amount of work is nothing compared to the previous work). So this combined hash can be attacked in 2^86 work not 2^144 like you would expect from a 288 bit hash.

Re:MD5+SHA1? (1)

grumbel (592662) | more than 6 years ago | (#21553589)

True, but on the other side relying on a single hash leaves you with a single point of failure, if the hash function is compromised, you don't have anything trusted left to check against. If on the other side you have two hash function you have a good chance that you figure out that one of your hash functions isn't secure any more and thus have enough time to replace it with something new, since there is always that second, still secure, function left.

Re:MD5+SHA1? (1)

kasperd (592156) | more than 6 years ago | (#21553731)

If on the other side you have two hash function you have a good chance that you figure out that one of your hash functions isn't secure any more and thus have enough time to replace it with something new
Don't expect a better warning just because you are using two different hash functions. With md5 you did get the warning a few years ago. Still most uses of md5 are secure. If you were to be using two, there is no guarantee that you are going to be told about the first break, if somebody want to attack the combination, they might decide to keep silent until they have a working attack. It all boils down to the intentions of whoever finds the weakness. Besides, if you wanted to pay the price in terms of CPU usage, you could go for a 256 bit hash.

Re:MD5+SHA1? (1)

Cairnarvon (901868) | more than 6 years ago | (#21553757)

Similarly, since ROT13 is such a weak encryption, why not just apply it twenty times? It's bound to be stronger, no?
Okay, stupid example, but you can't assume just piling on additional algorithms is going to make things more secure. While it's probably reasonably safe for MD5+SHA1, you're almost certainly much better off just using, say, SHA-512 instead.

Alternative approach using AES-256 (1)

gr8dude (832945) | more than 6 years ago | (#21553449)

Although AES-256 is not a hashing algorithm, I've seen it applied in hashing [lazybit.com] . Since it is a block cipher, when you encrypt a file, at the last iteration you have a chunk of 256 bits, which is used as a digest. If you change anything in the file, the change will propagate to other blocks (if encryption is done in CBC mode), so the last block (i.e. digest) will be different.
Load More Comments
Slashdot Login

Need an Account?

Forgot your password?