{"thread":{"id":"32031","subject":"What about SHA-1 collisions?","startedAt":"2012-11-06T20:26:43Z","lastAt":"2012-11-07T23:44:43Z","messageCount":5,"participants":["Josef Wolf","John McKown","Shawn Pearce","Andrew Ardill"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"202599","messageId":"20121106202643.GF28437@raven.wolf.lan","threadId":"32031","inReplyTo":null,"subject":"What about SHA-1 collisions?","fromName":"Josef Wolf","fromEmail":"jw@raven.inka.de","sentAt":"2012-11-06T20:26:43Z","receivedAt":"2012-11-06T20:26:43Z","isPatch":false,"sender":{"key":"jw@raven.inka.de","avatar":null},"body":"Hello,\n\nwe all know, the probability for SHA-1 collisions is very, very low, almost\nnon-existant. But we also know that they are not impossible.\n\nJust for curiosity: what would happen if such a collision would occur within\none repository?\n"},{"id":"202604","messageId":"loom.20121106T223000-502@post.gmane.org","threadId":"32031","inReplyTo":"20121106202643.GF28437@raven.wolf.lan","subject":"Re: What about SHA-1 collisions?","fromName":"John McKown","fromEmail":"john.mckown@healthmarkets.com","sentAt":"2012-11-06T21:41:29Z","receivedAt":"2012-11-06T21:41:29Z","isPatch":false,"sender":{"key":"john.mckown@healthmarkets.com","avatar":null},"body":"Josef Wolf <jw <at> raven.inka.de> writes:\n\n> \n> Hello,\n> \n> we all know, the probability for SHA-1 collisions is very, very low, almost\n> non-existant. But we also know that they are not impossible.\n> \n> Just for curiosity: what would happen if such a collision would occur within\n> one repository?\n> \n\nIn a sense, this cannot happen. Suppose you have a new working directory.\nYou do a \"git init\" to initialize it for use by git. You then copy in a\nbunch of data from elsewhere. By chance, files \"a\" and \"b\" have different\ncontent, but the same sha1 (they collide). The \"git add .\" command is\nbasically a short cut for doing something like:\nfor i in *;do git add $i;done\nThat is, it seems to add each file, one at a time in some order. Suppose\nit creates the sha1 for \"a\" first. It then creates the appropriate\n\"stuff\" for file \"a\" in the .git subdirectory, based on the sha1 value. Now,\nit gets around to processing \"b\". It gets the sha1 value of b and finds\nthat it already has an entry for that value. At that point, the \"git add\" thinks\n\"Oh, I've already processed this file. No need to do anything!\" So the contents\nof file \"b\" are not saved anywhere in git and, bottom line, that version of \"b\" \nwill not be in the git repository. Ever. Because \"a\" already has that SHA1 \"tied \nup\" and it is (theoretically) never released.\n\nI think of the SHA1 value being a unique key into a \"write once\" database. Once \nyou've added some content (a file) into the database, then the SHA1 value of\nthat content (file) is unmodifiable. Attempts to write another record into the \ndatabase is rejected (in a read DB, you'd get some sort of DUPLICATE KEY \nresponse). Git considers the \"duplicate key\" to be just fine because it ASSUMES \nthat the SHA1 is unique to the first file (content) which generates it.\n\nHope I made sense.\n\nJohn\n"},{"id":"202605","messageId":"20121106220938.GH28437@raven.wolf.lan","threadId":"32031","inReplyTo":"loom.20121106T223000-502@post.gmane.org","subject":"Re: What about SHA-1 collisions?","fromName":"Josef Wolf","fromEmail":"jw@raven.inka.de","sentAt":"2012-11-06T22:09:38Z","receivedAt":"2012-11-06T22:09:38Z","isPatch":false,"sender":{"key":"jw@raven.inka.de","avatar":null},"body":"On Tue, Nov 06, 2012 at 09:41:29PM +0000, John McKown wrote:\n> Josef Wolf <jw <at> raven.inka.de> writes:\n> > Just for curiosity: what would happen if such a collision would occur within\n> > one repository?\n\n> In a sense, this cannot happen.\n\nIn the scenario you described, contents of this version of file \"b\" are lost\nand replaced by the contents of file \"a\". So file \"b\" is broken.\n\nWhat happens when files \"a\" and \"b\" are added into different repositories?\nFile \"a\" is added to repos \"A\", and file \"b\" is added to repos \"B\". Now it\ndepends from which repository you fetch the collided blob first. If you fetch\nit from \"A\", file \"b\" will be broken. If you fetch first from \"B\", your \"a\"\nwill be broken.\n\nIt becomes even more interesting, if some commit or tree object would have\nthe same SHA1 as some other object. I guess, in such a case the repository\nwould be completely hosed?\n"},{"id":"202614","messageId":"CAJo=hJtF2+Z1BDQnysB7hk2MM336iEUMHd3zSLCm14yvw1_-wg@mail.gmail.com","threadId":"32031","inReplyTo":"20121106220938.GH28437@raven.wolf.lan","subject":"Re: What about SHA-1 collisions?","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2012-11-07T15:42:55Z","receivedAt":"2012-11-07T15:42:55Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Tue, Nov 6, 2012 at 2:09 PM, Josef Wolf <jw@raven.inka.de> wrote:\n>\n> On Tue, Nov 06, 2012 at 09:41:29PM +0000, John McKown wrote:\n> > Josef Wolf <jw <at> raven.inka.de> writes:\n> > > Just for curiosity: what would happen if such a collision would occur within\n> > > one repository?\n>\n> > In a sense, this cannot happen.\n>\n> In the scenario you described, contents of this version of file \"b\" are lost\n> and replaced by the contents of file \"a\". So file \"b\" is broken.\n>\n> What happens when files \"a\" and \"b\" are added into different repositories?\n> File \"a\" is added to repos \"A\", and file \"b\" is added to repos \"B\". Now it\n> depends from which repository you fetch the collided blob first. If you fetch\n> it from \"A\", file \"b\" will be broken. If you fetch first from \"B\", your \"a\"\n> will be broken.\n>\n> It becomes even more interesting, if some commit or tree object would have\n> the same SHA1 as some other object. I guess, in such a case the repository\n> would be completely hosed?\n\nWhen exchanging objects over the network, Git compares byte-for-byte\nany object that one side sent that the other side already has, and\ncomplains loudly when there is a collision detected. This only works\nif the sender includes the \"wrong\" content for the named object. Git\nalso does assume the SHA-1 is unique and that it is not always\nnecessary to transmit the object. In these cases you would not be able\nto detect the collision, because there isn't one. Your repository\nwould simply be using the wrong content for a file. Presumably one\nwould notice your build doesn't work anymore and investigate why.\n"},{"id":"202626","messageId":"CAH5451mwShC3QmX-5NxUO-00gx6uxNVKUHw4zrb=pyduHBJXLQ@mail.gmail.com","threadId":"32031","inReplyTo":"CAJo=hJtF2+Z1BDQnysB7hk2MM336iEUMHd3zSLCm14yvw1_-wg@mail.gmail.com","subject":"Re: What about SHA-1 collisions?","fromName":"Andrew Ardill","fromEmail":"andrew.ardill@gmail.com","sentAt":"2012-11-07T23:44:43Z","receivedAt":"2012-11-07T23:44:43Z","isPatch":false,"sender":{"key":"andrew.ardill@gmail.com","avatar":"https://gravatar.com/avatar/da14cb7c091dd44dc6c63a4d3361b149acaf25226dc78eb4131a17b93d9b0993?d=mp&s=160"},"body":" A recent article [1] did an analysis on the number of items needed\nfrom a given range to have a 50% chance of a collision. The famous\nbirthday paradox scenario was used, where you only need 23 people\nbefore the chance of two of them having the same birthday is over 50%.\nIn this scenario there are ~366 options available to be picked from,\nand 23 is significantly small in comparison.\n\nThe mathematics behind these statistics was extended to account for\nany sized range (call it N) and it turns out that the number of items\n(k) that can be picked before you have exceeded a given percentage\nchance (T) of _not_ having a collision is roughly\n\nk ~= sqrt(-2N.ln(T))\n\nAs pedrocr pointed out on Hacker News [2]\n\n\"Applying the formula for 160bit SHA-1 you need 1.7e23 objects to get\na 1% chance of collision. The current Linus kernel repository has 2.7\nmillion objects. So to get a collision you'd need a repository that's\n6e16 times larger. That should be plenty.\n\nFor some wacky perspective that's 10 million kernel sized\ncontributions for every man woman and child on earth together in a\nsingle repository. It would seem git will reach plenty of other\nbottlenecks before SHA-1 becomes a problem...\"\n\nAn interesting analysis, even given that the OP presumes a collision\nin their question.\n\nRegards,\n\nAndrew Ardill\n\n[1] http://www.solipsys.co.uk/new/TheBirthdayParadox.html\n[2] http://news.ycombinator.com/item?id=4753198\n"}]}