{"thread":{"id":"23945","subject":"[PATCH] diff.c: Ensure \"index $from..$to\" line contains unambiguous SHA1s","startedAt":"2010-05-30T13:37:17Z","lastAt":"2010-05-30T23:23:22Z","messageCount":3,"participants":["Johan Herland","Johannes Sixt"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"142573","messageId":"201005301537.18039.johan@herland.net","threadId":"23945","inReplyTo":null,"subject":"[PATCH] diff.c: Ensure \"index $from..$to\" line contains unambiguous SHA1s","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2010-05-30T13:37:17Z","receivedAt":"2010-05-30T13:37:17Z","isPatch":true,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"In the metainfo section of git diffs there's an \"index\" line providing\nabbreviated (unless --full-index is used) blob SHA1s from the\npre-/post-images used to generate the diff. These provide hints that\ncan be used to reconstruct a 3-way merge when applying the patch\n(see the --3way option to 'git am' for more details).\n\nIn order for this to work, however, the blob SHA1s must not be\nabbreviated into ambiguity.\n\nThis patch eliminates the possible ambiguity by using find_unique_abbrev()\nto produce the abbreviated SHA1s (instead of blind abbreviation by way of\n\"%.*s\").\n\nA testcase verifying the fix is also included.\n\nSigned-off-by: Johan Herland <johan@herland.net>\n---\n diff.c                              |    6 +++---\n t/t4043-diff-index-unique-abbrev.sh |   35 +++++++++++++++++++++++++++++++++++\n 2 files changed, 38 insertions(+), 3 deletions(-)\n create mode 100755 t/t4043-diff-index-unique-abbrev.sh\n\ndiff --git a/diff.c b/diff.c\nindex 494f560..1aefa66 100644\n--- a/diff.c\n+++ b/diff.c\n@@ -2419,9 +2419,9 @@ static void fill_metainfo(struct strbuf *msg,\n \t\t\t    (!fill_mmfile(&mf, two) && diff_filespec_is_binary(two)))\n \t\t\t\tabbrev = 40;\n \t\t}\n-\t\tstrbuf_addf(msg, \"index %.*s..%.*s\",\n-\t\t\t    abbrev, sha1_to_hex(one->sha1),\n-\t\t\t    abbrev, sha1_to_hex(two->sha1));\n+\t\tstrbuf_addf(msg, \"index %s..\",\n+\t\t\t    find_unique_abbrev(one->sha1, abbrev));\n+\t\tstrbuf_addstr(msg, find_unique_abbrev(two->sha1, abbrev));\n \t\tif (one->mode == two->mode)\n \t\t\tstrbuf_addf(msg, \" %06o\", one->mode);\n \t\tstrbuf_addch(msg, '\\n');\ndiff --git a/t/t4043-diff-index-unique-abbrev.sh b/t/t4043-diff-index-unique-abbrev.sh\nnew file mode 100755\nindex 0000000..d5ce72b\n--- /dev/null\n+++ b/t/t4043-diff-index-unique-abbrev.sh\n@@ -0,0 +1,35 @@\n+#!/bin/sh\n+\n+test_description='test unique sha1 abbreviation on \"index from..to\" line'\n+. ./test-lib.sh\n+\n+cat >expect_initial <<EOF\n+100644 blob 51d2738463ea4ca66f8691c91e33ce64b7d41bb1\tfoo\n+EOF\n+\n+cat >expect_update <<EOF\n+100644 blob 51d2738efb4ad8a1e40bed839ab8e116f0a15e47\tfoo\n+EOF\n+\n+test_expect_success 'setup' '\n+\techo 4827 > foo &&\n+\tgit add foo &&\n+\tgit commit -m \"initial\" &&\n+\tgit cat-file -p HEAD: > actual &&\n+\ttest_cmp expect_initial actual &&\n+\techo 11742 > foo &&\n+\tgit commit -a -m \"update\" &&\n+\tgit cat-file -p HEAD: > actual &&\n+\ttest_cmp expect_update actual\n+'\n+\n+cat >expect <<EOF\n+index 51d27384..51d2738e 100644\n+EOF\n+\n+test_expect_success 'diff does not produce ambiguous index line' '\n+\tgit diff HEAD^..HEAD | grep index > actual &&\n+\ttest_cmp expect actual\n+'\n+\n+test_done\n-- \n1.7.0.4\n"},{"id":"142581","messageId":"201005302158.40314.j6t@kdbg.org","threadId":"23945","inReplyTo":"201005301537.18039.johan@herland.net","subject":"Re: [PATCH] diff.c: Ensure \"index $from..$to\" line contains unambiguous SHA1s","fromName":"Johannes Sixt","fromEmail":"j6t@kdbg.org","sentAt":"2010-05-30T19:58:40Z","receivedAt":"2010-05-30T19:58:40Z","isPatch":true,"sender":{"key":"j6t@kdbg.org","avatar":"https://avatars.githubusercontent.com/u/14810926?v=4"},"body":"On Sonntag, 30. Mai 2010, Johan Herland wrote:\n> +cat >expect_initial <<EOF\n> +100644 blob 51d2738463ea4ca66f8691c91e33ce64b7d41bb1\tfoo\n> +EOF\n> +\n> +cat >expect_update <<EOF\n> +100644 blob 51d2738efb4ad8a1e40bed839ab8e116f0a15e47\tfoo\n> +EOF\n> +\n> +test_expect_success 'setup' '\n> +\techo 4827 > foo &&\n...\n> +\techo 11742 > foo &&\n\nHow the fscking hell did you find these two simple values that are an \nalmost-SHA1-collision? It's easier to hit the jackpot!?!\n\n-- Hannes\n"},{"id":"142596","messageId":"201005310123.23129.johan@herland.net","threadId":"23945","inReplyTo":"201005302158.40314.j6t@kdbg.org","subject":"Re: [PATCH] diff.c: Ensure \"index $from..$to\" line contains unambiguous SHA1s","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2010-05-30T23:23:22Z","receivedAt":"2010-05-30T23:23:22Z","isPatch":true,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"On Sunday 30 May 2010, Johannes Sixt wrote:\n> On Sonntag, 30. Mai 2010, Johan Herland wrote:\n> > +cat >expect_initial <<EOF\n> > +100644 blob 51d2738463ea4ca66f8691c91e33ce64b7d41bb1\tfoo\n> > +EOF\n> > +\n> > +cat >expect_update <<EOF\n> > +100644 blob 51d2738efb4ad8a1e40bed839ab8e116f0a15e47\tfoo\n> > +EOF\n> > +\n> > +test_expect_success 'setup' '\n> > +\techo 4827 > foo &&\n> \n> ...\n> \n> > +\techo 11742 > foo &&\n> \n> How the fscking hell did you find these two simple values that are an\n> almost-SHA1-collision? It's easier to hit the jackpot!?!\n\nFinding matches in the intial 7 hex chars (== 28 bits) of a SHA1 isn't \n_that_ hard. In this case, I used the attached hack/program[1], which found \nthe above values in <0.9 seconds, albeit you need ~1 GB free RAM to run \nit[2].\n\nThe program simply increments a 32-bit integer, and produces simple (but \nunique) blob objects (merely containing the 32-bit integer in decimal \nformat) for each integer, then hashes that blob object and stores the \noriginal integer in a reverse dictionary (actually, a 2^28-entry array), \nkeyed/indexed by the first 28 bits of the hash. Then, repeat until we find \nan integer whose blob hashes to the same location as a previous integer. \nSince we're using a 32-bit integer to generate inputs to a 2^28-entry array, \nwe're bound to find collisions long before the integer overflows.\n\nFTR, there are already several almost-collisions in real-world repos. I \nfirst found some in repos at my $DAYJOB, but there are also multiple cases \nin the git.git repo. The following command will list all 7-char ambiguities \nin a packfile:\n\n  git verify-pack -v $pack.idx | cut -c1-7 | uniq -d\n\n\nHave fun! :)\n\n...Johan\n\n\n[1]: Put the attached file in your git.git checkout and compile it with:\n\n  gcc -o find_sha_dup find_sha_dup.c block-sha1/sha1.c\n\n\n[2]: Double that for each additional bit you want to crack. I.e. cracking \nthe first 8 hex chars (== 32 bits) would require ~16 GB free RAM. I'm sure \nthere are more efficient ways of doing these things...\n\n-- \nJohan Herland, <johan@herland.net>\nwww.herland.net\n\n\n#include <stdint.h>\n#include <stdlib.h>\n#include <string.h>\n#include <stdio.h>\n\n#include \"block-sha1/sha1.h\"\n\n/* Find SHA1 collisions within the first 7 hex chars (== 28 bits) */\n\n#define num_entries (1 << 28) /* Need room for 2 ^ 28 entries */\nuint32_t a[num_entries];\n\nconst char *str (uint32_t x, uint32_t *len)\n{\n\t/* Generate unique, short, readable string from integer */\n#define buf_len 15\n\tstatic char buf[buf_len];\n\tint l;\n\tl = snprintf(buf, buf_len, \"%u\\n\", x);\n\tif (l >= buf_len || l < 0) {\n\t\tprintf(\"FAIL! l == %u\\n\", l);\n\t\texit(1);\n\t}\n\tif (len)\n\t\t*len = l;\n\treturn buf;\n}\n\nconst unsigned char *sha1 (const char *s, size_t len)\n{\n\tstatic blk_SHA_CTX sha1_ctx;\n\tstatic unsigned char sha1_result[20];\n\tchar hdr[32];\n\tint hdrlen;\n\n\t/* Make it look like a Git blob object */\n\thdrlen = sprintf(hdr, \"blob %lu\", len) + 1;\n\n\tblk_SHA1_Init(&sha1_ctx);\n\tblk_SHA1_Update(&sha1_ctx, hdr, hdrlen);\n\tblk_SHA1_Update(&sha1_ctx, s, len);\n\tblk_SHA1_Final(sha1_result, &sha1_ctx);\n\n\treturn sha1_result;\n}\n\nconst unsigned char *sha1_x (uint32_t x)\n{\n\tuint32_t len = 0;\n\tconst char *s = str(x, &len);\n\treturn sha1(s, len);\n}\n\nuint32_t a_index (const unsigned char *h)\n{\n\tuint32_t ret = (h[0] << 20) | (h[1] << 12) | (h[2] << 4) | (h[3] >> 4);\n\treturn ret;\n}\n\nchar *sha1_to_hex(const unsigned char *sha1)\n{\n\tstatic char buffer[41];\n\tstatic const char hex[] = \"0123456789abcdef\";\n\tint i;\n\tchar *buf = buffer;\n\n\tfor (i = 0; i < 20; i++) {\n\t\tunsigned int val = *sha1++;\n\t\t*buf++ = hex[val >> 4];\n\t\t*buf++ = hex[val & 0xf];\n\t}\n\t*buf = '\\0';\n\n\treturn buffer;\n}\n\nint main (void)\n{\n\tuint32_t x = 0, i;\n\n\tmemset(a, 0xff, num_entries * sizeof(uint32_t));\n\n\twhile (x != 0xffffffff) {\n\t\ti = a_index(sha1_x(x));\n\t\tif (a[i] == 0xffffffff) {\n\t\t\ta[i] = x++;\n\t\t\tcontinue;\n\t\t}\n\n\t\t/* Found collision! */\n\t\tuint32_t y = a[i];\n\t\tprintf(\"Found collision between entries %u and %u\\n\", y, x);\n\t\tprintf(\"\\t %u == '%s' => %s\\n\", y, str(y, NULL), sha1_to_hex(sha1_x(y)));\n\t\tprintf(\"\\t %u == '%s' => %s\\n\", x, str(x, NULL), sha1_to_hex(sha1_x(x)));\n\t\treturn 1;\n\t}\n\n\treturn 0;\n}\n"}]}