{"thread":{"id":"15745","subject":"Git commit hash clash prevention","startedAt":"2008-10-02T08:53:58Z","lastAt":"2008-10-02T16:04:28Z","messageCount":7,"participants":["martin f krafft","Thomas Rast","Johannes Schindelin","Jean-Luc Herren","Jakub Narebski","Stephan Beyer"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"92120","messageId":"20081002085358.GA5342@lapse.rw.madduck.net","threadId":"15745","inReplyTo":null,"subject":"Git commit hash clash prevention","fromName":"martin f krafft","fromEmail":"madduck@madduck.net","sentAt":"2008-10-02T08:53:58Z","receivedAt":"2008-10-02T08:53:58Z","isPatch":false,"sender":{"key":"madduck@madduck.net","avatar":null},"body":"Hi folks,\n\nthe other day during a workshop on Git, one of the attendants asked\nabout the scenario when two developers, Jane and David, both working\non the same project, both create a commit and the two just so happen\nto have the same SHA-1. I realise that the likelihood of this\nhappening is about as high as the chance of , but it *is* possible, isn't it? Even though this is thus\nsomewhat academic, I am still very curious about it.\n\nWhat happens when David now pulls from Jane? How does Git deal with\nthis?\n\nI imagine it'll be able to distinguish the two commits based on\nmetadata, but won't the DAG get corrupted?\n\nCheers,\n\n-- \nmartin | http://madduck.net/ | http://two.sentenc.es/\n \n\"and no one sings me lullabies,\n and no one makes me close my eyes,\n and so i throw the windows wide,\n and call to you across the sky\"\n -- pink floyd, 1971\n \nspamtraps: madduck.bogus@madduck.net\n"},{"id":"92124","messageId":"200810021118.15313.trast@student.ethz.ch","threadId":"15745","inReplyTo":"20081002085358.GA5342@lapse.rw.madduck.net","subject":"Re: Git commit hash clash prevention","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2008-10-02T09:18:13Z","receivedAt":"2008-10-02T09:18:13Z","isPatch":false,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"martin f krafft wrote:\n> the other day during a workshop on Git, one of the attendants asked\n> about the scenario when two developers, Jane and David, both working\n> on the same project, both create a commit and the two just so happen\n> to have the same SHA-1. I realise that the likelihood of this\n> happening is about as high as the chance of here>, but it *is* possible, isn't it? Even though this is thus\n> somewhat academic, I am still very curious about it.\n> \n> What happens when David now pulls from Jane? How does Git deal with\n> this?\n\nThere are two cases:\n\n* The commits are exactly identical. This won't happen in your\n scenario, but is still theoretically possible if you commit the same\n tree with the same author info, timestamps, etc. on two different\n machines. Then there is no problem, because they really are the\n same.\n\n* They're not identical, but there is a hash collision. Git will\n become very confused because it only ever saves one of them. (I\n suppose it'd \"only\" corrupt the DAG if the two are commits, but in\n the general case a commit could collide with a tree etc.)\n\n However, the expected number of objects needed to get a collision is\n on the order of 2**80 (http://en.wikipedia.org/wiki/Birthday_attack),\n and since there are (very roughly) 2**25 seconds in a year and 2**34\n years in the age of the universe, that still leaves you with 2**21\n ages of the universe to go.\n\n(I hope I did the counting right...)\n\n> I imagine it'll be able to distinguish the two commits based on\n> metadata, but won't the DAG get corrupted?\n\nNo, it does not distinguish between objects in any way but the SHA1.\n\n- Thomas\n\n-- \nThomas Rast\ntrast@student.ethz.ch\n\n\n"},{"id":"92126","messageId":"alpine.DEB.1.00.0810021202420.22125@pacific.mpi-cbg.de.mpi-cbg.de","threadId":"15745","inReplyTo":"20081002085358.GA5342@lapse.rw.madduck.net","subject":"Re: Git commit hash clash prevention","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2008-10-02T10:07:32Z","receivedAt":"2008-10-02T10:07:32Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Thu, 2 Oct 2008, martin f krafft wrote:\n\n> the other day during a workshop on Git, one of the attendants asked \n> about the scenario when two developers, Jane and David, both working on \n> the same project, both create a commit and the two just so happen to \n> have the same SHA-1. I realise that the likelihood of this happening is \n> about as high as the chance of , but it *is* \n> possible, isn't it? Even though this is thus somewhat academic, I am \n> still very curious about it.\n\nIt _is_ academic. Did you already discuss the chance that your wife gives \nbirth to a mouse? I haven't done the maths yet, but I am pretty certain \nthat this would be more likely than an unintended SHA-1 collision.\n\n> What happens when David now pulls from Jane? How does Git deal with \n> this?\n\nBasically, the commit that David has will not be overwritten. So every \ncommit referring to Jane's commit would point to David's in his \nrepository.\n\nBut the more likely case (well, as likely goes) would be that either \nJane's or David's object is actually a blob. And Git would complain about \na type mismatch then.\n\nCiao,\nDscho\n"},{"id":"92138","messageId":"48E4ABC0.80100@gmx.ch","threadId":"15745","inReplyTo":"200810021118.15313.trast@student.ethz.ch","subject":"Re: Git commit hash clash prevention","fromName":"Jean-Luc Herren","fromEmail":"jlh@gmx.ch","sentAt":"2008-10-02T11:08:48Z","receivedAt":"2008-10-02T11:08:48Z","isPatch":false,"sender":{"key":"jlh@gmx.ch","avatar":null},"body":"Hello list!\n\nThomas Rast wrote:\n> However, the expected number of objects needed to get a collision is\n> on the order of 2**80 (http://en.wikipedia.org/wiki/Birthday_attack),\n> and since there are (very roughly) 2**25 seconds in a year and 2**34\n> years in the age of the universe, that still leaves you with 2**21\n> ages of the universe to go.\n\nIn case it's interesting to someone, I once calculated (and wrote\ndown) the math for the following scenario:\n\n - 10 billion humans are programming\n - They *each* produce 5000 git objects every day\n - They all push to the same huge repository\n - They keep this up for 50 years\n\nWith those highly exagerated assumptions, the probability of\ngetting a hash collision in that huge git object database is\n6e-13. Provided I got the math right.\n\nSo, mathematically speaking you have to say \"yes, it *is*\npossible\". But math aside it's perfectly correct to say \"no, it\nwon't happen, ever\". (Speaking about the *accidental* case.)\n\njlh\n"},{"id":"92155","messageId":"m3prmjqeq8.fsf@localhost.localdomain","threadId":"15745","inReplyTo":"20081002085358.GA5342@lapse.rw.madduck.net","subject":"Re: Git commit hash clash prevention","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2008-10-02T14:00:18Z","receivedAt":"2008-10-02T14:00:18Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"martin f krafft writes:\n\n> the other day during a workshop on Git, one of the attendants asked\n> about the scenario when two developers, Jane and David, both working\n> on the same project, both create a commit and the two just so happen\n> to have the same SHA-1. I realise that the likelihood of this\n> happening is about as high as the chance of here>, but it *is* possible, isn't it? Even though this is thus\n> somewhat academic, I am still very curious about it.\n> \n> What happens when David now pulls from Jane? How does Git deal with\n> this?\n\nCannot happen in practice.\n\nBut just in case git trusts object it already has in repository over\nobject which just got fetched (or pushed).\n\n-- \nJakub Narebski\nPoland\nShadeHawk on #git\n"},{"id":"92181","messageId":"alpine.DEB.1.00.0810021735410.22125@pacific.mpi-cbg.de.mpi-cbg.de","threadId":"15745","inReplyTo":"m3prmjqeq8.fsf@localhost.localdomain","subject":"Re: Git commit hash clash prevention","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2008-10-02T15:39:26Z","receivedAt":"2008-10-02T15:39:26Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Thu, 2 Oct 2008, Jakub Narebski wrote:\n\n> martin f krafft writes:\n> \n> > the other day during a workshop on Git, one of the attendants asked\n> > about the scenario when two developers, Jane and David, both working\n> > on the same project, both create a commit and the two just so happen\n> > to have the same SHA-1. I realise that the likelihood of this\n> > happening is about as high as the chance of > here>, but it *is* possible, isn't it? Even though this is thus\n> > somewhat academic, I am still very curious about it.\n> > \n> > What happens when David now pulls from Jane? How does Git deal with\n> > this?\n> \n> Cannot happen in practice.\n> \n> But just in case git trusts object it already has in repository over\n> object which just got fetched (or pushed).\n\nOh, maybe the most important part: both David and Jane would have to \nrewrite their respective history, changing the respective commits in a \nsimple way (such as adding a space to the first line of the commit message \nor some such). Then, Git is changed to not accept that particular SHA-1 \n(we'd introduce a black \"list\").\n\nAll in all, it would be like a borked commit; not really easy to fix, but \nthe world would not stop turning because of it.\n\nCiao,\nDscho\n"},{"id":"92183","messageId":"20081002160427.GD7288@leksak.fem-net","threadId":"15745","inReplyTo":"20081002085358.GA5342@lapse.rw.madduck.net","subject":"Re: Git commit hash clash prevention","fromName":"Stephan Beyer","fromEmail":"s-beyer@gmx.net","sentAt":"2008-10-02T16:04:28Z","receivedAt":"2008-10-02T16:04:28Z","isPatch":false,"sender":{"key":"s-beyer@gmx.net","avatar":"https://avatars.githubusercontent.com/u/143889?v=4"},"body":"Hi,\n\nmartin f krafft wrote:\n> Hi folks,\n> \n> the other day during a workshop on Git, one of the attendants asked\n> about the scenario when two developers, Jane and David, both working\n> on the same project, both create a commit and the two just so happen\n> to have the same SHA-1.\n\nChanging the committer time is the easiest way to solve this problem,\nif it ever happens.\n\nI have wondered how Git would behave if there are two files that are\nnot equal but have the same SHA-1. But I haven't found any such example\nfiles to test this scenario and have not had the time to write or\nlook for a tool that generates them. (MD5 collisions can be generated\nwithin 2 hours on usual home hardware and even Wikipedia links to\ncollided files. An intelligent search for SHA-1 collisions takes\n2^63 evaluations and not 2^80 (simple birthday attack) as expected.\nSo it should be possible to find some random collisions and test the\nbehavior...)\n\nBut even if git behaves terrible useless in such situations, it\ndoes not make any sense to guard against them, because in practice\nthey just do not happen. (And I think such guards will just slow git\ndown in the usual case.)\n\nRegards,\n Stephan\n\n-- \nStephan Beyer , PGP 0x6EDDD207FCC5040F\n"}]}