{"thread":{"id":"32186","subject":"Possible vulnerability to SHA-1 collisions","startedAt":"2012-11-24T11:12:28Z","lastAt":"2012-11-28T09:35:05Z","messageCount":6,"participants":["Michael Hirshleifer","Shawn Pearce","Jeff King","Aaron Schrab","Andreas Ericsson"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"203763","messageId":"50B0AB9C.2040802@caltech.edu","threadId":"32186","inReplyTo":null,"subject":"Possible vulnerability to SHA-1 collisions","fromName":"Michael Hirshleifer","fromEmail":"111mth@caltech.edu","sentAt":"2012-11-24T11:12:28Z","receivedAt":"2012-11-24T11:12:28Z","isPatch":false,"sender":{"key":"111mth@caltech.edu","avatar":null},"body":"Evil Guy creates 2 files, 1 evil and 1 innocuous, with the same SHA-1 \nchecksum (including Git header). Mr. Evil creates a local branch with an \ninnocuous name like “test-bugfix”, and adds a commit containing a \nreference to the evil file. Separately, using a sockpuppet, Evil Guy \ncreates an innocuous bugfix (very likely to be accepted) containing the \ninnocuous file, and submits it to Good Guy. Before Good Guy can commit \nthe bugfix, Evil Guy pushes the evil branch to Github, and then \nimmediately deletes it; or equivalently --force pushes any innocuous \ncommit on top of it. (This is unlikely to arouse suspicion, and he can \nalways say he deleted it because it didn’t work.)\n\nGit keeps unreferenced objects around for a few weeks, so when Good Guy \ncommits the patch and pushes to Github, an object with an sha1sum that \nmatches the good file will already exist in the main repository. Since \nGit keeps the local copy of files when sha1sums match, the main Github \nrepository will then contain the evil file associated with Good Guy’s \ncommit. Any users cloning from Github will get the evil version. This is \nan exploit.\n\nAnd Good Guy’s local repository will contain the good file; he will not \nnotice anything amiss unless he nukes his local repository and clones \nfrom Github again. Even when the compromise is discovered, there will be \nno reason to suspect Evil Guy; the evil file seems to have been \ncommitted by Good Guy.\n\nPrevious discussion about hash collisions in Git seems to conclude that \nthey aren’t a security threat. See \nhttp://stackoverflow.com/questions/9392365/how-would-git-handle-a-sha-1-collision-on-a-blob/9392525#9392525, \nLinus Torvalds arguing that Git’s security doesn’t depend on SHA-1 \ncollision resistance.\n\nThis proposed exploit does not involve social engineering, or any good \nguys failing to spot or accepting patches containing evil data (what \nGood Guy accepts is a genuine bugfix). It contaminates the main public \nrepository in a way that Good Guy won’t immediately notice. It does not \nrequire a second-preimage attack; Bad Guy creates both versions of the \nfile. While this does require the bad guy to have commit access, the bad \nguy can avoid suspicion after the attack.\n"},{"id":"203768","messageId":"CAJo=hJsZdduMdSbN+3Ei-7vx3_Q7tO88LywWj5Vw3Ngs0QgsZg@mail.gmail.com","threadId":"32186","inReplyTo":"50B0AB9C.2040802@caltech.edu","subject":"Re: Possible vulnerability to SHA-1 collisions","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2012-11-24T18:09:31Z","receivedAt":"2012-11-24T18:09:31Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"I don't think there is an issue the way you have tried to describe\nthis scenario.\n\nOn Sat, Nov 24, 2012 at 3:12 AM, Michael Hirshleifer <111mth@caltech.edu> wrote:\n> Evil Guy creates 2 files, 1 evil and 1 innocuous, with the same SHA-1\n> checksum (including Git header). Mr. Evil creates a local branch with an\n> innocuous name like “test-bugfix”, and adds a commit containing a reference\n> to the evil file. Separately, using a sockpuppet, Evil Guy creates an\n> innocuous bugfix (very likely to be accepted) containing the innocuous file,\n> and submits it to Good Guy. Before Good Guy can commit the bugfix, Evil Guy\n> pushes the evil branch to Github, and then immediately deletes it; or\n> equivalently --force pushes any innocuous commit on top of it. (This is\n> unlikely to arouse suspicion, and he can always say he deleted it because it\n> didn’t work.)\n\nHere you assume Evil Guy has write access to the same repository as\nGood Guy. Lets assume this is possible, e.g. Evil Guy is actually\nimpersonating White Hat because he managed to steal White Hat's\ncredentials through a compromised host. Typically Evil Guy doesn't\nhave write access to Good Guy's repository, and thus can't introduce\nobjects into it without Good Guy being the one that creates the\nobjects.\n\nBut lets just keep he assumption that Evil Guy can write to the same\nrepository as Good Guy, and that he managed to create the bad branch\nand delete it, leaving the bad object in an unreachable state for 2\nweeks.\n\n> Git keeps unreferenced objects around for a few weeks, so when Good Guy\n> commits the patch and pushes to Github, an object with an sha1sum that\n> matches the good file will already exist in the main repository. Since Git\n> keeps the local copy of files when sha1sums match, the main Github\n> repository will then contain the evil file associated with Good Guy’s\n> commit. Any users cloning from Github will get the evil version. This is an\n> exploit.\n\nTypically... Git will fail with an error message when Good Guy pushes.\nGood Guy's client will (rightly) believe that the object doesn't exist\non the remote side, after all it is unreachable. So his client will\ninclude it in the pack being transmitted during push. When this pack\narrives on the remote side, the remote will identify it already has an\nobject named the same as an object coming in the pack. The remote will\ndo a byte-for-byte compare of both objects. As soon as a single byte\ndiffers, it will abort with an error.\n\nAt this point Good Guy can't push to his repository. `git gc\n--expire=now` will fix the repository by removing the unreachable\nobject, at which point Evil Guy's evil object is gone.\n\n> And Good Guy’s local repository will contain the good file; he will not\n> notice anything amiss unless he nukes his local repository and clones from\n> Github again. Even when the compromise is discovered, there will be no\n> reason to suspect Evil Guy; the evil file seems to have been committed by\n> Good Guy.\n\nSee above. Good Guy would have noticed something is amiss because the\nobject he sent already existed and didn't match.\n\n> Previous discussion about hash collisions in Git seems to conclude that they\n> aren’t a security threat. See\n> http://stackoverflow.com/questions/9392365/how-would-git-handle-a-sha-1-collision-on-a-blob/9392525#9392525,\n> Linus Torvalds arguing that Git’s security doesn’t depend on SHA-1 collision\n> resistance.\n\nThis is largely true because there are additional defenses (e.g. the\nbyte for byte compare on identical objects), and for projects like the\nLinux kernel there are many eyes looking at files all of the time.\nAnything that is amiss would be announced quickly on LKML and\ndiscussed until the root cause is identified and resolved.\n"},{"id":"204052","messageId":"20121127230753.GA22730@sigill.intra.peff.net","threadId":"32186","inReplyTo":"CAJo=hJsZdduMdSbN+3Ei-7vx3_Q7tO88LywWj5Vw3Ngs0QgsZg@mail.gmail.com","subject":"Re: Possible vulnerability to SHA-1 collisions","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-11-27T23:07:53Z","receivedAt":"2012-11-27T23:07:53Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Nov 24, 2012 at 10:09:31AM -0800, Shawn O. Pearce wrote:\n\n> On Sat, Nov 24, 2012 at 3:12 AM, Michael Hirshleifer <111mth@caltech.edu> wrote:\n> > Evil Guy creates 2 files, 1 evil and 1 innocuous, with the same SHA-1\n> > checksum (including Git header). Mr. Evil creates a local branch with an\n> > innocuous name like “test-bugfix”, and adds a commit containing a reference\n> > to the evil file. Separately, using a sockpuppet, Evil Guy creates an\n> > innocuous bugfix (very likely to be accepted) containing the innocuous file,\n> > and submits it to Good Guy. Before Good Guy can commit the bugfix, Evil Guy\n> > pushes the evil branch to Github, and then immediately deletes it; or\n> > equivalently --force pushes any innocuous commit on top of it. (This is\n> > unlikely to arouse suspicion, and he can always say he deleted it because it\n> > didn’t work.)\n> \n> Here you assume Evil Guy has write access to the same repository as\n> Good Guy. Lets assume this is possible, e.g. Evil Guy is actually\n> impersonating White Hat because he managed to steal White Hat's\n> credentials through a compromised host. Typically Evil Guy doesn't\n> have write access to Good Guy's repository, and thus can't introduce\n> objects into it without Good Guy being the one that creates the\n> objects.\n> \n> But lets just keep he assumption that Evil Guy can write to the same\n> repository as Good Guy, and that he managed to create the bad branch\n> and delete it, leaving the bad object in an unreachable state for 2\n> weeks.\n\nActually, it is somewhat easier on GitHub, because we share objects\nbetween forks of a repository via the alternates mechanism. So if you\ncan publicly fork the project and push a branch to your fork, you can\nwrite to the shared object database. This applies not just to GitHub,\nbut to any hosting service which shares object databases between\nprojects (I do not know offhand if other hosting providers like Google\nCode do this).\n\nBut as you noted later in your email, the byte-for-byte comparison on\nobject collision will let us detect this case when the good guy tries to\npush and abort.\n\n-Peff\n\nPS I also think the OP's \"sockpuppet creates innocuous bugfix\" above is\n   easier said than done. We do not have SHA-1 collisions yet, but if\n   the md5 attacks are any indication, the innocuous file will not be\n   completely clean; it will need to have some embedded binary goo that\n   is mutated randomly during the collision process (which is why the\n   md5 attacks were demonstrated with postscript files which _rendered_\n   to look good, but contained a chunk of random bytes in a spot ignored\n   by the postscript interpreter).\n"},{"id":"204060","messageId":"20121127233016.GC3937@pug.qqx.org","threadId":"32186","inReplyTo":"20121127230753.GA22730@sigill.intra.peff.net","subject":"Re: Possible vulnerability to SHA-1 collisions","fromName":"Aaron Schrab","fromEmail":"aaron@schrab.com","sentAt":"2012-11-27T23:30:17Z","receivedAt":"2012-11-27T23:30:17Z","isPatch":false,"sender":{"key":"aaron@schrab.com","avatar":"https://avatars.githubusercontent.com/u/39620?v=4"},"body":"At 18:07 -0500 27 Nov 2012, Jeff King <peff@peff.net> wrote:\n>PS I also think the OP's \"sockpuppet creates innocuous bugfix\" above is\n>   easier said than done. We do not have SHA-1 collisions yet, but if\n>   the md5 attacks are any indication, the innocuous file will not be\n>   completely clean; it will need to have some embedded binary goo that\n>   is mutated randomly during the collision process (which is why the\n>   md5 attacks were demonstrated with postscript files which _rendered_\n>   to look good, but contained a chunk of random bytes in a spot ignored\n>   by the postscript interpreter).\n\nI don't think that really saves us though.  Many formats have parts of \nthe file which will be ignored, such as comments in source code.  With \nthe suggested type of attack, there isn't a requirement about which \nversion of the file is modified.  So the attacker should be able to \ngenerate a version of a file with an innocuous change, get the SHA-1 for \nthat, then add garbage comments to their malicious version of the file \nto try to get the same SHA-1.\n"},{"id":"204073","messageId":"20121128002714.GA23224@sigill.intra.peff.net","threadId":"32186","inReplyTo":"20121127233016.GC3937@pug.qqx.org","subject":"Re: Possible vulnerability to SHA-1 collisions","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-11-28T00:27:14Z","receivedAt":"2012-11-28T00:27:14Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Nov 27, 2012 at 06:30:17PM -0500, Aaron Schrab wrote:\n\n> At 18:07 -0500 27 Nov 2012, Jeff King <peff@peff.net> wrote:\n> >PS I also think the OP's \"sockpuppet creates innocuous bugfix\" above is\n> >  easier said than done. We do not have SHA-1 collisions yet, but if\n> >  the md5 attacks are any indication, the innocuous file will not be\n> >  completely clean; it will need to have some embedded binary goo that\n> >  is mutated randomly during the collision process (which is why the\n> >  md5 attacks were demonstrated with postscript files which _rendered_\n> >  to look good, but contained a chunk of random bytes in a spot ignored\n> >  by the postscript interpreter).\n> \n> I don't think that really saves us though.  Many formats have parts\n> of the file which will be ignored, such as comments in source code.\n\nAgreed, it does not save us unconditionally. It just makes it harder to\nexecute the attack. Would you take a patch from a stranger that had a\nkilobyte of binary garbage in a comment?\n\nA more likely avenue would be a true binary file where nobody is\nexpected to read the diff.\n\n> With the suggested type of attack, there isn't a requirement about\n> which version of the file is modified.  So the attacker should be\n> able to generate a version of a file with an innocuous change, get\n> the SHA-1 for that, then add garbage comments to their malicious\n> version of the file to try to get the same SHA-1.\n\nThat's not how birthday collision attacks usually work, though. You do\nnot get to just mutate the malicious side and leave the innocuous side\nuntouched. You are mutating both sides over and over and hoping to find\na matching sha1 from the \"good\" and \"evil\" sides.\n\nOf course, I have not been keeping up too closely with the efforts to\nbreak sha-1. Maybe there is something more nefarious about the current\nattacks. I am just going off my recollection of the md5 collision\nattacks.\n\n-Peff\n"},{"id":"204150","messageId":"50B5DAC9.7020609@op5.se","threadId":"32186","inReplyTo":"20121128002714.GA23224@sigill.intra.peff.net","subject":"Re: Possible vulnerability to SHA-1 collisions","fromName":"Andreas Ericsson","fromEmail":"ae@op5.se","sentAt":"2012-11-28T09:35:05Z","receivedAt":"2012-11-28T09:35:05Z","isPatch":false,"sender":{"key":"ae@op5.se","avatar":"https://gravatar.com/avatar/426e89595c75a8f5252dd0c989e5fabe5bcac616e68557427ad9aef6b0ca342a?d=mp&s=160"},"body":"On 11/28/2012 01:27 AM, Jeff King wrote:\n> On Tue, Nov 27, 2012 at 06:30:17PM -0500, Aaron Schrab wrote:\n> \n>> At 18:07 -0500 27 Nov 2012, Jeff King <peff@peff.net> wrote:\n>>> PS I also think the OP's \"sockpuppet creates innocuous bugfix\" above is\n>>>   easier said than done. We do not have SHA-1 collisions yet, but if\n>>>   the md5 attacks are any indication, the innocuous file will not be\n>>>   completely clean; it will need to have some embedded binary goo that\n>>>   is mutated randomly during the collision process (which is why the\n>>>   md5 attacks were demonstrated with postscript files which _rendered_\n>>>   to look good, but contained a chunk of random bytes in a spot ignored\n>>>   by the postscript interpreter).\n>>\n>> I don't think that really saves us though.  Many formats have parts\n>> of the file which will be ignored, such as comments in source code.\n> \n> Agreed, it does not save us unconditionally. It just makes it harder to\n> execute the attack. Would you take a patch from a stranger that had a\n> kilobyte of binary garbage in a comment?\n> \n> A more likely avenue would be a true binary file where nobody is\n> expected to read the diff.\n> \n>> With the suggested type of attack, there isn't a requirement about\n>> which version of the file is modified.  So the attacker should be\n>> able to generate a version of a file with an innocuous change, get\n>> the SHA-1 for that, then add garbage comments to their malicious\n>> version of the file to try to get the same SHA-1.\n> \n> That's not how birthday collision attacks usually work, though. You do\n> not get to just mutate the malicious side and leave the innocuous side\n> untouched. You are mutating both sides over and over and hoping to find\n> a matching sha1 from the \"good\" and \"evil\" sides.\n> \n> Of course, I have not been keeping up too closely with the efforts to\n> break sha-1. Maybe there is something more nefarious about the current\n> attacks. I am just going off my recollection of the md5 collision\n> attacks.\n> \n\nAFAIR, collision attacks can be executed with a 2^51 probability (with\na 2^80 claim, that's pretty bad), but preimage attacks are still stuck\nvery close to the claimed 2^160.\n\nThat means every attack involving SHA1 means Mr. Malicious creates\nboth the involved files or does exceptional research without sharing\nit.\n\nI think git's job is to make sure that write access to only one of\nthe repositories is insufficient to launch an attack. If the attacker\nmanages to change all repositories involved then the hash function\nused is really quite irrelevant.\n\n-- \nAndreas Ericsson                   andreas.ericsson@op5.se\nOP5 AB                             www.op5.se\nTel: +46 8-230225                  Fax: +46 8-230231\n\nConsidering the successes of the wars on alcohol, poverty, drugs and\nterror, I think we should give some serious thought to declaring war\non peace.\n"}]}