{"thread":{"id":"28720","subject":"[IGNORETHIS/PATCH] Choosing the sha1 prefix of your commits","startedAt":"2011-10-19T18:03:24Z","lastAt":"2011-10-25T22:35:04Z","messageCount":24,"participants":["Ævar Arnfjörð Bjarmason","Jeff King","Jonathan Nieder","Kyle Moffett","Junio C Hamano","Nguyen Thai Ngoc Duy","Mikael Magnusson","Ted Ts'o","Elijah Newren","Drew Northup"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"178004","messageId":"CACBZZX5PqYa0uWiGgs952rk2cy+QRCU95kF63qzSi3fKK-YrCQ@mail.gmail.com","threadId":"28720","inReplyTo":null,"subject":"[IGNORETHIS/PATCH] Choosing the sha1 prefix of your commits","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2011-10-19T18:03:24Z","receivedAt":"2011-10-19T18:03:24Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"You do not need to read this. Really, stop now.\n\nThis is quick hack I wrote just before leaving work to show that I\ncould indeed push patches to our main repository starting with\n31337. Names hidden to protect the innocent.\n\nWith a quick call to getenv() i'll be easy to supply a prefix with an\nenvironment variable, so you can have d00dbabe, deadbeef, b00b\netc. commits as time allows.\n\n    < cow-orker-1> avar: what do I have to do to have all my\n                            commit ids begin with 31337?\n    < cow-orker-2> cow-orker-1: just figure out SHA1 collision\n    < cow-orker-2> well with MD5 it is \"easy\" to have\n                   same-prefix collisions, so you can\n                   append junk that will be ignored or\n                   have no effect, and have the same MD5\n                   as the shorter version\n    <@avar> It actually wouldn't be too hard to make all your commits\nbegin with 31337\n    <@avar> I might patch my git client to do that\n    <@avar> Basically the sha1 is a function of the commit object /\nmessage / top-level tree\n    <@avar> and any compliant git client ignores headers it doesn't know about\n    <@avar> so you can just add a header \"lulz %d\"\n    <@avar> where %d is a number you keep incrementing until your\nresulting sha1 happens to begin with 31337\n    <@avar> 31337 is a 5 character hex string, and 16^5/2 = 524288\n    <@avar> so you'd on average have to generate half a million\ncommits before you'd get the desired results\n    <@avar> which would slow down git somewhat at commit time, but not\nmuch more than using svn :)\n    < cow-orker-2> enjoy your 3MB commits\n    < cow-orker-2> ah you can do that on the same header\n    <@avar> yes\n    < cow-orker-2> thanks, you just ruined my evening\n    [...]\n    <@avar> Also you don't have to waste your evening, I've implemented this\n    < cow-orker-1> \\o/\n    < cow-orker-3> hurry up and make a commit, already\n    < cow-orker-3> [img-mj-popcorn.gif]\n    <@avar> victory is mine: 313375d995e6f8b7773c6ed1ee165e5a9e15690b !\n\nThis is how you use it:\n\n    $ time ~/g/git/git-commit -F /tmp/commit-message\n    Try 0/4000000 to get a 1337 commit =\n33d86a5a13ce07914a38ead3a517e391df0cc8c2\n    Try 100000/4000000 to get a 1337 commit =\n058e7663f54a3dd85e2c5a88cebf221ff7c25889\n    Try 200000/4000000 to get a 1337 commit =\n78839302cf449d088db1df5eb81f9116cbce55d0\n    Try 300000/4000000 to get a 1337 commit =\nf0af0cbe91d0ba8903085e2f867246095e6fb957\n    Try 400000/4000000 to get a 1337 commit =\n2068605f90321558e97ae5a083f63475ae2075ea\n    Try 500000/4000000 to get a 1337 commit =\nf8b4e2acd14ab111fd7957956368d181596bc6ef\n    Try 600000/4000000 to get a 1337 commit =\n3a479ab83d969f9b5638481445506036d1e1db46\n    Try 700000/4000000 to get a 1337 commit =\n29b98585b44c02e59240c1d8a1956ae434b3543f\n    Try 800000/4000000 to get a 1337 commit =\n8749e31c40200554b3758313cada1a3f596b0230\n    Try 900000/4000000 to get a 1337 commit =\n3fb2e617db95db8c027fba686c3f75eaa1b7f880\n    commit id = 313375d995e6f8b7773c6ed1ee165e5a9e15690b\n    [trunk 313375d] <censored>\n     <censored>\n\n    real    1m15.389s\n    user    0m45.969s\n    sys     0m29.368s\n\nWhich in just over a minute will generate, in my case:\n\n    $ git show --pretty=raw 313375d995e6f8b7773c6ed1ee165e5a9e15690b | head -n 7\n    commit 313375d995e6f8b7773c6ed1ee165e5a9e15690b\n    tree c9bebc99c05dfe61cccf02ebdf442945c8ff8b3c\n    parent 0dce2d45a79d26a593f0e12301cdfeb7eb23c17a\n    author Ævar Arnfjörð Bjarmason <avar@example.com> <censored> <censored>\n    committer Ævar Arnfjörð Bjarmason <avar@example.com> <censored> <censored>\n    lulz 697889\n\nAnd this is the evil one-off code for this:\n\n    diff --git a/commit.c b/commit.c\n    index 73b7e00..71d1605 100644\n    --- a/commit.c\n    +++ b/commit.c\n    @@ -853,2 +853,4 @@ int commit_tree(const char *msg, unsigned char *tree,\n            int encoding_is_utf8;\n    +       int try;\n    +       int tries = 4000000;\n            struct strbuf buffer;\n    @@ -857,2 +859,5 @@ int commit_tree(const char *msg, unsigned char *tree,\n\n    +       struct commit_list *parents_ptr = parents;\n    +\n    +       for (try = 0; try < tries; try++) {\n            /* Not having i18n.commitencoding is the same as having utf-8 */\n    @@ -872,3 +877,2 @@ int commit_tree(const char *msg, unsigned char *tree,\n                            sha1_to_hex(parents->item->object.sha1));\n    -               free(parents);\n                    parents = next;\n    @@ -876,2 +880,4 @@ int commit_tree(const char *msg, unsigned char *tree,\n\n    +               parents = parents_ptr;\n    +\n            /* Person/date information */\n    @@ -883,2 +889,4 @@ int commit_tree(const char *msg, unsigned char *tree,\n                    strbuf_addf(&buffer, \"encoding %s\\n\", git_commit_encoding);\n    +\n    +               strbuf_addf(&buffer, \"lulz %d\\n\", try);\n            strbuf_addch(&buffer, '\\n');\n    @@ -893,3 +901,21 @@ int commit_tree(const char *msg, unsigned char *tree,\n            result = write_sha1_file(buffer.buf, buffer.len, commit_type, ret);\n    +\n    +               if (result) {\n    +                       die(\"failed to write commit object\");\n    +               } else {\n    +                       if (strncmp(sha1_to_hex(ret), \"31337\", 5) == 0) {\n    +                               printf(\"commit id = %s\\n\",\nsha1_to_hex(ret));\n    +                               goto done;\n    +                       } else {\n    +                               if (try % 100000 == 0) {\n    +                                       fprintf(stderr, \"Try %d/%d\nto get a 1337 commit = %s\\n\", try, tries, sha1_to_hex(ret));\n    +                               }\n    +                               unlink_or_warn(sha1_file_name(ret));\n    +                       }\n            strbuf_release(&buffer);\n    +               }\n    +       }\n    +       done:\n    +       strbuf_release(&buffer);\n    +\n            return result;\n\nThere's nothing new or novel about this. I just thought it would be\nnice to share it. Someone asked me if having a \"lulz\" header wouldn't\nbreak things, but since we introduced the \"encoding\" header a while\nback clients have learned to ignore unknown headers, so it doesn't.\n\nWhich is why we can discuss e.g. adding GPG headers without worrying\nabout breaking everything.\n\nI also think it's interesting that we seemingly don't have (in my\nbrief search, maybe I missed it) an API for writing a complete commit\nobject into a strbuf, so I had to write a lot of commit objects to\ndisk, and keep unlinking the unacceptable candidates so the repository\nwouldn't balloon in size.\n"},{"id":"178006","messageId":"20111019190114.GA4670@sigill.intra.peff.net","threadId":"28720","inReplyTo":"CACBZZX5PqYa0uWiGgs952rk2cy+QRCU95kF63qzSi3fKK-YrCQ@mail.gmail.com","subject":"Re: [IGNORETHIS/PATCH] Choosing the sha1 prefix of your commits","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-10-19T19:01:14Z","receivedAt":"2011-10-19T19:01:14Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Oct 19, 2011 at 08:03:24PM +0200, Ævar Arnfjörð Bjarmason wrote:\n\n> This is quick hack I wrote just before leaving work to show that I\n> could indeed push patches to our main repository starting with\n> 31337. Names hidden to protect the innocent.\n\nClever and amusing.\n\n> Which in just over a minute will generate, in my case:\n> \n>     $ git show --pretty=raw 313375d995e6f8b7773c6ed1ee165e5a9e15690b | head -n 7\n>     commit 313375d995e6f8b7773c6ed1ee165e5a9e15690b\n>     tree c9bebc99c05dfe61cccf02ebdf442945c8ff8b3c\n>     parent 0dce2d45a79d26a593f0e12301cdfeb7eb23c17a\n>     author Ævar Arnfjörð Bjarmason <avar@example.com> <censored> <censored>\n>     committer Ævar Arnfjörð Bjarmason <avar@example.com> <censored> <censored>\n>     lulz 697889\n\nNice header name.\n\n> I also think it's interesting that we seemingly don't have (in my\n> brief search, maybe I missed it) an API for writing a complete commit\n> object into a strbuf, so I had to write a lot of commit objects to\n> disk, and keep unlinking the unacceptable candidates so the repository\n> wouldn't balloon in size.\n\nCalculating an object sha1 is pretty straightforward. I think you could\njust tack the \"commit <size>\" header in front of the commit strbuf, and\nsha1 that, and then just send the \"winner\" to actually be written.\n\nToo bad it won't work in an append only way.  The internal state of sha1\nafter a certain set of bytes is deterministic, so you could do something\nlike:\n\n  void leetify_object(struct strbuf *data)\n  {\n          SHA_CTX base, guess;\n          int len = data->len;\n          int i = 0;\n\n          /* come up with a base internal state representing\n           * the commit */\n          SHA1_Init(&base);\n          SHA1_Update(&base, data->buf, data->len);\n\n          while (1) {\n                  char append[64];\n                  int n = snprintf(append, sizeof(append),\n                                   \"x-lulz-by: %d\\n\", i);\n                  unsigned char sha1[20];\n\n                  /* and then from that state, see what the sha1 would\n                   * be if we add our few new bytes */\n                  memcpy(&guess, &base, sizeof(guess));\n                  SHA1_Update(&guess, append, n);\n                  SHA1_Final(sha1, &guess);\n\n                  /* did we pick a winner? */\n                  if (sha1[0] == 0x31 &&\n                      sha1[1] == 0x33 &&\n                      &sha1[2] & 0xf0) == 0x70) {\n                            strbuf_addstr(data, append);\n                            return;\n                  }\n\n                  i++;\n          }\n  }\n\nThere are two problems with this:\n\n  1. The x-lulz-by header is visible in the commit message. I think you\n     can actually get around this by appending a NUL character, and \"git\n     log\" and friends will stop processing the commit message there.\n\n  2. The object header will actually have the length of the object at\n     the beginning. So as your lulz number grows, the length of the\n     object will change, and invalidate your earlier sha1. You could get\n     around this by using a fixed-size guess (e.g., start with 20 bytes\n     of zeroes, and then just keep incrementing).\n\n-Peff\n"},{"id":"178008","messageId":"20111019193834.GA14168@sigill.intra.peff.net","threadId":"28720","inReplyTo":"20111019190114.GA4670@sigill.intra.peff.net","subject":"Re: [IGNORETHIS/PATCH] Choosing the sha1 prefix of your commits","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-10-19T19:38:34Z","receivedAt":"2011-10-19T19:38:34Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Oct 19, 2011 at 03:01:14PM -0400, Jeff King wrote:\n\n> Too bad it won't work in an append only way.  The internal state of sha1\n> after a certain set of bytes is deterministic, so you could do something\n> like:\n\nOK, here's a patch which does that. It's way faster:\n\n  $ git init\n  $ time for i in `seq 1 10`; do\n      echo $i >file\n      git add file\n      git commit -q -m $i\n    done\n  real    0m1.212s\n  user    0m1.132s\n  sys     0m0.028s\n\nSo that's about .12 seconds per commit. Without my patch, it's about .01\nseconds. So you waste a tenth of a second generating the collision. Not\ntoo bad.\n\nAnd the result:\n\n  $ git log --oneline\n  31337a1 10\n  313376b 9\n  3133782 8\n  31337cf 7\n  313377a 6\n  313374b 5\n  31337b1 4\n  31337a3 3\n  3133703 2\n  3133706 1\n\nAnd nothing shows up in the body, because git truncates at the NUL we\nadded:\n\n  $ git show\n  commit 31337a1093af2d97eb2e6c08b261c2946395fdd3\n  Author: Jeff King <peff@peff.net>\n  Date:   Wed Oct 19 15:34:00 2011 -0400\n\n      10\n\n  diff --git a/file b/file\n  index ec63514..f599e28 100644\n  --- a/file\n  +++ b/file\n  @@ -1 +1 @@\n  -9\n  +10\n\nIt also parameterizes the desired sha1, so you could easily find hashes\nending in 31337, or any other pattern. Or add \"git commit\n--collide=31337\".\n\n---\ndiff --git a/commit.c b/commit.c\nindex 73b7e00..c478752 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -840,6 +840,57 @@ struct commit_list *reduce_heads(struct commit_list *heads)\n \treturn result;\n }\n \n+static unsigned char elite_want[20] = { 0x31, 0x33, 0x70 };\n+static unsigned char elite_mask[20] = { 0xff, 0xff, 0xf0 };\n+\n+static inline int sha1_match_mask(unsigned char *sha1,\n+\t\t\t\t  unsigned char *want,\n+\t\t\t\t  unsigned char *mask)\n+{\n+\tint i;\n+\tfor (i = 0; i < 20; i++)\n+\t\tif ((want[i] & mask[i]) != (sha1[i] & mask[i]))\n+\t\t    return 0;\n+\treturn 1;\n+}\n+\n+static void collide_commit(struct strbuf *data,\n+\t\t\t   unsigned char want[20],\n+\t\t\t   unsigned char mask[20])\n+{\n+\tstatic const char terminator[] = { 0 };\n+\tchar header[32];\n+\tint header_len;\n+\tunsigned int lulz;\n+\tSHA_CTX base;\n+\n+\theader_len = snprintf(header, sizeof(header),\n+\t\t\t      \"commit %lu\",\n+\t\t\t      data->len + 1 + sizeof(lulz)) + 1;\n+\tSHA1_Init(&base);\n+\tSHA1_Update(&base, header, header_len);\n+\tSHA1_Update(&base, data->buf, data->len);\n+\tSHA1_Update(&base, terminator, sizeof(terminator));\n+\n+\tlulz = 0;\n+\tdo {\n+\t\tSHA_CTX guess;\n+\t\tunsigned char sha1[20];\n+\n+\t\tmemcpy(&guess, &base, sizeof(guess));\n+\t\tSHA1_Update(&guess, &lulz, sizeof(lulz));\n+\t\tSHA1_Final(sha1, &guess);\n+\n+\t\tif (sha1_match_mask(sha1, want, mask)) {\n+\t\t\tstrbuf_add(data, terminator, sizeof(terminator));\n+\t\t\tstrbuf_add(data, &lulz, sizeof(lulz));\n+\t\t\treturn;\n+\t\t}\n+\n+\t\tlulz++;\n+\t} while (1);\n+}\n+\n static const char commit_utf8_warn[] =\n \"Warning: commit message does not conform to UTF-8.\\n\"\n \"You may want to amend it after fixing the message, or set the config\\n\"\n@@ -890,6 +941,8 @@ int commit_tree(const char *msg, unsigned char *tree,\n \tif (encoding_is_utf8 && !is_utf8(buffer.buf))\n \t\tfprintf(stderr, commit_utf8_warn);\n \n+\tcollide_commit(&buffer, elite_want, elite_mask);\n+\n \tresult = write_sha1_file(buffer.buf, buffer.len, commit_type, ret);\n \tstrbuf_release(&buffer);\n \treturn result;\n"},{"id":"178052","messageId":"20111019220931.GA8322@elie.hsd1.il.comcast.net","threadId":"28720","inReplyTo":"CACBZZX5PqYa0uWiGgs952rk2cy+QRCU95kF63qzSi3fKK-YrCQ@mail.gmail.com","subject":"Re: [IGNORETHIS/PATCH] Choosing the sha1 prefix of your commits","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2011-10-19T22:09:31Z","receivedAt":"2011-10-19T22:09:31Z","isPatch":true,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Ævar Arnfjörð Bjarmason wrote:\n\n> Someone asked me if having a \"lulz\" header wouldn't\n> break things, but since we introduced the \"encoding\" header a while\n> back clients have learned to ignore unknown headers, so it doesn't.\n>\n> Which is why we can discuss e.g. adding GPG headers without worrying\n> about breaking everything.\n\nJust for the record (and I think you understood this already): it is\nnot quite so simple.  Clients are allowed to assume that no \"unknown\"\nheader lines will appear before any of the known fields.  A future git\nversion could even assume that, say, a\n\n\tlength-of-remainder-of-header\n\nfield appears before any lines after encoding and the GPG stuff.\n\nSo it would definitely be frowned upon to add new lines to that part\nof the commit object without at least discussing it on this list.\nJeff mentioned one way to get your lulz without violating that\nconstraint. ;-)\n\nhttp://thread.gmane.org/gmane.comp.version-control.git/138848/focus=138921\n"},{"id":"178064","messageId":"20111020025149.GA31549@sigill.intra.peff.net","threadId":"28720","inReplyTo":"20111019193834.GA14168@sigill.intra.peff.net","subject":"Re: [IGNORETHIS/PATCH] Choosing the sha1 prefix of your commits","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-10-20T02:51:49Z","receivedAt":"2011-10-20T02:51:49Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Oct 19, 2011 at 03:38:34PM -0400, Jeff King wrote:\n\n> It also parameterizes the desired sha1, so you could easily find hashes\n> ending in 31337, or any other pattern. Or add \"git commit\n> --collide=31337\".\n\nI couldn't resist:\n\n  $ git commit -q -m foo --collide=deadbeef &&\n    git rev-list -1 HEAD\n  deadbeefdbd6e62a2185606a4fad653e22509b56\n\nYou can also do:\n\n  $ SHA1=0000000000000000000000000000000000031337\n  $ MASK=00000000000000000000000000000000000fffff\n  $ git commit -q -m foo --collide=$SHA1/$MASK &&\n    git rev-list -1 HEAD\n  ea49af84db92ed0d2bc3ed13810f5990e7c31337\n\nKeep in mind that each hex character you add increases the search space\nby a factor of 16. deadbeef took about 70 seconds to find on my machine.\nI'm tempted to look for \"3133700..0031337\", but it would probably\ntake about 4 hours.\n\nPatch is below.\n\n-Peff\n\n---\ndiff --git a/builtin/commit.c b/builtin/commit.c\nindex c46f2d1..734a7ab 100644\n--- a/builtin/commit.c\n+++ b/builtin/commit.c\n@@ -105,6 +105,10 @@\n static const char *only_include_assumed;\n static struct strbuf message;\n \n+static int collide;\n+static unsigned char collide_sha1[20];\n+static unsigned char collide_mask[20];\n+\n static int null_termination;\n static enum {\n \tSTATUS_FORMAT_LONG,\n@@ -125,6 +129,52 @@ static int opt_parse_m(const struct option *opt, const char *arg, int unset)\n \treturn 0;\n }\n \n+static int parse_partial_sha1(const char *s, unsigned char sha1[20])\n+{\n+\tunsigned int i;\n+\n+\thashclr(sha1);\n+\n+\tfor (i = 0; i < 40 && s[i]; i++) {\n+\t\tunsigned int v = hexval(s[i]);\n+\t\tif (v & ~0xf)\n+\t\t\tbreak;\n+\t\tif (!(i & 1))\n+\t\t\tv <<= 4;\n+\t\tsha1[i/2] |= v;\n+\t}\n+\treturn i;\n+}\n+\n+static void fill_sha1_mask(int n, unsigned char mask[20]) {\n+\tint i;\n+\n+\thashclr(mask);\n+\tfor (i = 0; i < n/2; i++)\n+\t\tmask[i] = 0xff;\n+\tif (n & 1)\n+\t\tmask[i] = 0xf0;\n+}\n+\n+static int opt_parse_collide(const struct option *opt, const char *arg,\n+\t\t\t     int unset)\n+{\n+\tif (unset)\n+\t\tcollide = 0;\n+\telse {\n+\t\tint n = parse_partial_sha1(arg, collide_sha1);\n+\t\tif (!arg[n])\n+\t\t\tfill_sha1_mask(n, collide_mask);\n+\t\telse if (arg[n] == '/')\n+\t\t\tparse_partial_sha1(arg + n + 1, collide_mask);\n+\t\telse\n+\t\t\tdie(\"invalid --collide sha1: %s\", arg);\n+\t\tcollide = 1;\n+\t}\n+\treturn 0;\n+}\n+\n+\n static struct option builtin_commit_options[] = {\n \tOPT__QUIET(&quiet, \"suppress summary after successful commit\"),\n \tOPT__VERBOSE(&verbose, \"show diff in commit message template\"),\n@@ -144,6 +194,7 @@ static int opt_parse_m(const struct option *opt, const char *arg, int unset)\n \tOPT_BOOLEAN('e', \"edit\", &edit_flag, \"force edit of commit\"),\n \tOPT_STRING(0, \"cleanup\", &cleanup_arg, \"default\", \"how to strip spaces and #comments from message\"),\n \tOPT_BOOLEAN(0, \"status\", &include_status, \"include status in commit message template\"),\n+\tOPT_CALLBACK(0, \"collide\", NULL, \"sha1[/mask]\", \"choose commit sha1 like <sha1>\", opt_parse_collide),\n \t/* end commit message options */\n \n \tOPT_GROUP(\"Commit contents options\"),\n@@ -1483,8 +1534,9 @@ int cmd_commit(int argc, const char **argv, const char *prefix)\n \t\texit(1);\n \t}\n \n-\tif (commit_tree(sb.buf, active_cache_tree->sha1, parents, sha1,\n-\t\t\tauthor_ident.buf)) {\n+\tif (commit_tree_collide(sb.buf, active_cache_tree->sha1, parents, sha1,\n+\t\t\t\tauthor_ident.buf,\n+\t\t\t\tcollide ? collide_sha1 : NULL, collide_mask)) {\n \t\trollback_index_files();\n \t\tdie(_(\"failed to write commit object\"));\n \t}\ndiff --git a/commit.c b/commit.c\nindex 73b7e00..24ddccd 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -840,6 +840,54 @@ struct commit_list *reduce_heads(struct commit_list *heads)\n \treturn result;\n }\n \n+static inline int sha1_match_mask(const unsigned char *sha1,\n+\t\t\t\t  const unsigned char *want,\n+\t\t\t\t  const unsigned char *mask)\n+{\n+\tint i;\n+\tfor (i = 0; i < 20; i++)\n+\t\tif ((want[i] & mask[i]) != (sha1[i] & mask[i]))\n+\t\t    return 0;\n+\treturn 1;\n+}\n+\n+static void collide_commit(struct strbuf *data,\n+\t\t\t   const unsigned char *want,\n+\t\t\t   const unsigned char *mask)\n+{\n+\tstatic const char terminator[] = { 0 };\n+\tchar header[32];\n+\tint header_len;\n+\tunsigned int lulz;\n+\tSHA_CTX base;\n+\n+\theader_len = snprintf(header, sizeof(header),\n+\t\t\t      \"commit %lu\",\n+\t\t\t      data->len + 1 + sizeof(lulz)) + 1;\n+\tSHA1_Init(&base);\n+\tSHA1_Update(&base, header, header_len);\n+\tSHA1_Update(&base, data->buf, data->len);\n+\tSHA1_Update(&base, terminator, sizeof(terminator));\n+\n+\tlulz = 0;\n+\tdo {\n+\t\tSHA_CTX guess;\n+\t\tunsigned char sha1[20];\n+\n+\t\tmemcpy(&guess, &base, sizeof(guess));\n+\t\tSHA1_Update(&guess, &lulz, sizeof(lulz));\n+\t\tSHA1_Final(sha1, &guess);\n+\n+\t\tif (sha1_match_mask(sha1, want, mask)) {\n+\t\t\tstrbuf_add(data, terminator, sizeof(terminator));\n+\t\t\tstrbuf_add(data, &lulz, sizeof(lulz));\n+\t\t\treturn;\n+\t\t}\n+\n+\t\tlulz++;\n+\t} while (1);\n+}\n+\n static const char commit_utf8_warn[] =\n \"Warning: commit message does not conform to UTF-8.\\n\"\n \"You may want to amend it after fixing the message, or set the config\\n\"\n@@ -849,6 +897,15 @@ int commit_tree(const char *msg, unsigned char *tree,\n \t\tstruct commit_list *parents, unsigned char *ret,\n \t\tconst char *author)\n {\n+\treturn commit_tree_collide(msg, tree, parents, ret, author,\n+\t\t\t\t   NULL, NULL);\n+}\n+\n+int commit_tree_collide(const char *msg, unsigned char *tree,\n+\t\t\tstruct commit_list *parents, unsigned char *ret,\n+\t\t\tconst char *author, const unsigned char *want,\n+\t\t\tconst unsigned char *mask)\n+{\n \tint result;\n \tint encoding_is_utf8;\n \tstruct strbuf buffer;\n@@ -890,6 +947,9 @@ int commit_tree(const char *msg, unsigned char *tree,\n \tif (encoding_is_utf8 && !is_utf8(buffer.buf))\n \t\tfprintf(stderr, commit_utf8_warn);\n \n+\tif (want && mask)\n+\t\tcollide_commit(&buffer, want, mask);\n+\n \tresult = write_sha1_file(buffer.buf, buffer.len, commit_type, ret);\n \tstrbuf_release(&buffer);\n \treturn result;\ndiff --git a/commit.h b/commit.h\nindex 009b113..337dcbd 100644\n--- a/commit.h\n+++ b/commit.h\n@@ -184,5 +184,9 @@ static inline int single_parent(struct commit *commit)\n extern int commit_tree(const char *msg, unsigned char *tree,\n \t\tstruct commit_list *parents, unsigned char *ret,\n \t\tconst char *author);\n+extern int commit_tree_collide(const char *msg, unsigned char *tree,\n+\t\t\t       struct commit_list *parents, unsigned char *ret,\n+\t\t\t       const char *author, const unsigned char *sha1,\n+\t\t\t       const unsigned char *mask);\n \n #endif /* COMMIT_H */\n"},{"id":"178065","messageId":"CAGZ=bqK2oVPxW3mm-WHMd1+KSiPquympJyhRqLWr1F=G74p+BA@mail.gmail.com","threadId":"28720","inReplyTo":"20111020025149.GA31549@sigill.intra.peff.net","subject":"Re: [IGNORETHIS/PATCH] Choosing the sha1 prefix of your commits","fromName":"Kyle Moffett","fromEmail":"kyle@moffetthome.net","sentAt":"2011-10-20T04:15:03Z","receivedAt":"2011-10-20T04:15:03Z","isPatch":true,"sender":{"key":"kyle@moffetthome.net","avatar":null},"body":"On Wed, Oct 19, 2011 at 22:51, Jeff King <peff@peff.net> wrote:\n> Keep in mind that each hex character you add increases the search space\n> by a factor of 16. deadbeef took about 70 seconds to find on my machine.\n> I'm tempted to look for \"3133700..0031337\", but it would probably\n> take about 4 hours.\n\nHeh, there's one other practical downside I can think of...\n\nIf you create a bunch of commits with the same 8-hex-character prefix\nthen suddenly the \"git describe\" logic for using the first 7 commit ID\ncharacters gets a whole lot less useful.\n\nCheers,\nKyle Moffett\n\n-- \nCurious about my work on the Debian powerpcspe port?\nI'm keeping a blog here: http://pureperl.blogspot.com/\n"},{"id":"178066","messageId":"20111020042559.GA5466@sigill.intra.peff.net","threadId":"28720","inReplyTo":"CAGZ=bqK2oVPxW3mm-WHMd1+KSiPquympJyhRqLWr1F=G74p+BA@mail.gmail.com","subject":"Re: [IGNORETHIS/PATCH] Choosing the sha1 prefix of your commits","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-10-20T04:25:59Z","receivedAt":"2011-10-20T04:25:59Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Oct 20, 2011 at 12:15:03AM -0400, Kyle Moffett wrote:\n\n> On Wed, Oct 19, 2011 at 22:51, Jeff King <peff@peff.net> wrote:\n> > Keep in mind that each hex character you add increases the search space\n> > by a factor of 16. deadbeef took about 70 seconds to find on my machine.\n> > I'm tempted to look for \"3133700..0031337\", but it would probably\n> > take about 4 hours.\n> \n> Heh, there's one other practical downside I can think of...\n> \n> If you create a bunch of commits with the same 8-hex-character prefix\n> then suddenly the \"git describe\" logic for using the first 7 commit ID\n> characters gets a whole lot less useful.\n\nActually, git will generally find a unique abbreviation among all of\nyour objects when using abbreviated sha1s, so you'll just get longer\nabbreviations. Of course, it is only unique at the time of generation,\nso new objects may make it ambiguous. Which is why the default minimum\nis 7, not 1.  But of course with this trick you've effectively removed\nall of the entropy from those initial 7 characters, and you effectively\nonly have 1 or 2 non-uniform characters.\n\nSo yeah, it is worse.  But really...spending millions of CPU cycles to\nget a preimage collision with the partial sha1, and hack-ishly embedding\nrandom crap after a NUL in every commit message, and _this_ is your\ncomplaint? ;)\n\n-Peff\n"},{"id":"178067","messageId":"7vzkgw9tjw.fsf@alter.siamese.dyndns.org","threadId":"28720","inReplyTo":"CAGZ=bqK2oVPxW3mm-WHMd1+KSiPquympJyhRqLWr1F=G74p+BA@mail.gmail.com","subject":"Re: [IGNORETHIS/PATCH] Choosing the sha1 prefix of your commits","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-10-20T04:27:15Z","receivedAt":"2011-10-20T04:27:15Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Kyle Moffett <kyle@moffetthome.net> writes:\n\n> Heh, there's one other practical downside I can think of...\n>\n> If you create a bunch of commits with the same 8-hex-character prefix\n> then suddenly the \"git describe\" logic for using the first 7 commit ID\n> characters gets a whole lot less useful.\n\nIn the sense that you need to cut and paste a lot more characters, you are\ncorrect that it would make it less useful, but if you are talking about\nuniqueness, you are mistaken.\n\nThe rule is not \"using the first 7 hexdigits\", but is \"using as many\nhexdigits to make assure uniqueness, but use at least 7\".\n"},{"id":"178068","messageId":"7vvcrk9td7.fsf@alter.siamese.dyndns.org","threadId":"28720","inReplyTo":"20111019193834.GA14168@sigill.intra.peff.net","subject":"Re: [IGNORETHIS/PATCH] Choosing the sha1 prefix of your commits","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-10-20T04:31:16Z","receivedAt":"2011-10-20T04:31:16Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> And nothing shows up in the body, because git truncates at the NUL we\n> added:\n>\n>   $ git show\n>   commit 31337a1093af2d97eb2e6c08b261c2946395fdd3\n>   Author: Jeff King <peff@peff.net>\n>   Date:   Wed Oct 19 15:34:00 2011 -0400\n>\n>       10\n>\n>   diff --git a/file b/file\n\nBut you cannot hide from \"cat-file commit\" ;-)\n\nWith the recent push to more (perceived) security, it may probably make\nsense to teach \"log\" family commands to quote-show ^@ and what is behind\nin their output by default, perhaps with an option to turn it off.\n"},{"id":"178069","messageId":"CAGZ=bq+y1Q1KKUwyBJmWMoAWn_+M+CBNVBh-UBtLttqN6_gjew@mail.gmail.com","threadId":"28720","inReplyTo":"7vzkgw9tjw.fsf@alter.siamese.dyndns.org","subject":"Re: [IGNORETHIS/PATCH] Choosing the sha1 prefix of your commits","fromName":"Kyle Moffett","fromEmail":"kyle@moffetthome.net","sentAt":"2011-10-20T04:32:55Z","receivedAt":"2011-10-20T04:32:55Z","isPatch":true,"sender":{"key":"kyle@moffetthome.net","avatar":null},"body":"On Thu, Oct 20, 2011 at 00:27, Junio C Hamano <gitster@pobox.com> wrote:\n> Kyle Moffett <kyle@moffetthome.net> writes:\n>\n>> Heh, there's one other practical downside I can think of...\n>>\n>> If you create a bunch of commits with the same 8-hex-character prefix\n>> then suddenly the \"git describe\" logic for using the first 7 commit ID\n>> characters gets a whole lot less useful.\n>\n> In the sense that you need to cut and paste a lot more characters, you are\n> correct that it would make it less useful, but if you are talking about\n> uniqueness, you are mistaken.\n>\n> The rule is not \"using the first 7 hexdigits\", but is \"using as many\n> hexdigits to make assure uniqueness, but use at least 7\".\n\nWell, yes, but if you generate some 10 commits with the same\n7-character prefix, run \"git describe\", and then generate another\nseveral with the same prefix... Chances are the previously-unique\noutput of \"git describe\" is no longer unique.\n\nAlso, even if you do use enough characters for it to be reliably\nunique, it's not really an abbreviation if your commit description is\n\"v2.0.3-42-gdeadbeef04a69f\", with that many characters you might as\nwell just paste the whole SHA1 sum.\n\nWith all that said, it is a very clever (and ugly) hack :-D.  Kudos!\n\nCheers,\nKyle Moffett\n\n-- \nCurious about my work on the Debian powerpcspe port?\nI'm keeping a blog here: http://pureperl.blogspot.com/\n"},{"id":"178070","messageId":"20111020043448.GA7628@sigill.intra.peff.net","threadId":"28720","inReplyTo":"7vvcrk9td7.fsf@alter.siamese.dyndns.org","subject":"Re: [IGNORETHIS/PATCH] Choosing the sha1 prefix of your commits","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-10-20T04:34:48Z","receivedAt":"2011-10-20T04:34:48Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Oct 19, 2011 at 09:31:16PM -0700, Junio C Hamano wrote:\n\n> Jeff King <peff@peff.net> writes:\n> \n> > And nothing shows up in the body, because git truncates at the NUL we\n> > added:\n> >\n> >   $ git show\n> >   commit 31337a1093af2d97eb2e6c08b261c2946395fdd3\n> >   Author: Jeff King <peff@peff.net>\n> >   Date:   Wed Oct 19 15:34:00 2011 -0400\n> >\n> >       10\n> >\n> >   diff --git a/file b/file\n> \n> But you cannot hide from \"cat-file commit\" ;-)\n\nYes. The implementation is a horrible hack, second only in grossness to\nthe original idea. :)\n\n> With the recent push to more (perceived) security, it may probably make\n> sense to teach \"log\" family commands to quote-show ^@ and what is behind\n> in their output by default, perhaps with an option to turn it off.\n\nAgreed. Having hidden cruft makes birthday collision attacks easier (or\nit will, if sha1 ever gets broken to that point).  Unfortunately, there\nis a _ton_ of code which assumes that commit messages are\nNUL-terminated, as they always have been since e871b64 (2005-05-25).\n\n-Peff\n"},{"id":"178073","messageId":"7vr5289mlu.fsf@alter.siamese.dyndns.org","threadId":"28720","inReplyTo":"20111020043448.GA7628@sigill.intra.peff.net","subject":"Re: [IGNORETHIS/PATCH] Choosing the sha1 prefix of your commits","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-10-20T06:57:17Z","receivedAt":"2011-10-20T06:57:17Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> Agreed. Having hidden cruft makes birthday collision attacks easier (or\n> it will, if sha1 ever gets broken to that point).  Unfortunately, there\n> is a _ton_ of code which assumes that commit messages are\n> NUL-terminated, as they always have been since e871b64 (2005-05-25).\n\nI think that commit is irrelevant, as long as read_sha1_file() returns the\ncontents as <ptr,len> pair, which has been the case forever. It's just the\nmatter of propagating the length back up the callchain.\n\nA naïve implementation to add \"len\" member to struct commit would increase\nthe size of the in-core commit object by sizeof(unsigned long), which we\nmay want to avoid. Traversals that care nothing but the topology of the\nhistory would have to waste that memory and these things tend to add up\n(8-byte ulong * 250k commits = 2MB).\n\nPerhaps change the type of \"buf\" member in struct commit to a pointer to a\n<ptr,len> pair, or something? Or perhaps a few megabytes wasted between\nfriends we do not care much about?\n"},{"id":"178075","messageId":"20111020071356.GA14945@sigill.intra.peff.net","threadId":"28720","inReplyTo":"7vr5289mlu.fsf@alter.siamese.dyndns.org","subject":"Re: [IGNORETHIS/PATCH] Choosing the sha1 prefix of your commits","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-10-20T07:13:56Z","receivedAt":"2011-10-20T07:13:56Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Oct 19, 2011 at 11:57:17PM -0700, Junio C Hamano wrote:\n\n> Jeff King <peff@peff.net> writes:\n> \n> > Agreed. Having hidden cruft makes birthday collision attacks easier (or\n> > it will, if sha1 ever gets broken to that point).  Unfortunately, there\n> > is a _ton_ of code which assumes that commit messages are\n> > NUL-terminated, as they always have been since e871b64 (2005-05-25).\n> \n> I think that commit is irrelevant, as long as read_sha1_file() returns the\n> contents as <ptr,len> pair, which has been the case forever. It's just the\n> matter of propagating the length back up the callchain.\n\nIt's not that the commit is bad or the source of problems. My point is\nthat the assumption that commit messages are NUL-terminated has been\nthere for a really long time, so there are lots of spots in the code\nthat sloppily run string functions on them. Every one of those needs to\nbe found and fixed (e.g., I remember seeing this in\nfor-each-ref.c:find_subpos recently).\n\nIt's not impossible, of course, or even really that hard. It's just a\ngiant pain, and I wonder if the effort is worth it.\n\n> A naïve implementation to add \"len\" member to struct commit would increase\n> the size of the in-core commit object by sizeof(unsigned long), which we\n> may want to avoid. Traversals that care nothing but the topology of the\n> history would have to waste that memory and these things tend to add up\n> (8-byte ulong * 250k commits = 2MB).\n> \n> Perhaps change the type of \"buf\" member in struct commit to a pointer to a\n> <ptr,len> pair, or something? Or perhaps a few megabytes wasted between\n> friends we do not care much about?\n\nI think you'd have to convert the struct (even if not every piece of\ncode is converted to use it) and profile.\n\n-Peff\n"},{"id":"178076","messageId":"CACsJy8BObsN3=uQ=RA-Am4X+WPYnP87mrmY+MbotDL9-VFb3TA@mail.gmail.com","threadId":"28720","inReplyTo":"7vr5289mlu.fsf@alter.siamese.dyndns.org","subject":"Re: [IGNORETHIS/PATCH] Choosing the sha1 prefix of your commits","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2011-10-20T07:27:44Z","receivedAt":"2011-10-20T07:27:44Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Thu, Oct 20, 2011 at 5:57 PM, Junio C Hamano <gitster@pobox.com> wrote:\n> Jeff King <peff@peff.net> writes:\n>\n>> Agreed. Having hidden cruft makes birthday collision attacks easier (or\n>> it will, if sha1 ever gets broken to that point).  Unfortunately, there\n>> is a _ton_ of code which assumes that commit messages are\n>> NUL-terminated, as they always have been since e871b64 (2005-05-25).\n>\n> I think that commit is irrelevant, as long as read_sha1_file() returns the\n> contents as <ptr,len> pair, which has been the case forever. It's just the\n> matter of propagating the length back up the callchain.\n>\n> A naïve implementation to add \"len\" member to struct commit would increase\n> the size of the in-core commit object by sizeof(unsigned long), which we\n> may want to avoid. Traversals that care nothing but the topology of the\n> history would have to waste that memory and these things tend to add up\n> (8-byte ulong * 250k commits = 2MB).\n\nOr write commit_length(struct commit *c) that calculates SHA-1 from\nc->buf and checks against c->object.sha1. If it does not match,\nconsider NUL part of the message and move to the next NUL. This\nfunction would be expensive so we may not call frequently though.\n\nOr store length in ((int*)c->buf)[-1].\n-- \nDuy\n"},{"id":"178082","messageId":"CACsJy8B7CJ3VO-UKCym2kgfOOPadL25gt2sxApk95nKoWVk2yQ@mail.gmail.com","threadId":"28720","inReplyTo":"7vvcrk9td7.fsf@alter.siamese.dyndns.org","subject":"Re: [IGNORETHIS/PATCH] Choosing the sha1 prefix of your commits","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2011-10-20T09:14:56Z","receivedAt":"2011-10-20T09:14:56Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Thu, Oct 20, 2011 at 3:31 PM, Junio C Hamano <gitster@pobox.com> wrote:\n> Jeff King <peff@peff.net> writes:\n>\n>> And nothing shows up in the body, because git truncates at the NUL we\n>> added:\n>>\n>>   $ git show\n>>   commit 31337a1093af2d97eb2e6c08b261c2946395fdd3\n>>   Author: Jeff King <peff@peff.net>\n>>   Date:   Wed Oct 19 15:34:00 2011 -0400\n>>\n>>       10\n>>\n>>   diff --git a/file b/file\n>\n> But you cannot hide from \"cat-file commit\" ;-)\n>\n> With the recent push to more (perceived) security, it may probably make\n> sense to teach \"log\" family commands to quote-show ^@ and what is behind\n> in their output by default, perhaps with an option to turn it off.\n\nWhat about NUL in file name in tree objects? Suppose the original tree\nhas an entry named \"goodthing\". With luck, they might be able to\ncreate a new tree object with the entry renamed to \"evil\\x001234\" that\nhas the same SHA-1. Could that possibly cause any problems?\n-- \nDuy\n"},{"id":"178083","messageId":"CAHYJk3QV8QckbOM76QfqQfTsyOtk+nvfhCped+W3t60JfCfouA@mail.gmail.com","threadId":"28720","inReplyTo":"20111019190114.GA4670@sigill.intra.peff.net","subject":"Re: [IGNORETHIS/PATCH] Choosing the sha1 prefix of your commits","fromName":"Mikael Magnusson","fromEmail":"mikachu@gmail.com","sentAt":"2011-10-20T09:38:44Z","receivedAt":"2011-10-20T09:38:44Z","isPatch":true,"sender":{"key":"mikachu@gmail.com","avatar":null},"body":"On 19 October 2011 21:01, Jeff King <peff@peff.net> wrote:\n> On Wed, Oct 19, 2011 at 08:03:24PM +0200, Ævar Arnfjörð Bjarmason wrote:\n>\n>> This is quick hack I wrote just before leaving work to show that I\n>> could indeed push patches to our main repository starting with\n>> 31337. Names hidden to protect the innocent.\n>\n> Clever and amusing.\n>\n>> Which in just over a minute will generate, in my case:\n>>\n>>     $ git show --pretty=raw 313375d995e6f8b7773c6ed1ee165e5a9e15690b | head -n 7\n>>     commit 313375d995e6f8b7773c6ed1ee165e5a9e15690b\n>>     tree c9bebc99c05dfe61cccf02ebdf442945c8ff8b3c\n>>     parent 0dce2d45a79d26a593f0e12301cdfeb7eb23c17a\n>>     author Ævar Arnfjörð Bjarmason <avar@example.com> <censored> <censored>\n>>     committer Ævar Arnfjörð Bjarmason <avar@example.com> <censored> <censored>\n>>     lulz 697889\n>\n> Nice header name.\n\nIf you don't mind waiting, you could just increase the timestamps\nuntil you get the desired collision. (If you still want them to be\ncorrect, trying 4000000 times would about 6 weeks though :).\n\n-- \nMikael Magnusson\n"},{"id":"178084","messageId":"20111020131454.GB7464@thunk.org","threadId":"28720","inReplyTo":"20111020071356.GA14945@sigill.intra.peff.net","subject":"Re: [IGNORETHIS/PATCH] Choosing the sha1 prefix of your commits","fromName":"Ted Ts'o","fromEmail":"tytso@mit.edu","sentAt":"2011-10-20T13:14:55Z","receivedAt":"2011-10-20T13:14:55Z","isPatch":true,"sender":{"key":"tytso@mit.edu","avatar":"https://avatars.githubusercontent.com/u/51416?v=4"},"body":"On Thu, Oct 20, 2011 at 03:13:56AM -0400, Jeff King wrote:\n> It's not that the commit is bad or the source of problems. My point is\n> that the assumption that commit messages are NUL-terminated has been\n> there for a really long time, so there are lots of spots in the code\n> that sloppily run string functions on them. Every one of those needs to\n> be found and fixed (e.g., I remember seeing this in\n> for-each-ref.c:find_subpos recently).\n\nAnother possibility is to warn if the commit messages are not NULL\nterminated.  Note though that if we're really worried about a bad guy\ntrying to attack us with a hash collision, he/she could always use\n\"invisible\" non-printing characters in the commit message, and/or just\nmess with one or both of the timestamps.  The more bits and more\ndegrees of flexibility the attacker has, the easier it would be, of\ncourse.  In the grand scheme of things it's not clear to me how big of\na deal this would be.\n\nIf people were really concerned it would probably be easier to use\nbackup crypto checksum using something stronger (say, SHA-2 or the\neventual SHA-3).  Just store the backup checksums of the parent\ncommitments in some backwardly compatible place that old git\nimplementations wouldn't look (say, after the NULL in the commit\nmessage if there isn't a better place :-), and new implementations\nwould know to generate the checksums, and old implementations would\nignore it.\n\nThat way, if anyone *does* figure out a way to generate real hash\ncollisions with SHA1 of objects that look almost completely identical\nto the original objects, new implementations that would gradually make\ntheir way out to the field could verify the SHA-2 (or SHA-3, when it\nis announced, assuming that we the tag the checksums with a type\nidentifier) checksums and notice that they are not correct.\n\nMaybe someone's already thought of this, but the cool thing about this\nidea is it's a way that we can upgrade to a stronger hash algorithm\nwithout needing a flag day due to some kind of incompatible format\nchange; we keep using SHA1 for the user-visible hash, since it's fine\nmodulo intentional attacks, and then use a hidden, backup checksum\nwhich can be checked either all the time, or if that turns out to be a\ncomputational burden, at some configurable random percent of the time.\n\nAnyway, just a thought....\n\n\t      \t      \t     \t\t   \t  - Ted\n"},{"id":"178085","messageId":"CABPp-BGUghrwUv4YHcSXeaLaYoUG=7oS7a5OhR3MYs0W6E5Bow@mail.gmail.com","threadId":"28720","inReplyTo":"CAHYJk3QV8QckbOM76QfqQfTsyOtk+nvfhCped+W3t60JfCfouA@mail.gmail.com","subject":"Re: [IGNORETHIS/PATCH] Choosing the sha1 prefix of your commits","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2011-10-20T13:44:31Z","receivedAt":"2011-10-20T13:44:31Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Thu, Oct 20, 2011 at 3:38 AM, Mikael Magnusson <mikachu@gmail.com> wrote:\n>> On Wed, Oct 19, 2011 at 08:03:24PM +0200, Ævar Arnfjörð Bjarmason wrote:\n>>\n>>> This is quick hack I wrote just before leaving work to show that I\n>>> could indeed push patches to our main repository starting with\n>>> 31337. Names hidden to protect the innocent.\n>>\n> If you don't mind waiting, you could just increase the timestamps\n> until you get the desired collision. (If you still want them to be\n> correct, trying 4000000 times would about 6 weeks though :).\n\nBut the nice thing is that we have both author and committer dates to\ntwiddle with, meaning that if we need 4000000 different values to try\nthen it's only 2000 for each of those two dates, i.e. we only need to\nbe willing to let those dates float by about half an hour.\n"},{"id":"178090","messageId":"20111020154406.GA16114@sigill.intra.peff.net","threadId":"28720","inReplyTo":"CACsJy8B7CJ3VO-UKCym2kgfOOPadL25gt2sxApk95nKoWVk2yQ@mail.gmail.com","subject":"Re: [IGNORETHIS/PATCH] Choosing the sha1 prefix of your commits","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-10-20T15:44:06Z","receivedAt":"2011-10-20T15:44:06Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Oct 20, 2011 at 08:14:56PM +1100, Nguyen Thai Ngoc Duy wrote:\n\n> > But you cannot hide from \"cat-file commit\" ;-)\n> >\n> > With the recent push to more (perceived) security, it may probably make\n> > sense to teach \"log\" family commands to quote-show ^@ and what is behind\n> > in their output by default, perhaps with an option to turn it off.\n> \n> What about NUL in file name in tree objects? Suppose the original tree\n> has an entry named \"goodthing\". With luck, they might be able to\n> create a new tree object with the entry renamed to \"evil\\x001234\" that\n> has the same SHA-1. Could that possibly cause any problems?\n\nNUL is already meaningful in a tree object; it is the end of the\nfilename. So after the NUL, we will consider the next 20 bytes to be\nsha1, and then after that, the mode of the next file entry.\n\n-Peff\n"},{"id":"178091","messageId":"20111020155611.GB16114@sigill.intra.peff.net","threadId":"28720","inReplyTo":"20111020131454.GB7464@thunk.org","subject":"Re: [IGNORETHIS/PATCH] Choosing the sha1 prefix of your commits","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-10-20T15:56:11Z","receivedAt":"2011-10-20T15:56:11Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Oct 20, 2011 at 09:14:55AM -0400, Ted Ts'o wrote:\n\n> Another possibility is to warn if the commit messages are not NULL\n> terminated.\n\nA minor nit, but it's not whether they are terminated with NUL, but\nrather whether they have embedded NUL. But yeah, this could maybe just\nbe something fsck looks for.\n\n> Note though that if we're really worried about a bad guy trying to\n> attack us with a hash collision, he/she could always use \"invisible\"\n> non-printing characters in the commit message, and/or just mess with\n> one or both of the timestamps.  The more bits and more degrees of\n> flexibility the attacker has, the easier it would be, of course.  In\n> the grand scheme of things it's not clear to me how big of a deal this\n> would be.\n\nGood point. Append-only attacks are cheaper, because you can avoid doing\nmost of the hash computation on each iteration (like my patch does). But\nthat's not a big-O speedup, it just makes the constant smaller.  So you\ncould assume that any feasible appending attack would probably become\nfeasible for recomputing the full hash eventually.\n\n> If people were really concerned it would probably be easier to use\n> backup crypto checksum using something stronger (say, SHA-2 or the\n> eventual SHA-3).  Just store the backup checksums of the parent\n> commitments in some backwardly compatible place that old git\n> implementations wouldn't look (say, after the NULL in the commit\n> message if there isn't a better place :-), and new implementations\n> would know to generate the checksums, and old implementations would\n> ignore it.\n\nYeah, if birthday attacks against sha1 become possible, the sensible\nthing is probably not to worry too much about the file format, but to\nuse a better hash.\n\nCommits can hide extra hashes in a header pretty easily. But what about\ntrees and blobs? I don't think there's any \"ignored\" space in either\none.\n\n-Peff\n"},{"id":"178096","messageId":"7vehy7a4sf.fsf_-_@alter.siamese.dyndns.org","threadId":"28720","inReplyTo":"20111020071356.GA14945@sigill.intra.peff.net","subject":"Re* [IGNORETHIS/PATCH] Choosing the sha1 prefix of your commits","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-10-20T18:36:48Z","receivedAt":"2011-10-20T18:36:48Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> It's not that the commit is bad or the source of problems. My point is\n> that the assumption that commit messages are NUL-terminated has been\n> there for a really long time, so there are lots of spots in the code\n> that sloppily run string functions on them. Every one of those needs to\n> be found and fixed (e.g., I remember seeing this in\n> for-each-ref.c:find_subpos recently).\n>\n> It's not impossible, of course, or even really that hard. It's just a\n> giant pain, and I wonder if the effort is worth it.\n\nTrue.\n\nIt probably is not worth it for most applications, but this fix-up to a\nfairly recent one is worth doing, I would suspect.\n\n-- >8 --\nSubject: parse_signed_commit: really use the entire commit log message\n\n... even beyond the first NUL in the buffer, when checking the commit\nagainst the detached signature in the header.\n\nSigned-off-by: Junio C Hamano <gitster@pobox.com>\n---\n commit.c                 |   11 +++++------\n t/t7510-signed-commit.sh |   21 ++++++++++++++++-----\n 2 files changed, 21 insertions(+), 11 deletions(-)\n\ndiff --git a/commit.c b/commit.c\nindex 93045a2..6ec49fa 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -854,28 +854,27 @@ int parse_signed_commit(const unsigned char *sha1,\n \tunsigned long size;\n \tenum object_type type;\n \tchar *buffer = read_sha1_file(sha1, &type, &size);\n-\tint in_header, saw_signature = -1;\n+\tint saw_signature = -1;\n \tchar *line;\n \n \tif (!buffer || type != OBJ_COMMIT)\n \t\tgoto cleanup;\n \n \tline = buffer;\n-\tin_header = 1;\n \tsaw_signature = 0;\n-\twhile (*line) {\n+\twhile (line < buffer + size) {\n \t\tchar *next = strchrnul(line, '\\n');\n \t\tif (*next)\n \t\t\tnext++;\n-\t\tif (in_header && !prefixcmp(line, gpg_sig_header)) {\n+\t\tif (!prefixcmp(line, gpg_sig_header)) {\n \t\t\tconst char *sig = line + gpg_sig_header_len;\n \t\t\tstrbuf_add(signature, sig, next - sig);\n \t\t\tsaw_signature = 1;\n \t\t} else {\n+\t\t\tif (*line == '\\n')\n+\t\t\t\tnext = buffer + size; /* dump the whole remainder */\n \t\t\tstrbuf_add(payload, line, next - line);\n \t\t}\n-\t\tif (*line == '\\n')\n-\t\t\tin_header = 0;\n \t\tline = next;\n \t}\n  cleanup:\ndiff --git a/t/t7510-signed-commit.sh b/t/t7510-signed-commit.sh\nindex 5c7475d..30401ce 100755\n--- a/t/t7510-signed-commit.sh\n+++ b/t/t7510-signed-commit.sh\n@@ -50,11 +50,22 @@ test_expect_success GPG 'show signatures' '\n \n test_expect_success GPG 'detect fudged signature' '\n \tgit cat-file commit master >raw &&\n-\tsed -e \"s/fourth signed/4th forged/\" raw >forged &&\n-\tgit hash-object -w -t commit forged >forged.commit &&\n-\tgit show --pretty=short --show-signature $(cat forged.commit) >actual &&\n-\tgrep \"BAD signature from\" actual &&\n-\t! grep \"Good signature from\" actual\n+\n+\tsed -e \"s/fourth signed/4th forged/\" raw >forged1 &&\n+\tgit hash-object -w -t commit forged1 >forged1.commit &&\n+\tgit show --pretty=short --show-signature $(cat forged1.commit) >actual1 &&\n+\tgrep \"BAD signature from\" actual1 &&\n+\t! grep \"Good signature from\" actual1\n+'\n+\n+test_expect_success GPG 'detect fudged signature with NUL' '\n+\tgit cat-file commit master >raw &&\n+\tcat raw >forged2 &&\n+\techo Qwik | tr \"Q\" \"\\000\" >>forged2 &&\n+\tgit hash-object -w -t commit forged2 >forged2.commit &&\n+\tgit show --pretty=short --show-signature $(cat forged2.commit) >actual2 &&\n+\tgrep \"BAD signature from\" actual2 &&\n+\t! grep \"Good signature from\" actual2\n '\n \n test_done\n"},{"id":"178099","messageId":"20111020190052.GA25360@sigill.intra.peff.net","threadId":"28720","inReplyTo":"7vehy7a4sf.fsf_-_@alter.siamese.dyndns.org","subject":"Re: Re* [IGNORETHIS/PATCH] Choosing the sha1 prefix of your commits","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-10-20T19:00:52Z","receivedAt":"2011-10-20T19:00:52Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Oct 20, 2011 at 11:36:48AM -0700, Junio C Hamano wrote:\n\n> It probably is not worth it for most applications, but this fix-up to a\n> fairly recent one is worth doing, I would suspect.\n> \n> -- >8 --\n> Subject: parse_signed_commit: really use the entire commit log message\n>\n> ... even beyond the first NUL in the buffer, when checking the commit\n> against the detached signature in the header.\n\nYeah, that is worth fixing, I think. It's one thing to be a little lazy\nin pretty-printing for \"git log\", but I think signature verification\nshould be more careful.\n\nPatch itself looks sane to me. There's still some use of str-like\nfunctions, but they would prevent us from even seeing the signature\nheaders in the first place, so anything with a NUL that high is just\nbroken and crappy.\n\nI didn't check, but I wonder if fsck does/should check that there is a\nproper end-of-header blank line before we hit any NUL.\n\n-Peff\n"},{"id":"178246","messageId":"20111024204737.GA25574@sigill.intra.peff.net","threadId":"28720","inReplyTo":"20111020025149.GA31549@sigill.intra.peff.net","subject":"Re: [IGNORETHIS/PATCH] Choosing the sha1 prefix of your commits","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-10-24T20:47:38Z","receivedAt":"2011-10-24T20:47:38Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Oct 19, 2011 at 10:51:49PM -0400, Jeff King wrote:\n\n> I couldn't resist:\n> \n>   $ git commit -q -m foo --collide=deadbeef &&\n>     git rev-list -1 HEAD\n>   deadbeefdbd6e62a2185606a4fad653e22509b56\n\nHere's a followup with a few cleanups:\n\n  1. It will actually finish and report an error if we fail to find a\n     commit after ULONG_MAX tries. On 64-bit machines this is unlikely,\n     but it might be possible on a 32-bit machine if you have a lot of\n     patience.\n\n  2. It uses git_SHA* now, so it will build properly against BLK_SHA1 if\n     NO_OPENSSL is defined.\n\n  3. It will split the the collision-finding work across online_cpus()\n     threads.\n\nSomebody else suggested farming the work out to a GPU. I'll leave that\nas an exercise to the reader.\n\n-Peff\n\n---\n builtin/commit.c |   56 ++++++++++++++++++-\n commit.c         |  165 ++++++++++++++++++++++++++++++++++++++++++++++++++++++\n commit.h         |    4 +\n 3 files changed, 223 insertions(+), 2 deletions(-)\n\ndiff --git a/builtin/commit.c b/builtin/commit.c\nindex c46f2d1..734a7ab 100644\n--- a/builtin/commit.c\n+++ b/builtin/commit.c\n@@ -105,6 +105,10 @@\n static const char *only_include_assumed;\n static struct strbuf message;\n \n+static int collide;\n+static unsigned char collide_sha1[20];\n+static unsigned char collide_mask[20];\n+\n static int null_termination;\n static enum {\n \tSTATUS_FORMAT_LONG,\n@@ -125,6 +129,52 @@ static int opt_parse_m(const struct option *opt, const char *arg, int unset)\n \treturn 0;\n }\n \n+static int parse_partial_sha1(const char *s, unsigned char sha1[20])\n+{\n+\tunsigned int i;\n+\n+\thashclr(sha1);\n+\n+\tfor (i = 0; i < 40 && s[i]; i++) {\n+\t\tunsigned int v = hexval(s[i]);\n+\t\tif (v & ~0xf)\n+\t\t\tbreak;\n+\t\tif (!(i & 1))\n+\t\t\tv <<= 4;\n+\t\tsha1[i/2] |= v;\n+\t}\n+\treturn i;\n+}\n+\n+static void fill_sha1_mask(int n, unsigned char mask[20]) {\n+\tint i;\n+\n+\thashclr(mask);\n+\tfor (i = 0; i < n/2; i++)\n+\t\tmask[i] = 0xff;\n+\tif (n & 1)\n+\t\tmask[i] = 0xf0;\n+}\n+\n+static int opt_parse_collide(const struct option *opt, const char *arg,\n+\t\t\t     int unset)\n+{\n+\tif (unset)\n+\t\tcollide = 0;\n+\telse {\n+\t\tint n = parse_partial_sha1(arg, collide_sha1);\n+\t\tif (!arg[n])\n+\t\t\tfill_sha1_mask(n, collide_mask);\n+\t\telse if (arg[n] == '/')\n+\t\t\tparse_partial_sha1(arg + n + 1, collide_mask);\n+\t\telse\n+\t\t\tdie(\"invalid --collide sha1: %s\", arg);\n+\t\tcollide = 1;\n+\t}\n+\treturn 0;\n+}\n+\n+\n static struct option builtin_commit_options[] = {\n \tOPT__QUIET(&quiet, \"suppress summary after successful commit\"),\n \tOPT__VERBOSE(&verbose, \"show diff in commit message template\"),\n@@ -144,6 +194,7 @@ static int opt_parse_m(const struct option *opt, const char *arg, int unset)\n \tOPT_BOOLEAN('e', \"edit\", &edit_flag, \"force edit of commit\"),\n \tOPT_STRING(0, \"cleanup\", &cleanup_arg, \"default\", \"how to strip spaces and #comments from message\"),\n \tOPT_BOOLEAN(0, \"status\", &include_status, \"include status in commit message template\"),\n+\tOPT_CALLBACK(0, \"collide\", NULL, \"sha1[/mask]\", \"choose commit sha1 like <sha1>\", opt_parse_collide),\n \t/* end commit message options */\n \n \tOPT_GROUP(\"Commit contents options\"),\n@@ -1483,8 +1534,9 @@ int cmd_commit(int argc, const char **argv, const char *prefix)\n \t\texit(1);\n \t}\n \n-\tif (commit_tree(sb.buf, active_cache_tree->sha1, parents, sha1,\n-\t\t\tauthor_ident.buf)) {\n+\tif (commit_tree_collide(sb.buf, active_cache_tree->sha1, parents, sha1,\n+\t\t\t\tauthor_ident.buf,\n+\t\t\t\tcollide ? collide_sha1 : NULL, collide_mask)) {\n \t\trollback_index_files();\n \t\tdie(_(\"failed to write commit object\"));\n \t}\ndiff --git a/commit.c b/commit.c\nindex 73b7e00..7beea9b 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -6,6 +6,7 @@\n #include \"diff.h\"\n #include \"revision.h\"\n #include \"notes.h\"\n+#include \"thread-utils.h\"\n \n int save_commit_buffer = 1;\n \n@@ -840,6 +841,158 @@ struct commit_list *reduce_heads(struct commit_list *heads)\n \treturn result;\n }\n \n+static inline int sha1_match_mask(const unsigned char *sha1,\n+\t\t\t\t  const unsigned char *want,\n+\t\t\t\t  const unsigned char *mask)\n+{\n+\tint i;\n+\tfor (i = 0; i < 20; i++)\n+\t\tif ((want[i] & mask[i]) != (sha1[i] & mask[i]))\n+\t\t    return 0;\n+\treturn 1;\n+}\n+\n+static unsigned long find_collision(const unsigned char *want,\n+\t\t\t\t    const unsigned char *mask,\n+\t\t\t\t    const git_SHA_CTX *base,\n+\t\t\t\t    unsigned long start,\n+\t\t\t\t    unsigned long end)\n+{\n+\tunsigned long lulz;\n+\n+\tfor (lulz = start; lulz < end; lulz++) {\n+\t\tgit_SHA_CTX guess;\n+\t\tunsigned char sha1[20];\n+\n+\t\tmemcpy(&guess, base, sizeof(guess));\n+\t\tgit_SHA1_Update(&guess, &lulz, sizeof(lulz));\n+\t\tgit_SHA1_Final(sha1, &guess);\n+\n+\t\tif (sha1_match_mask(sha1, want, mask))\n+\t\t\treturn lulz;\n+\t}\n+\treturn end;\n+}\n+\n+#ifndef NO_PTHREADS\n+struct collision_thread_data {\n+\tconst unsigned char *want;\n+\tconst unsigned char *mask;\n+\tconst git_SHA_CTX *base;\n+\tunsigned long start;\n+\tunsigned long end;\n+\n+\tpthread_mutex_t *mutex;\n+\tpthread_cond_t *cond;\n+\tint *threads_alive;\n+\tunsigned long *answer;\n+};\n+\n+static void *collision_thread(void *vdata)\n+{\n+\tstruct collision_thread_data *d = vdata;\n+\tunsigned long r;\n+\n+\tpthread_setcanceltype(PTHREAD_CANCEL_ASYNCHRONOUS, NULL);\n+\n+\tr = find_collision(d->want, d->mask, d->base,\n+\t\t\t   d->start, d->end);\n+\n+\tpthread_mutex_lock(d->mutex);\n+\n+\t(*d->threads_alive)--;\n+\tif (r != d->end) {\n+\t\t*d->answer = r;\n+\t\tpthread_cond_signal(d->cond);\n+\t}\n+\telse {\n+\t\t/* If we failed to find it, and we're the last thread,\n+\t\t * wake up the parent so it can report failure. */\n+\t\tif (!*d->threads_alive)\n+\t\t\tpthread_cond_signal(d->cond);\n+\t}\n+\n+\tpthread_mutex_unlock(d->mutex);\n+\treturn NULL;\n+}\n+\n+static unsigned long find_collision_threaded(int nthreads,\n+\t\t\t\t\t     const unsigned char *want,\n+\t\t\t\t\t     const unsigned char *mask,\n+\t\t\t\t\t     const git_SHA_CTX *base)\n+{\n+\tint i;\n+\tpthread_t *threads;\n+\tstruct collision_thread_data *data;\n+\tpthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;\n+\tpthread_cond_t cond = PTHREAD_COND_INITIALIZER;\n+\tint threads_alive = nthreads;\n+\tunsigned long ret = ULONG_MAX;\n+\n+\tthreads = xmalloc(nthreads * sizeof(*threads));\n+\tdata = xmalloc(nthreads * sizeof(*data));\n+\n+\tpthread_mutex_lock(&mutex);\n+\n+\tfor (i = 0; i < nthreads; i++) {\n+\t\tdata[i].want = want;\n+\t\tdata[i].mask = mask;\n+\t\tdata[i].base = base;\n+\t\tdata[i].start = i * (ULONG_MAX / nthreads);\n+\t\tdata[i].end = (i+1) * (ULONG_MAX / nthreads);\n+\t\tdata[i].mutex = &mutex;\n+\t\tdata[i].cond = &cond;\n+\t\tdata[i].answer = &ret;\n+\t\tdata[i].threads_alive = &threads_alive;\n+\t\tpthread_create(&threads[i], NULL, collision_thread, &data[i]);\n+\t}\n+\n+\tpthread_cond_wait(&cond, &mutex);\n+\n+\tfor (i = 0; i < nthreads; i++) {\n+\t\tpthread_cancel(threads[i]);\n+\t\tpthread_join(threads[i], NULL);\n+\t}\n+\n+\tfree(threads);\n+\tfree(data);\n+\treturn ret;\n+}\n+#endif /* NO_PTHREADS */\n+\n+\n+static void collide_commit(struct strbuf *data,\n+\t\t\t   const unsigned char *want,\n+\t\t\t   const unsigned char *mask)\n+{\n+\tstatic const char terminator[] = { 0 };\n+\tchar header[32];\n+\tint header_len;\n+\tunsigned long lulz;\n+\tgit_SHA_CTX base;\n+\n+\theader_len = snprintf(header, sizeof(header),\n+\t\t\t      \"commit %lu\",\n+\t\t\t      data->len + 1 + sizeof(lulz)) + 1;\n+\tgit_SHA1_Init(&base);\n+\tgit_SHA1_Update(&base, header, header_len);\n+\tgit_SHA1_Update(&base, data->buf, data->len);\n+\tgit_SHA1_Update(&base, terminator, sizeof(terminator));\n+\n+#ifdef NO_PTHREADS\n+\tlulz = find_collision(want, mask, &base, 0, ULONG_MAX);\n+#else\n+\tlulz = find_collision_threaded(online_cpus(), want, mask, &base);\n+#endif /* NO_PTHREADS */\n+\n+\tif (lulz != ULONG_MAX) {\n+\t\tstrbuf_add(data, terminator, sizeof(terminator));\n+\t\tstrbuf_add(data, &lulz, sizeof(lulz));\n+\t}\n+\telse\n+\t\twarning(\"sorry, I couldn't find a collision!\");\n+}\n+\n static const char commit_utf8_warn[] =\n \"Warning: commit message does not conform to UTF-8.\\n\"\n \"You may want to amend it after fixing the message, or set the config\\n\"\n@@ -849,6 +1002,15 @@ int commit_tree(const char *msg, unsigned char *tree,\n \t\tstruct commit_list *parents, unsigned char *ret,\n \t\tconst char *author)\n {\n+\treturn commit_tree_collide(msg, tree, parents, ret, author,\n+\t\t\t\t   NULL, NULL);\n+}\n+\n+int commit_tree_collide(const char *msg, unsigned char *tree,\n+\t\t\tstruct commit_list *parents, unsigned char *ret,\n+\t\t\tconst char *author, const unsigned char *want,\n+\t\t\tconst unsigned char *mask)\n+{\n \tint result;\n \tint encoding_is_utf8;\n \tstruct strbuf buffer;\n@@ -890,6 +1052,9 @@ int commit_tree(const char *msg, unsigned char *tree,\n \tif (encoding_is_utf8 && !is_utf8(buffer.buf))\n \t\tfprintf(stderr, commit_utf8_warn);\n \n+\tif (want && mask)\n+\t\tcollide_commit(&buffer, want, mask);\n+\n \tresult = write_sha1_file(buffer.buf, buffer.len, commit_type, ret);\n \tstrbuf_release(&buffer);\n \treturn result;\ndiff --git a/commit.h b/commit.h\nindex 009b113..337dcbd 100644\n--- a/commit.h\n+++ b/commit.h\n@@ -184,5 +184,9 @@ static inline int single_parent(struct commit *commit)\n extern int commit_tree(const char *msg, unsigned char *tree,\n \t\tstruct commit_list *parents, unsigned char *ret,\n \t\tconst char *author);\n+extern int commit_tree_collide(const char *msg, unsigned char *tree,\n+\t\t\t       struct commit_list *parents, unsigned char *ret,\n+\t\t\t       const char *author, const unsigned char *sha1,\n+\t\t\t       const unsigned char *mask);\n \n #endif /* COMMIT_H */\n-- \n1.7.7.40.g1a72f\n"},{"id":"178299","messageId":"1319582104.10399.38.camel@drew-northup.unet.maine.edu","threadId":"28720","inReplyTo":"20111020155611.GB16114@sigill.intra.peff.net","subject":"Re: [IGNORETHIS/PATCH] Choosing the sha1 prefix of your commits","fromName":"Drew Northup","fromEmail":"drew.northup@maine.edu","sentAt":"2011-10-25T22:35:04Z","receivedAt":"2011-10-25T22:35:04Z","isPatch":true,"sender":{"key":"drew.northup@maine.edu","avatar":"https://avatars.githubusercontent.com/u/18331571?v=4"},"body":"\nOn Thu, 2011-10-20 at 11:56 -0400, Jeff King wrote:\n> On Thu, Oct 20, 2011 at 09:14:55AM -0400, Ted Ts'o wrote:\n> \n> > Another possibility is to warn if the commit messages are not NULL\n> > terminated.\n> \n> A minor nit, but it's not whether they are terminated with NUL, but\n> rather whether they have embedded NUL. But yeah, this could maybe just\n> be something fsck looks for.\n\nGod (or your deity of choice) forbid that anybody ever writes code that\nsaves raw UTF-16 as the commit message...\n\n-- \n-Drew Northup\n________________________________________________\n\"As opposed to vegetable or mineral error?\"\n-John Pescatore, SANS NewsBites Vol. 12 Num. 59\n"}]}