{"thread":{"id":"28927","subject":"git behaviour question regarding SHA-1 and commits","startedAt":"2011-11-13T17:04:17Z","lastAt":"2011-11-14T13:04:07Z","messageCount":11,"participants":["vinassa vinassa","Ævar Arnfjörð Bjarmason","Jonathan Nieder","Dmitry Potapov","Junio C Hamano","Johannes Sixt","Jeff King","Victor Engmark"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"179388","messageId":"CAJuRt+r9BjYcead6hgzdUT0Bisz1D48cegqkoJ0S537VMYBy_g@mail.gmail.com","threadId":"28927","inReplyTo":null,"subject":"git behaviour question regarding SHA-1 and commits","fromName":"vinassa vinassa","fromEmail":"vinassa.vinassa@gmail.com","sentAt":"2011-11-13T17:04:17Z","receivedAt":"2011-11-13T17:04:17Z","isPatch":false,"sender":{"key":"vinassa.vinassa@gmail.com","avatar":null},"body":"Hello,\n\nI am relatively new to git; I have only used it to track other git\nprojects, and sometimes to format and send patches to them, but never\nto handle my own projects.\n\nNow I am considering using git for my next task at work.\n\nI am wondering about how git behaves currently, if I kinda win the\nlottery of the universe, and happen to create a commit with a SHA-1\nthat is already the SHA-1 of another commit in the previous history.\nHowever improbable.\n\nWould that be detected, so that I could just add a newline, and then\ncommit with a different resulting SHA-1,\nwould I just lose one of those commits (hopefully the new one), would\nI end up with a corrupted repository?\n\nI found some mention of this in the archive, more about SHA-1 security\nimplications, that were dismissed, but here I am looking at just a\nrandom, very unfortunate case, and just wondering if in this case I\nwould end up in a FUBAR situation.\n\nThank you,\n\nVinassa\n"},{"id":"179389","messageId":"CACBZZX7VTdc2wHYHb1BB-wCJbKLVEmbzQaBTV04S1KDrqeN73A@mail.gmail.com","threadId":"28927","inReplyTo":"CAJuRt+r9BjYcead6hgzdUT0Bisz1D48cegqkoJ0S537VMYBy_g@mail.gmail.com","subject":"Re: git behaviour question regarding SHA-1 and commits","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2011-11-13T17:41:05Z","receivedAt":"2011-11-13T17:41:05Z","isPatch":false,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"This is not something you have to worry about, just get on with using\nGit and stop worrying about phenomenally unlikely edge cases that are\nnever going to happen.\n"},{"id":"179390","messageId":"20111113182757.GA15194@elie.hsd1.il.comcast.net","threadId":"28927","inReplyTo":"CAJuRt+r9BjYcead6hgzdUT0Bisz1D48cegqkoJ0S537VMYBy_g@mail.gmail.com","subject":"Re: git behaviour question regarding SHA-1 and commits","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2011-11-13T18:27:57Z","receivedAt":"2011-11-13T18:27:57Z","isPatch":false,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Hi Vinassa,\n\nvinassa vinassa wrote:\n\n> I am wondering about how git behaves currently, if I kinda win the\n> lottery of the universe, and happen to create a commit with a SHA-1\n> that is already the SHA-1 of another commit in the previous history.\n> However improbable.\n\nThat would be great!  You could definitely get an academic paper out\nof it.\n\n> Would that be detected, so that I could just add a newline, and then\n> commit with a different resulting SHA-1,\n> would I just lose one of those commits (hopefully the new one), would\n> I end up with a corrupted repository?\n\nI suspect that one of the two commits would \"win\" the right to be\nshown by commands like \"git log\".  A commit made after one of the\ncommits participating in the hash collision might be stored as a delta\nagainst the wrong one in the pack, producing errors when you try to\naccess it (which is good, since it helps you find the hash collision\nand you can get a paper and prizes).\n\nThough I haven't tested.  It would be nice to have an md5git (or even\ntruncated-sha1-git) program to test this kind of thing with.\n\nThanks and hope that helps,\nJonathan\n"},{"id":"179395","messageId":"CAM6yGmBgpWzC_jgeyKbWCU-_NJ2NCjpOBHWtTtKyZd95P1xU=A@mail.gmail.com","threadId":"28927","inReplyTo":"20111113182757.GA15194@elie.hsd1.il.comcast.net","subject":"Re: git behaviour question regarding SHA-1 and commits","fromName":"vinassa vinassa","fromEmail":"vinassa.vinassa@gmail.com","sentAt":"2011-11-13T22:14:25Z","receivedAt":"2011-11-13T22:14:25Z","isPatch":false,"sender":{"key":"vinassa.vinassa@gmail.com","avatar":null},"body":"Hi, thanks for the responses, I get the picture. Some comments below still.\n\nOn Sun, Nov 13, 2011 at 7:27 PM, Jonathan Nieder <jrnieder@gmail.com> wrote:\n>\n> Hi Vinassa,\n>\n> vinassa vinassa wrote:\n>\n> > I am wondering about how git behaves currently, if I kinda win the\n> > lottery of the universe, and happen to create a commit with a SHA-1\n> > that is already the SHA-1 of another commit in the previous history.\n> > However improbable.\n>\n> That would be great!  You could definitely get an academic paper out\n> of it.\n>\n> > Would that be detected, so that I could just add a newline, and then\n> > commit with a different resulting SHA-1,\n> > would I just lose one of those commits (hopefully the new one), would\n> > I end up with a corrupted repository?\n>\n> I suspect that one of the two commits would \"win\" the right to be\n> shown by commands like \"git log\".  A commit made after one of the\n> commits participating in the hash collision might be stored as a delta\n> against the wrong one in the pack, producing errors when you try to\n> access it (which is good, since it helps you find the hash collision\n> and you can get a paper and prizes).\n\nAfter cashing in the prizes, I would be able then to git reset --soft,\nadd a newline, make another commit and go on with my work, right? No\nscrew up big enough to demand restoring from backups.\n\n> Though I haven't tested.  It would be nice to have an md5git (or even\n> truncated-sha1-git) program to test this kind of thing with.\n\nYes, would be nice. I'll try to see if I can wrap my mind around the\ntest infrastructure.\n\n> Thanks and hope that helps,\n> Jonathan\n\nThank you for your patience, I understand I should not worry about\nthis, but this has made me even more curious about what would happen..\n\nVinassa\n"},{"id":"179396","messageId":"CAHkcothpwYHK7qtmCE-XR8kVKb9bqfbSiWjLPW82SOEhohXR1g@mail.gmail.com","threadId":"28927","inReplyTo":"CAJuRt+r9BjYcead6hgzdUT0Bisz1D48cegqkoJ0S537VMYBy_g@mail.gmail.com","subject":"Re: git behaviour question regarding SHA-1 and commits","fromName":"Dmitry Potapov","fromEmail":"dpotapov@gmail.com","sentAt":"2011-11-13T22:14:35Z","receivedAt":"2011-11-13T22:14:35Z","isPatch":false,"sender":{"key":"dpotapov@gmail.com","avatar":"https://avatars.githubusercontent.com/u/6568595?v=4"},"body":"On Sun, Nov 13, 2011 at 9:04 PM, vinassa vinassa\n<vinassa.vinassa@gmail.com> wrote:\n>\n> I found some mention of this in the archive, more about SHA-1 security\n> implications, that were dismissed, but here I am looking at just a\n> random, very unfortunate case, and just wondering if in this case I\n> would end up in a FUBAR situation.\n\nI do not see how such an event would be very unfortunate considering\nthat it would make you instantaneously famous, so you could write a\nlot of articles about what happened and make a fortunate of it... but\nif we consider a _far_ much more likely event like some object from\nthe sky falling directly on your head at the moment when you are doing\na commit, that I would be really very unfortunate... So, maybe, you\nshould rent space in a bunker first just to work safely...\n\nSeriously, it is so ridiculous to worry so much about so improbable\nevent, while in practice a lot of repository corruptions comes from\nunreliable DRAM, disk storage, or some other reasons. The mean time\nbetween failures for high quality components is only a few hundred\nyears while doing a commit every second will take dozen million\ntimes more than the age of our universe to generate a collision. So,\nthose probabilities are so different that there is nothing in our\nevery day experiences that has the same scale difference. It is like\na hair width and the distance to the closest star.\n\n\nDmitry\n"},{"id":"179404","messageId":"7vwrb3l6v2.fsf@alter.siamese.dyndns.org","threadId":"28927","inReplyTo":"CACBZZX7VTdc2wHYHb1BB-wCJbKLVEmbzQaBTV04S1KDrqeN73A@mail.gmail.com","subject":"Re: git behaviour question regarding SHA-1 and commits","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-11-14T03:29:05Z","receivedAt":"2011-11-14T03:29:05Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Ævar Arnfjörð Bjarmason <avarab@gmail.com> writes:\n\n> This is not something you have to worry about, just get on with using\n> Git and stop worrying about phenomenally unlikely edge cases that are\n> never going to happen.\n\nPeople who repeated answers along this line, you can stop. The message has\nbeen heard, but without answering the original question.\n\nWhen we create a new object (i.e. \"git add\" to register a new blob\ncontents, \"git commit\" that internally generates new tree objects to\nrecord updated \"whole contents\" and then records the commit object), we\nfirst compute what the object name of the new object would be, and then\ncheck if we already have an object with the same object name in the object\nstore. If we do, we do not write the new copy of the object out (see the\nfunction write_sha1_file() in sha1_file.c and the call to has_sha1_file()\nthat bypasses write_loose_object()).\n\nSo the old contents will be kept without getting overwritten.\n\nWhich sounds nice, but it has interesting consequences, as we do not\nbother running byte-for-byte comparison when we find what we tried to\nwrite already existed in the object store in order to error out in fear of\nthe miniscule chance that we would hit a SHA-1 collision.\n\nIf the collision is between commit objects, for example, we would write\nthe (old) commit object name to the tip of the current branch. Most\nlikely, the tree object recorded in the (old) commit would not match the\ntree object your \"git commit\" wanted to record (otherwise you have hit\nSHA-1 collision twice in a row ;-), which would mean \"git status\" would\nshow that a whole bunch of paths have changed between the HEAD and the\nindex. Also \"git log\" would show the history leading to the (old) commit\nthat is likely to be very different from what you would expect immediately\nafter committing the collided commit. Of course, you could recover from it\nwith \"git reset --soft\" after finding out what the previous HEAD was from\nthe reflog, but it won't be a pleasant experience.\n\nThere can be other kinds of collisions (e.g. your latest commit might have\ncollided with an existing blob or tree, in which case it is likely that\nalmost nothing would work after finding a blob or tree in HEAD).\n"},{"id":"179412","messageId":"4EC0C5CF.3010708@viscovery.net","threadId":"28927","inReplyTo":"CAJuRt+r9BjYcead6hgzdUT0Bisz1D48cegqkoJ0S537VMYBy_g@mail.gmail.com","subject":"Re: git behaviour question regarding SHA-1 and commits","fromName":"Johannes Sixt","fromEmail":"j.sixt@viscovery.net","sentAt":"2011-11-14T07:39:59Z","receivedAt":"2011-11-14T07:39:59Z","isPatch":false,"sender":{"key":"j6t@kdbg.org","avatar":"https://avatars.githubusercontent.com/u/14810926?v=4"},"body":"Am 11/13/2011 18:04, schrieb vinassa vinassa:\n> I am wondering about how git behaves currently, if I kinda win the\n> lottery of the universe, and happen to create a commit with a SHA-1\n> that is already the SHA-1 of another commit in the previous history.\n> However improbable.\n> \n> Would that be detected, so that I could just add a newline, and then\n> commit with a different resulting SHA-1,\n> would I just lose one of those commits (hopefully the new one), would\n> I end up with a corrupted repository?\n\nI *think* the following would happen:\n\n1. Git detects that the (commit) object that it is about to generate\nalready exists, and does not write a new one.\n\n2. Then the branch's ref is updated to the SHA-1. Since the original\ncommit is somewhere back in history, this is effectively like 'git reset\n--soft that-commit'.\n\n3. At your next 'git diff --cached', you notice unexpected differences\nbetween the index and the branch head. You will wonder what happened.\n(\"Who typed 'git reset --soft that-commit' while I was looking the other\nway??\")\n\n4. To recover, you just 'git reset --soft @{1}' to revert to the state\nbefore the commit attempt, and commit again. Your commit message from the\nfirst attempt will be lost unless you have used -C or -F for your commit.\nAt any rate, you can reuse the exact same commit message for this second\ncommit attempt, because by now time will have advanced by at least one\nsecond, which gives you a different commit timestamp and, hence, a\ndifferent commit object.\n\n-- Hannes\n"},{"id":"179423","messageId":"20111114113235.GE10847@sigill.intra.peff.net","threadId":"28927","inReplyTo":"20111113182757.GA15194@elie.hsd1.il.comcast.net","subject":"Re: git behaviour question regarding SHA-1 and commits","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-11-14T11:32:35Z","receivedAt":"2011-11-14T11:32:35Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, Nov 13, 2011 at 12:27:57PM -0600, Jonathan Nieder wrote:\n\n> Though I haven't tested.  It would be nice to have an md5git (or even\n> truncated-sha1-git) program to test this kind of thing with.\n\nFortunately we have such a thing:\n\n  http://article.gmane.org/gmane.comp.version-control.git/184243\n\nThat one actually has 40 bits of hash entropy, so you'd expect to\ngenerate 2^20 (about a million) commits before accidentally colliding.\nIf you want an easier experiment, you could truncate it even further.\n\n-Peff\n"},{"id":"179424","messageId":"20111114114856.GF10847@sigill.intra.peff.net","threadId":"28927","inReplyTo":"7vwrb3l6v2.fsf@alter.siamese.dyndns.org","subject":"Re: git behaviour question regarding SHA-1 and commits","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-11-14T11:48:56Z","receivedAt":"2011-11-14T11:48:56Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, Nov 13, 2011 at 07:29:05PM -0800, Junio C Hamano wrote:\n\n> If the collision is between commit objects, for example, we would write\n> the (old) commit object name to the tip of the current branch. Most\n> likely, the tree object recorded in the (old) commit would not match the\n> tree object your \"git commit\" wanted to record (otherwise you have hit\n> SHA-1 collision twice in a row ;-), which would mean \"git status\" would\n> show that a whole bunch of paths have changed between the HEAD and the\n> index. Also \"git log\" would show the history leading to the (old) commit\n> that is likely to be very different from what you would expect immediately\n> after committing the collided commit. Of course, you could recover from it\n> with \"git reset --soft\" after finding out what the previous HEAD was from\n> the reflog, but it won't be a pleasant experience.\n> \n> There can be other kinds of collisions (e.g. your latest commit might have\n> collided with an existing blob or tree, in which case it is likely that\n> almost nothing would work after finding a blob or tree in HEAD).\n\nYou are more likely to just have blobs collide, since we generate many\nmore blobs than commits (each commit should have at least one changed\nblob, but typically has more).\n\nAnd in that case, I expect git would silently lose that state. We would\nfail to write the new blob to the object db, but \"git diff\" would report\nnothing, as it would see that the index entry's sha1 is the same as what\nis in HEAD, and that the file is up to date with respect to the stat\ninformation in the index. So if you were to \"git checkout\", your content\nwould be lost forever. However, if you instead modify the file further,\nthe new content will be kept (and you will get a very confusing diff).\n\n-Peff\n"},{"id":"179426","messageId":"20111114124851.GB21854@victor","threadId":"28927","inReplyTo":"20111114113235.GE10847@sigill.intra.peff.net","subject":"Re: git behaviour question regarding SHA-1 and commits","fromName":"Victor Engmark","fromEmail":"victor.engmark@terreactive.ch","sentAt":"2011-11-14T12:48:51Z","receivedAt":"2011-11-14T12:48:51Z","isPatch":false,"sender":{"key":"victor.engmark@terreactive.ch","avatar":null},"body":"On Mon, Nov 14, 2011 at 06:32:35AM -0500, Jeff King wrote:\n> On Sun, Nov 13, 2011 at 12:27:57PM -0600, Jonathan Nieder wrote:\n> \n> > Though I haven't tested.  It would be nice to have an md5git (or even\n> > truncated-sha1-git) program to test this kind of thing with.\n> \n> Fortunately we have such a thing:\n> \n>   http://article.gmane.org/gmane.comp.version-control.git/184243\n> \n> That one actually has 40 bits of hash entropy, so you'd expect to\n> generate 2^20 (about a million) commits before accidentally colliding.\n> If you want an easier experiment, you could truncate it even further.\n\nWould it be helpful to truncate this to something ludicrous like a\nsingle byte of entropy, to be able to write tests for the various tools\nand options?\n\nCheers,\nV\n\n-- \nterreActive AG\nKasinostrasse 30\nCH-5001 Aarau\nTel: +41 62 834 00 55\nFax: +41 62 823 93 56\nwww.terreactive.ch\n\nWir sichern Ihren Erfolg - seit 15 Jahren\n"},{"id":"179427","messageId":"20111114130407.GA24156@sigill.intra.peff.net","threadId":"28927","inReplyTo":"20111114124851.GB21854@victor","subject":"Re: git behaviour question regarding SHA-1 and commits","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-11-14T13:04:07Z","receivedAt":"2011-11-14T13:04:07Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Nov 14, 2011 at 01:48:51PM +0100, Victor Engmark wrote:\n\n> > Fortunately we have such a thing:\n> > \n> >   http://article.gmane.org/gmane.comp.version-control.git/184243\n> > \n> > That one actually has 40 bits of hash entropy, so you'd expect to\n> > generate 2^20 (about a million) commits before accidentally colliding.\n> > If you want an easier experiment, you could truncate it even further.\n> \n> Would it be helpful to truncate this to something ludicrous like a\n> single byte of entropy, to be able to write tests for the various tools\n> and options?\n\nThat's probably too small. Obviously any implementation like this is not\ngoing to be usable for interacting with existing repositories, but if\nyou have too many collisions, then you won't even be able to create a\nfew new commits for your test.\n\nSomething like 20 bits means you can brute-force a collision for a\nparticular blob, commit, tree, or whatever in a few seconds, but you\nwon't be having accidental ones all the time.\n\n-Peff\n"}]}