Stories
Slash Boxes
Comments
Search

News for nerds, stuff that matters

Slashdot Log In

Log In

Create Account  |  Retrieve Password

MD5 Proven Ineffective for App Signatures

Posted by Zonk on Sun Dec 02, 2007 06:31 AM
from the needs-a-bit-of-retooling dept.
Security Encryption
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.'"
+ -
story

Related Stories

Submission: MD5 proven ineffective for app signatures by prostoalex (308614)
[+] New Elliptic Curve Cryptography Record 43 comments
deian writes "Cryptography researchers Joppe W. Bos, Marcelo E. Kaihara, Thorsten Kleinjung, Arjen K. Lenstra and Peter L. Montgomery have just announced that they have set a new record for the elliptic curve discrete logarithm problem (ECDLP) by solving it over a 112-bit finite field. The previous record was for a 109-bit prime field and dates back from October 2002. Their calculation was done on the EPFL cluster of more than 200 PS3s (same one used to create the Rogue CA certificates and demonstrate a reproducible attack on MD5 algorithms). On the PS3, the effort is equivalent to about 14 full 56-bit DES key searches!"
This discussion has been archived. No new comments can be posted.
The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.

MD5 Proven Ineffective for App Signatures 50 Comments More /

 Full
 Abbreviated
 Hidden
More
Loading... please wait.

  • Nothing new (Score:5, Insightful)

    by grumbel (592662) <grumbel@gmx.de> on Sunday December 02 2007, @06:43AM (#21550943) Homepage
    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: (Score:2, Informative)

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

      14 Sep 2005

    • Re: (Score:2, Redundant)

      by Instine (963303)
      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 (Score:5, Interesting)

      by Bert64 (520050) <bert@[ ]shdot.fi ... m ['sla' in gap]> on Sunday December 02 2007, @07:16AM (#21551053) Homepage
      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: (Score:2, Informative)

        by jthill (303417)

        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: (Score:3, Interesting)

        by Kjella (173770)
        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
        • 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:Nothing new (Score:5, Informative)

      by Anonymous Coward on Sunday December 02 2007, @07:40AM (#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 (Score:5, Informative)

      by MathFox (686808) on Sunday December 02 2007, @07:44AM (#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: (Score:2, Informative)

      by The New Andy (873493)
      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;

    • 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: (Score:3, Informative)

        by grumbel (592662)
        ### 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.
    • 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

  • Well everyone's boned then (Score:4, Interesting)

    by tietokone-olmi (26595) on Sunday December 02 2007, @06:53AM (#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: (Score:2, Interesting)

      by 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 (Score:4, Informative)

      by CarpetShark (865376) on Sunday December 02 2007, @07:33AM (#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.

  • Not accurate, not new (Score:5, Insightful)

    by Niten (201835) on Sunday December 02 2007, @07:05AM (#21551015) Homepage

    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!

  • Birthday Attack (Score:5, Insightful)

    by tangent3 (449222) on Sunday December 02 2007, @07:15AM (#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 (Score:4, Informative)

      by Anonymous Coward on Sunday December 02 2007, @07:28AM (#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.
      • Mod parent up. The person is only a A/C, but I cannot see how this is related to the birthday paradox.

  • use two hash functions (Score:5, Informative)

    by m2943 (1140797) on Sunday December 02 2007, @07:17AM (#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 (Score:4, Interesting)

      by mollymoo (202721) on Sunday December 02 2007, @09:53AM (#21551549) Journal

      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.

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

  • Ah yes, this again (Score:5, Interesting)

    by Effugas (2378) * on Sunday December 02 2007, @07:18AM (#21551063) Homepage
    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.
    • 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: (Score:3, Insightful)

      by Henry V .009 (518000)

      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

  • Use GnuPG instead (Score:5, Insightful)

    by gweihir (88907) on Sunday December 02 2007, @07:39AM (#21551125)
    As many projects have done for years. md5 sums as crypto-protection are more or less a historic way to do it.
      • 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: (Score:3, Insightful)

          by gweihir (88907)
          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: (Score:3, Informative)

          by AnyoneEB (574727)

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

  • Door locks are insecure if you can get a key too! (Score:3, Insightful)

    by Nezer (92629) on Sunday December 02 2007, @07:49AM (#21551177) Homepage

    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?
  • I alsways thought that MD5SUMS where there only to verify wether a download was successfull or not.

    • Re: (Score:3, Informative)

      by grumbel (592662)
      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... (Score:3, Insightful)

    by Matthieu Araman (823) on Sunday December 02 2007, @08:05AM (#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 ?)
    • "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...
  • 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 (Score:4, Interesting)

      by kasperd (592156) on Sunday December 02 2007, @09:51AM (#21551537) Homepage Journal
      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.
  • 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

    • Well, duh! (Score:5, Insightful)

      by YA_Python_dev (885173) on Sunday December 02 2007, @06:59AM (#21550993) Journal

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

      • 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.
      • 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 (Score:5, Informative)

          by jthill (303417) on Sunday December 02 2007, @08:23AM (#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: (Score:2, Insightful)

        by hotrodent (1017236)
        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

All trademarks and copyrights on this page are owned by their respective owners. Comments are owned by the Poster. The Rest © 1997-2009 Geeknet, Inc.