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

Hmm...

[Char-i-o's]

Need more salt.

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

Well, duh!

[YA_Python_dev]

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:

[bhima]

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:

[cheater512]

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

Re:

[mlts]

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 sur

Re:

[Garridan]

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 co

Re:

[cheater512]

Making bad.exe the same size is dead simple actually as long as its smaller to begin with.
You can pad it out without too much trouble.

Whats tougher is making dual collisions. Say MD5 and SHA1.

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.

Re:ONE block, surely

[jthill]

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:

[colmore]

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:

[hotrodent]

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

Re:

[account_deleted]

Comment removed based on user account deletion

Re:

[fatphil]

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:

[mrmeval]

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.

Re:

[fatphil]

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

Just plain wrong. Read the article.

Re:

[icepick72]

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:

[grumbel]

### 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:

[icepick72]

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(goo

Re:

[hackstraw]

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 executab

Nothing new

[grumbel]

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:

[Anonymous Coward]

http://www.codeproject.com/dotnet/HackingMd5.asp [codeproject.com]

14 Sep 2005

Re:

[Instine]

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

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

Re:

[jthill]

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 hav

Re:

[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

Re:

[norton_I]

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 (al

Re:

[Red Pointy Tail]

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

Re:Voting machines

[Dare nMc]

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

[Anonymous Coward]

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

[MathFox]

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:

[Ghubi]

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

Re:

[The New Andy]

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;

Re:

[account_deleted]

Comment removed based on user account deletion

Re:

[grumbel]

### 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:

[owlstead]

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 signin

Re:

[OrangeTide]

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

Re:

[fatphil]

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

[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:

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

This is a REMOTE attack, and reasonably potent

[CarpetShark]

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

[quigonn]

If you'd read the article,

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

Re:

[cloudmaster]

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

Re:

[OrangeTide]

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

Right

[setrops]

"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

[Niten]

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:

[Niten]

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

pretext attack, for the record.

Re:

[cortana]

You're at stage six, "Explain why a simple collision attack is still useless, it's really the second pre-image attack that counts".

http://www.linuxworld.com/cgi-bin/mailto/x_linux.cgi?pagetosend=/export/home/httpd/linuxworld/news/2007/111207-hash.html [linuxworld.com] :)

Re:

[ferespo]

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

Re:

[Niten]

(I'm no expert on this by any means, but I hope I can partially answer your 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'm not sure I completely understand what you mean by "private keys between the parts." But if you mean entirely symmetric encryption, then in many circumstances a cryptographic signature -- and therefore a hash function to produce the signature -- is unnecessary, as an attempt to tamper with a transmission without knowing the secret key would result in meaningless gibberish on the receiving end. The major caveat is t

Re:

[Eivind Eklund]

It is sometimes possible, depending on the exact way we use the symmetric cipher and the exact symmetric cipher.

Three examples:

First, a stream cipher. A stream cipher is a cipher that generate a pseudorandom stream of data, which you then XOR with your data stream. The most well-known stream ciphers are RC4 (used in e.g. SSL) and the one-time pad (having a bunch of true random data you XOR with your data, where the random stream is the same length as your data). The attack here is that the attacker c

Birthday Attack

[tangent3]

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

[Anonymous Coward]

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:

[owlstead]

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

Re:

[Anonymous Coward]

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 ne

use two hash functions

[m2943]

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

[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:

[m2943]

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:

[maxwell demon]

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:

[ToasterMonkey]

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.

I'll ask the same thing many others are asking. If you can sneak garbage into a binary, why not sneak the actual payload in? And... there are people who inspect binaries and are thrown off by random garbage code? What exactly are they looking for then? If I throw a fistful of metal widgets under someone's hood, would I expect to fool the driver or his mechanic? The attack most of you are suggesting is so bizarrely over-complicated.

It's like a crazy plan to put a suspicious looking EMPTY package in th

Re:

[noidentity]

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:

[AnyoneEB]

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.

Re:

[noidentity]

If this is true, then they should create a new MD5SHA1 hash function that can be treated as a unit and a single hash value when being displayed. Or would that be considered too impure/inelegant?

Re:

[AnyoneEB]

If you are going to start using a new hash function, you might as well use SHA-2 [wikipedia.org] or something else with no known attacks. MD5 and SHA1 attacks are interesting because a lot of existing applications use them, but seeing as there are known partial attacks against both, one would likely be best off avoiding them for new applications.

Re:

[m2943]

The issue is not whether two secure hash functions are better than one, the issue is whether two different, possibly insecure hash functions are better than one. And they are, because the probability that two independent hash functions become compromised at the same time is much smaller than a single function getting compromised.

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

[slashdotard]

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

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

Re:

[TorKlingberg]

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:

[Henry V .009]

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

Re:

[Henry V .009]

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

Re:

[Effugas]

No, I'll stand by my original point. Predicting the behavior of a turing-complete environment is quite literally the halting problem. People keep trying to "prove" software, and let me tell you first hand, it keeps failing miserably. I think you're ignoring the reality that most software transforms external data, meaning unpredictable environmental inputs (even mouse clicks!) are first class citizens.

The problem is that MD5 can only hash the bag of bits available at compile time. It misses the accumulat

Use GnuPG instead

[gweihir]

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

Optional Secutity ? tee hee ROF,LMFAO

[Grampaw Willie]

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

Bost projects I've seen..

[Junta]

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 sit

Re:

[gweihir]

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

Re:

[AnyoneEB]

As I understand it, the normal way to generate a digital signature is to use a hash algorithm like MD5 or SHA1 and then encrypt the hash with a private key. Then you verify by hashing the file and decrypting the signature with the public key and checking to see if they match. Therefore, distributing signatures instead of hashes is orthogonal to the discussion at hand. If the hash is broken, then the signature is broken, too.

See Wikipedia for more information on digital signatures [wikipedia.org].

Re:Best projects I've seen..

[gweihir]

Oh, the discussuion basically says that hash-only is broken anyways, even if the hash remains secure. Therefore breaking this specific hash does not matter a lot.

Door locks are insecure if you can get a key too!

[Nezer]

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?

Re:

[account_deleted]

Comment removed based on user account deletion

Re:

[grumbel]

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

[Matthieu Araman]

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

[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:

[SagSaw]

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

Re:

[Matthieu Araman]

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:

[SagSaw]

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

A workaround?

[finnw]

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 prefixe

Re:

[sqlrob]

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

Nothing new

[kasperd]

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 a

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.

Security hashes

[billcopc]

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:

[SagSaw]

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

Re:

[billcopc]

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

Md5 as a signature

[Almahtar]

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), y

Re:

[Grampaw Willie]

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

Use multiple hash functions...

[Roogna]

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

MD5+SHA1?

[Midnight Thunder]

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:

[kasperd]

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 sl

Re:

[grumbel]

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:

[kasperd]

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 co

Re:

[Cairnarvon]

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

[gr8dude]

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.