{"thread":{"id":"49936","subject":"easy way to demonstrate length of colliding SHA-1 prefixes?","startedAt":"2018-12-02T12:08:50Z","lastAt":"2018-12-03T22:57:46Z","messageCount":5,"participants":["Robert P. J. Day","Ævar Arnfjörð Bjarmason","Matthew DeVore","Jeff King"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"364438","messageId":"alpine.LFD.2.21.1812020647440.32023@localhost.localdomain","threadId":"49936","inReplyTo":null,"subject":"easy way to demonstrate length of colliding SHA-1 prefixes?","fromName":"Robert P. J. Day","fromEmail":"rpjday@crashcourse.ca","sentAt":"2018-12-02T11:50:47Z","receivedAt":"2018-12-02T12:08:50Z","isPatch":false,"sender":{"key":"rpjday@crashcourse.ca","avatar":"https://avatars.githubusercontent.com/u/226084077?v=4"},"body":"\n  as part of an upcoming git class i'm delivering, i thought it would\nbe amusing to demonstrate the maximum length of colliding SHA-1\nprefixes in a repository (in my case, i use the linux kernel git repo\nfor most of my examples).\n\n  is there a way to display the objects in the object database that\nclash in the longest object name SHA-1 prefix; i mean, short of\nmanually listing all object names, running that through cut and sort\nand uniq and ... you get the idea.\n\n  is there a cute way to do that? thanks.\n\nrday\n"},{"id":"364439","messageId":"87y398uknn.fsf@evledraar.gmail.com","threadId":"49936","inReplyTo":"alpine.LFD.2.21.1812020647440.32023@localhost.localdomain","subject":"Re: easy way to demonstrate length of colliding SHA-1 prefixes?","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2018-12-02T13:23:56Z","receivedAt":"2018-12-02T13:24:01Z","isPatch":false,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Sun, Dec 02 2018, Robert P. J. Day wrote:\n\n>   as part of an upcoming git class i'm delivering, i thought it would\n> be amusing to demonstrate the maximum length of colliding SHA-1\n> prefixes in a repository (in my case, i use the linux kernel git repo\n> for most of my examples).\n>\n>   is there a way to display the objects in the object database that\n> clash in the longest object name SHA-1 prefix; i mean, short of\n> manually listing all object names, running that through cut and sort\n> and uniq and ... you get the idea.\n>\n>   is there a cute way to do that? thanks.\n\nYou'll always need to list them all. It's inherently an operation where\nfor each SHA-1 you need to search for other ones with that prefix up to\na given length.\n\nPerhaps you've missed that you can use --abbrev=N for this, and just\ngrep for things that are loger than that N, e.g. for linux.git:\n\n    git log --oneline --abbrev=10 --pretty=format:%h |\n    grep -E -v '^.{10}$' |\n    perl -pe 's/^(.{10}).*/$1/'\n\nThis will list the 4 objects that need more than 10 characters to be\nshown unambiguously. If you then \"git cat-file -t\" them you'll get the\ndisambiguation help.\n"},{"id":"364442","messageId":"alpine.LFD.2.21.1812021123050.5509@localhost.localdomain","threadId":"49936","inReplyTo":"87y398uknn.fsf@evledraar.gmail.com","subject":"Re: easy way to demonstrate length of colliding SHA-1 prefixes?","fromName":"Robert P. J. Day","fromEmail":"rpjday@crashcourse.ca","sentAt":"2018-12-02T16:24:31Z","receivedAt":"2018-12-02T16:24:37Z","isPatch":false,"sender":{"key":"rpjday@crashcourse.ca","avatar":"https://avatars.githubusercontent.com/u/226084077?v=4"},"body":"On Sun, 2 Dec 2018, Ævar Arnfjörð Bjarmason wrote:\n\n> On Sun, Dec 02 2018, Robert P. J. Day wrote:\n>\n> >   as part of an upcoming git class i'm delivering, i thought it\n> > would be amusing to demonstrate the maximum length of colliding\n> > SHA-1 prefixes in a repository (in my case, i use the linux kernel\n> > git repo for most of my examples).\n> >\n> >   is there a way to display the objects in the object database\n> > that clash in the longest object name SHA-1 prefix; i mean, short\n> > of manually listing all object names, running that through cut and\n> > sort and uniq and ... you get the idea.\n> >\n> >   is there a cute way to do that? thanks.\n>\n> You'll always need to list them all. It's inherently an operation\n> where for each SHA-1 you need to search for other ones with that\n> prefix up to a given length.\n\n  i assumed as much, just wasn't sure about the esoteric dark corners\nof git i've never gotten to yet.\n\n> Perhaps you've missed that you can use --abbrev=N for this, and just\n> grep for things that are loger than that N, e.g. for linux.git:\n>\n>     git log --oneline --abbrev=10 --pretty=format:%h |\n>     grep -E -v '^.{10}$' |\n>     perl -pe 's/^(.{10}).*/$1/'\n>\n> This will list the 4 objects that need more than 10 characters to be\n> shown unambiguously. If you then \"git cat-file -t\" them you'll get\n> the disambiguation help.\n\n  that's pretty close to what i came up with, thanks.\n\nrday\n\n-- \n\n========================================================================\nRobert P. J. Day                                 Ottawa, Ontario, CANADA\n                  http://crashcourse.ca/dokuwiki\n\nTwitter:                                       http://twitter.com/rpjday\nLinkedIn:                               http://ca.linkedin.com/in/rpjday\n========================================================================"},{"id":"364497","messageId":"5d63905a-4a52-0724-90f6-a2b0a7ab0f62@comcast.net","threadId":"49936","inReplyTo":"87y398uknn.fsf@evledraar.gmail.com","subject":"Re: easy way to demonstrate length of colliding SHA-1 prefixes?","fromName":"Matthew DeVore","fromEmail":"matvore@comcast.net","sentAt":"2018-12-03T22:30:44Z","receivedAt":"2018-12-03T22:31:02Z","isPatch":false,"sender":{"key":"matvore@comcast.net","avatar":"https://gravatar.com/avatar/550c64ce544f82818ad931e244dfb08bbb1febfa6d1ce3cfd65e76215ca0ac8a?d=mp&s=160"},"body":"\n\nOn 12/02/2018 05:23 AM, Ævar Arnfjörð Bjarmason wrote:\n> \n> On Sun, Dec 02 2018, Robert P. J. Day wrote:\n> \n>>    as part of an upcoming git class i'm delivering, i thought it would\n>> be amusing to demonstrate the maximum length of colliding SHA-1\n>> prefixes in a repository (in my case, i use the linux kernel git repo\n>> for most of my examples).\n>>\n>>    is there a way to display the objects in the object database that\n>> clash in the longest object name SHA-1 prefix; i mean, short of\n>> manually listing all object names, running that through cut and sort\n>> and uniq and ... you get the idea.\n>>\n>>    is there a cute way to do that? thanks.\n> \n\nHere is a one-liner to do it. It is Perl line noise, so it's not very \ncute, thought that is subjective. The output shown below is for the Git \nproject (not Linux) repository as I've currently synced it:\n\n$ git rev-list --objects HEAD | sort | perl -anE 'BEGIN { $prev = \"\"; \n$long = \"\" } $n = $F[0]; for my $i (reverse 1..40) {last if $i < \nlength($long); if (substr($prev, 0, $i) eq substr($n, 0, $i)) {$long = \nsubstr($prev, 0, $i); last} } $prev = $n; END {say $long}'\n\nc68038ef\n\n$ git cat-file -t c68038ef\n\nerror: short SHA1 c68038ef is ambiguous\nhint: The candidates are:\nhint:   c68038effe commit 2012-06-01 - vcs-svn: suppress a \nsigned/unsigned comparison warning\nhint:   c68038ef00 blob\nfatal: Not a valid object name c68038ef\n\n\n> You'll always need to list them all. It's inherently an operation where\n> for each SHA-1 you need to search for other ones with that prefix up to\n> a given length.\n> \n> Perhaps you've missed that you can use --abbrev=N for this, and just\n> grep for things that are loger than that N, e.g. for linux.git:\n> \n>      git log --oneline --abbrev=10 --pretty=format:%h |\n>      grep -E -v '^.{10}$' |\n>      perl -pe 's/^(.{10}).*/$1/'\n\nI think the goal was to search all object hashes, not just commits. And \ngit rev-list --objects will do that.\n"},{"id":"364499","messageId":"20181203225743.GA12254@sigill.intra.peff.net","threadId":"49936","inReplyTo":"5d63905a-4a52-0724-90f6-a2b0a7ab0f62@comcast.net","subject":"Re: easy way to demonstrate length of colliding SHA-1 prefixes?","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-12-03T22:57:43Z","receivedAt":"2018-12-03T22:57:46Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Dec 03, 2018 at 02:30:44PM -0800, Matthew DeVore wrote:\n\n> Here is a one-liner to do it. It is Perl line noise, so it's not very cute,\n> thought that is subjective. The output shown below is for the Git project\n> (not Linux) repository as I've currently synced it:\n> \n> $ git rev-list --objects HEAD | sort | perl -anE 'BEGIN { $prev = \"\"; $long\n> = \"\" } $n = $F[0]; for my $i (reverse 1..40) {last if $i < length($long); if\n> (substr($prev, 0, $i) eq substr($n, 0, $i)) {$long = substr($prev, 0, $i);\n> last} } $prev = $n; END {say $long}'\n\nOoh, object-collision golf.\n\nTry:\n\n  git cat-file --batch-all-objects --batch-check='%(objectname)'\n\ninstead of \"rev-list | sort\". It's _much_ faster, because it doesn't\nhave to actually open the objects and walk the graph.\n\nSome versions of uniq have \"-w\" (including GNU, but it's definitely not\nin POSIX), which lets you do:\n\n  git cat-file --batch-all-objects --batch-check='%(objectname)' |\n  uniq -cdw 7\n\nto list all collisions of length 7 (it will show just the first item\nfrom each group, but you can use -D to see them all).\n\n> > You'll always need to list them all. It's inherently an operation where\n> > for each SHA-1 you need to search for other ones with that prefix up to\n> > a given length.\n> > \n> > Perhaps you've missed that you can use --abbrev=N for this, and just\n> > grep for things that are loger than that N, e.g. for linux.git:\n> > \n> >      git log --oneline --abbrev=10 --pretty=format:%h |\n> >      grep -E -v '^.{10}$' |\n> >      perl -pe 's/^(.{10}).*/$1/'\n> \n> I think the goal was to search all object hashes, not just commits. And git\n> rev-list --objects will do that.\n\nYou can add \"-t --raw\" to see the abbreviated tree and blob names,\nthough it gets tricky around handling merges.\n\n-Peff\n"}]}