patchChoosing the sha1 prefix of your commits

You do not need to read this. Really, stop now.

This is quick hack I wrote just before leaving work to show that I
could indeed push patches to our main repository starting with
31337. Names hidden to protect the innocent.

With a quick call to getenv() i'll be easy to supply a prefix with an environment variable, so you can have d00dbabe, deadbeef, b00b etc. commits as time allows.

    < cow-orker-1> avar: what do I have to do to have all my
                            commit ids begin with 31337?
    < cow-orker-2> cow-orker-1: just figure out SHA1 collision
    < cow-orker-2> well with MD5 it is "easy" to have
                   same-prefix collisions, so you can
                   append junk that will be ignored or
                   have no effect, and have the same MD5
                   as the shorter version
    <@avar> It actually wouldn't be too hard to make all your commits
begin with 31337
    <@avar> I might patch my git client to do that
    <@avar> Basically the sha1 is a function of the commit object /
message / top-level tree
    <@avar> and any compliant git client ignores headers it doesn't know about
    <@avar> so you can just add a header "lulz %d"
    <@avar> where %d is a number you keep incrementing until your
resulting sha1 happens to begin with 31337
    <@avar> 31337 is a 5 character hex string, and 16^5/2 = 524288
    <@avar> so you'd on average have to generate half a million
commits before you'd get the desired results
    <@avar> which would slow down git somewhat at commit time, but not
much more than using svn :)
    < cow-orker-2> enjoy your 3MB commits
    < cow-orker-2> ah you can do that on the same header
    <@avar> yes
    < cow-orker-2> thanks, you just ruined my evening
    [...]
    <@avar> Also you don't have to waste your evening, I've implemented this
    < cow-orker-1> \o/
    < cow-orker-3> hurry up and make a commit, already
    < cow-orker-3> [img-mj-popcorn.gif]
    <@avar> victory is mine: 313375d995e6f8b7773c6ed1ee165e5a9e15690b !

This is how you use it:

    $ time ~/g/git/git-commit -F /tmp/commit-message
    Try 0/4000000 to get a 1337 commit =
33d86a5a13ce07914a38ead3a517e391df0cc8c2
    Try 100000/4000000 to get a 1337 commit =
058e7663f54a3dd85e2c5a88cebf221ff7c25889
    Try 200000/4000000 to get a 1337 commit =
78839302cf449d088db1df5eb81f9116cbce55d0
    Try 300000/4000000 to get a 1337 commit =
f0af0cbe91d0ba8903085e2f867246095e6fb957
    Try 400000/4000000 to get a 1337 commit =
2068605f90321558e97ae5a083f63475ae2075ea
    Try 500000/4000000 to get a 1337 commit =
f8b4e2acd14ab111fd7957956368d181596bc6ef
    Try 600000/4000000 to get a 1337 commit =
3a479ab83d969f9b5638481445506036d1e1db46
    Try 700000/4000000 to get a 1337 commit =
29b98585b44c02e59240c1d8a1956ae434b3543f
    Try 800000/4000000 to get a 1337 commit =
8749e31c40200554b3758313cada1a3f596b0230
    Try 900000/4000000 to get a 1337 commit =
3fb2e617db95db8c027fba686c3f75eaa1b7f880
    commit id = 313375d995e6f8b7773c6ed1ee165e5a9e15690b
    [trunk 313375d] <censored>
     <censored>

    real    1m15.389s
    user    0m45.969s
    sys     0m29.368s

Which in just over a minute will generate, in my case:

    $ git show --pretty=raw 313375d995e6f8b7773c6ed1ee165e5a9e15690b | head -n 7
    commit 313375d995e6f8b7773c6ed1ee165e5a9e15690b
    tree c9bebc99c05dfe61cccf02ebdf442945c8ff8b3c
    parent 0dce2d45a79d26a593f0e12301cdfeb7eb23c17a
    author Ævar Arnfjörð Bjarmason <avar@example.com> <censored> <censored>
    committer Ævar Arnfjörð Bjarmason <avar@example.com> <censored> <censored>
    lulz 697889

And this is the evil one-off code for this:

    diff --git a/commit.c b/commit.c
    index 73b7e00..71d1605 100644
    --- a/commit.c
    +++ b/commit.c
    @@ -853,2 +853,4 @@ int commit_tree(const char *msg, unsigned char *tree,
            int encoding_is_utf8;
    +       int try;
    +       int tries = 4000000;
            struct strbuf buffer;
    @@ -857,2 +859,5 @@ int commit_tree(const char *msg, unsigned char *tree,

    +       struct commit_list *parents_ptr = parents;
    +
    +       for (try = 0; try < tries; try++) {
            /* Not having i18n.commitencoding is the same as having utf-8 */
    @@ -872,3 +877,2 @@ int commit_tree(const char *msg, unsigned char *tree,
                            sha1_to_hex(parents->item->object.sha1));
    -               free(parents);
                    parents = next;
    @@ -876,2 +880,4 @@ int commit_tree(const char *msg, unsigned char *tree,

    +               parents = parents_ptr;
    +
            /* Person/date information */
    @@ -883,2 +889,4 @@ int commit_tree(const char *msg, unsigned char *tree,
                    strbuf_addf(&buffer, "encoding %s\n", git_commit_encoding);
    +
    +               strbuf_addf(&buffer, "lulz %d\n", try);
            strbuf_addch(&buffer, '\n');
    @@ -893,3 +901,21 @@ int commit_tree(const char *msg, unsigned char *tree,
            result = write_sha1_file(buffer.buf, buffer.len, commit_type, ret);
    +
    +               if (result) {
    +                       die("failed to write commit object");
    +               } else {
    +                       if (strncmp(sha1_to_hex(ret), "31337", 5) == 0) {
    +                               printf("commit id = %s\n",
sha1_to_hex(ret));
    +                               goto done;
    +                       } else {
    +                               if (try % 100000 == 0) {
    +                                       fprintf(stderr, "Try %d/%d
to get a 1337 commit = %s\n", try, tries, sha1_to_hex(ret));
    +                               }
    +                               unlink_or_warn(sha1_file_name(ret));
    +                       }
            strbuf_release(&buffer);
    +               }
    +       }
    +       done:
    +       strbuf_release(&buffer);
    +
            return result;

There's nothing new or novel about this. I just thought it would be nice to share it. Someone asked me if having a "lulz" header wouldn't break things, but since we introduced the "encoding" header a while back clients have learned to ignore unknown headers, so it doesn't.

Which is why we can discuss e.g. adding GPG headers without worrying about breaking everything.

I also think it's interesting that we seemingly don't have (in my brief search, maybe I missed it) an API for writing a complete commit object into a strbuf, so I had to write a lot of commit objects to disk, and keep unlinking the unacceptable candidates so the repository wouldn't balloon in size.

On Wed, Oct 19, 2011 at 08:03:24PM +0200, Ævar Arnfjörð Bjarmason wrote:

Clever and amusing.

Nice header name.

Calculating an object sha1 is pretty straightforward. I think you could just tack the "commit <size>" header in front of the commit strbuf, and sha1 that, and then just send the "winner" to actually be written.

Too bad it won't work in an append only way. The internal state of sha1 after a certain set of bytes is deterministic, so you could do something like:

  void leetify_object(struct strbuf *data)
  {
          SHA_CTX base, guess;
          int len = data->len;
          int i = 0;

          /* come up with a base internal state representing
           * the commit */
          SHA1_Init(&base);
          SHA1_Update(&base, data->buf, data->len);

          while (1) {
                  char append[64];
                  int n = snprintf(append, sizeof(append),
                                   "x-lulz-by: %d\n", i);
                  unsigned char sha1[20];

                  /* and then from that state, see what the sha1 would
                   * be if we add our few new bytes */
                  memcpy(&guess, &base, sizeof(guess));
                  SHA1_Update(&guess, append, n);
                  SHA1_Final(sha1, &guess);

                  /* did we pick a winner? */
                  if (sha1[0] == 0x31 &&
                      sha1[1] == 0x33 &&
                      &sha1[2] & 0xf0) == 0x70) {
                            strbuf_addstr(data, append);
                            return;
                  }

                  i++;
          }
  }

There are two problems with this:

  1. The x-lulz-by header is visible in the commit message. I think you
     can actually get around this by appending a NUL character, and "git
     log" and friends will stop processing the commit message there.

  2. The object header will actually have the length of the object at
     the beginning. So as your lulz number grows, the length of the
     object will change, and invalidate your earlier sha1. You could get
     around this by using a fixed-size guess (e.g., start with 20 bytes
     of zeroes, and then just keep incrementing).

-Peff

On Wed, Oct 19, 2011 at 03:01:14PM -0400, Jeff King wrote:

OK, here's a patch which does that. It's way faster:

  $ git init
  $ time for i in `seq 1 10`; do
      echo $i >file
      git add file
      git commit -q -m $i
    done
  real    0m1.212s
  user    0m1.132s
  sys     0m0.028s

So that's about .12 seconds per commit. Without my patch, it's about .01 seconds. So you waste a tenth of a second generating the collision. Not too bad.

And the result:

  $ git log --oneline
  31337a1 10
  313376b 9
  3133782 8
  31337cf 7
  313377a 6
  313374b 5
  31337b1 4
  31337a3 3
  3133703 2
  3133706 1

And nothing shows up in the body, because git truncates at the NUL we added:

  $ git show
  commit 31337a1093af2d97eb2e6c08b261c2946395fdd3
  Author: Jeff King <peff@peff.net>
  Date:   Wed Oct 19 15:34:00 2011 -0400

      10

  diff --git a/file b/file
  index ec63514..f599e28 100644
  --- a/file
  +++ b/file
  @@ -1 +1 @@
  -9
  +10

It also parameterizes the desired sha1, so you could easily find hashes ending in 31337, or any other pattern. Or add "git commit --collide=31337".

---

On Wed, Oct 19, 2011 at 03:38:34PM -0400, Jeff King wrote:

I couldn't resist:

  $ git commit -q -m foo --collide=deadbeef &&
    git rev-list -1 HEAD
  deadbeefdbd6e62a2185606a4fad653e22509b56

You can also do:

  $ SHA1=0000000000000000000000000000000000031337
  $ MASK=00000000000000000000000000000000000fffff
  $ git commit -q -m foo --collide=$SHA1/$MASK &&
    git rev-list -1 HEAD
  ea49af84db92ed0d2bc3ed13810f5990e7c31337

Keep in mind that each hex character you add increases the search space by a factor of 16. deadbeef took about 70 seconds to find on my machine. I'm tempted to look for "3133700..0031337", but it would probably take about 4 hours.

Patch is below.

-Peff

---

On Wed, Oct 19, 2011 at 22:51, Jeff King <peff@peff.net> wrote:

Heh, there's one other practical downside I can think of...

If you create a bunch of commits with the same 8-hex-character prefix then suddenly the "git describe" logic for using the first 7 commit ID characters gets a whole lot less useful.

Cheers, Kyle Moffett

On Thu, Oct 20, 2011 at 12:15:03AM -0400, Kyle Moffett wrote:

Actually, git will generally find a unique abbreviation among all of your objects when using abbreviated sha1s, so you'll just get longer abbreviations. Of course, it is only unique at the time of generation, so new objects may make it ambiguous. Which is why the default minimum is 7, not 1. But of course with this trick you've effectively removed all of the entropy from those initial 7 characters, and you effectively only have 1 or 2 non-uniform characters.

So yeah, it is worse. But really...spending millions of CPU cycles to get a preimage collision with the partial sha1, and hack-ishly embedding random crap after a NUL in every commit message, and _this_ is your complaint? ;)

-Peff

Kyle Moffett <kyle@moffetthome.net> writes:

In the sense that you need to cut and paste a lot more characters, you are correct that it would make it less useful, but if you are talking about uniqueness, you are mistaken.

The rule is not "using the first 7 hexdigits", but is "using as many hexdigits to make assure uniqueness, but use at least 7".

On Thu, Oct 20, 2011 at 00:27, Junio C Hamano <gitster@pobox.com> wrote:

Well, yes, but if you generate some 10 commits with the same 7-character prefix, run "git describe", and then generate another several with the same prefix... Chances are the previously-unique output of "git describe" is no longer unique.

Also, even if you do use enough characters for it to be reliably unique, it's not really an abbreviation if your commit description is "v2.0.3-42-gdeadbeef04a69f", with that many characters you might as well just paste the whole SHA1 sum.

With all that said, it is a very clever (and ugly) hack :-D.  Kudos!

Cheers, Kyle Moffett

On Wed, Oct 19, 2011 at 10:51:49PM -0400, Jeff King wrote:

Here's a followup with a few cleanups:

  1. It will actually finish and report an error if we fail to find a
     commit after ULONG_MAX tries. On 64-bit machines this is unlikely,
     but it might be possible on a 32-bit machine if you have a lot of
     patience.

  2. It uses git_SHA* now, so it will build properly against BLK_SHA1 if
     NO_OPENSSL is defined.

  3. It will split the the collision-finding work across online_cpus()
     threads.

Somebody else suggested farming the work out to a GPU. I'll leave that as an exercise to the reader.

-Peff

---
 builtin/commit.c |   56 ++++++++++++++++++-
 commit.c         |  165 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
 commit.h         |    4 +
 3 files changed, 223 insertions(+), 2 deletions(-)

Jeff King <peff@peff.net> writes:

But you cannot hide from "cat-file commit" ;-)

With the recent push to more (perceived) security, it may probably make sense to teach "log" family commands to quote-show ^@ and what is behind in their output by default, perhaps with an option to turn it off.

On Wed, Oct 19, 2011 at 09:31:16PM -0700, Junio C Hamano wrote:

Yes. The implementation is a horrible hack, second only in grossness to the original idea. :)

Agreed. Having hidden cruft makes birthday collision attacks easier (or it will, if sha1 ever gets broken to that point). Unfortunately, there is a _ton_ of code which assumes that commit messages are NUL-terminated, as they always have been since e871b64 (2005-05-25).

-Peff

Jeff King <peff@peff.net> writes:

I think that commit is irrelevant, as long as read_sha1_file() returns the contents as <ptr,len> pair, which has been the case forever. It's just the matter of propagating the length back up the callchain.

A naïve implementation to add "len" member to struct commit would increase the size of the in-core commit object by sizeof(unsigned long), which we may want to avoid. Traversals that care nothing but the topology of the history would have to waste that memory and these things tend to add up (8-byte ulong * 250k commits = 2MB).

Perhaps change the type of "buf" member in struct commit to a pointer to a <ptr,len> pair, or something? Or perhaps a few megabytes wasted between friends we do not care much about?

On Wed, Oct 19, 2011 at 11:57:17PM -0700, Junio C Hamano wrote:

It's not that the commit is bad or the source of problems. My point is that the assumption that commit messages are NUL-terminated has been there for a really long time, so there are lots of spots in the code that sloppily run string functions on them. Every one of those needs to be found and fixed (e.g., I remember seeing this in for-each-ref.c:find_subpos recently).

It's not impossible, of course, or even really that hard. It's just a giant pain, and I wonder if the effort is worth it.

I think you'd have to convert the struct (even if not every piece of code is converted to use it) and profile.

-Peff

On Thu, Oct 20, 2011 at 03:13:56AM -0400, Jeff King wrote:

Another possibility is to warn if the commit messages are not NULL terminated. Note though that if we're really worried about a bad guy trying to attack us with a hash collision, he/she could always use "invisible" non-printing characters in the commit message, and/or just mess with one or both of the timestamps. The more bits and more degrees of flexibility the attacker has, the easier it would be, of course. In the grand scheme of things it's not clear to me how big of a deal this would be.

If people were really concerned it would probably be easier to use backup crypto checksum using something stronger (say, SHA-2 or the eventual SHA-3). Just store the backup checksums of the parent commitments in some backwardly compatible place that old git implementations wouldn't look (say, after the NULL in the commit message if there isn't a better place :-), and new implementations would know to generate the checksums, and old implementations would ignore it.

That way, if anyone *does* figure out a way to generate real hash collisions with SHA1 of objects that look almost completely identical to the original objects, new implementations that would gradually make their way out to the field could verify the SHA-2 (or SHA-3, when it is announced, assuming that we the tag the checksums with a type identifier) checksums and notice that they are not correct.

Maybe someone's already thought of this, but the cool thing about this idea is it's a way that we can upgrade to a stronger hash algorithm without needing a flag day due to some kind of incompatible format change; we keep using SHA1 for the user-visible hash, since it's fine modulo intentional attacks, and then use a hidden, backup checksum which can be checked either all the time, or if that turns out to be a computational burden, at some configurable random percent of the time.

Anyway, just a thought....

	      	      	     		   	  - Ted

On Thu, Oct 20, 2011 at 09:14:55AM -0400, Ted Ts'o wrote:

A minor nit, but it's not whether they are terminated with NUL, but rather whether they have embedded NUL. But yeah, this could maybe just be something fsck looks for.

Good point. Append-only attacks are cheaper, because you can avoid doing most of the hash computation on each iteration (like my patch does). But that's not a big-O speedup, it just makes the constant smaller. So you could assume that any feasible appending attack would probably become feasible for recomputing the full hash eventually.

Yeah, if birthday attacks against sha1 become possible, the sensible thing is probably not to worry too much about the file format, but to use a better hash.

Commits can hide extra hashes in a header pretty easily. But what about trees and blobs? I don't think there's any "ignored" space in either one.

-Peff

On Thu, 2011-10-20 at 11:56 -0400, Jeff King wrote:

God (or your deity of choice) forbid that anybody ever writes code that saves raw UTF-16 as the commit message...

Jeff King <peff@peff.net> writes:

True.

It probably is not worth it for most applications, but this fix-up to a fairly recent one is worth doing, I would suspect.

-- >8 --
Subject: parse_signed_commit: really use the entire commit log message

... even beyond the first NUL in the buffer, when checking the commit against the detached signature in the header.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 commit.c                 |   11 +++++------
 t/t7510-signed-commit.sh |   21 ++++++++++++++++-----
 2 files changed, 21 insertions(+), 11 deletions(-)

On Thu, Oct 20, 2011 at 11:36:48AM -0700, Junio C Hamano wrote:

Yeah, that is worth fixing, I think. It's one thing to be a little lazy in pretty-printing for "git log", but I think signature verification should be more careful.

Patch itself looks sane to me. There's still some use of str-like functions, but they would prevent us from even seeing the signature headers in the first place, so anything with a NUL that high is just broken and crappy.

I didn't check, but I wonder if fsck does/should check that there is a proper end-of-header blank line before we hit any NUL.

-Peff

On Thu, Oct 20, 2011 at 5:57 PM, Junio C Hamano <gitster@pobox.com> wrote:

Or write commit_length(struct commit *c) that calculates SHA-1 from c->buf and checks against c->object.sha1. If it does not match, consider NUL part of the message and move to the next NUL. This function would be expensive so we may not call frequently though.

Or store length in ((int*)c->buf)[-1].

On Thu, Oct 20, 2011 at 3:31 PM, Junio C Hamano <gitster@pobox.com> wrote:

What about NUL in file name in tree objects? Suppose the original tree has an entry named "goodthing". With luck, they might be able to create a new tree object with the entry renamed to "evil\x001234" that has the same SHA-1. Could that possibly cause any problems?

On Thu, Oct 20, 2011 at 08:14:56PM +1100, Nguyen Thai Ngoc Duy wrote:

NUL is already meaningful in a tree object; it is the end of the filename. So after the NUL, we will consider the next 20 bytes to be sha1, and then after that, the mode of the next file entry.

-Peff

On 19 October 2011 21:01, Jeff King <peff@peff.net> wrote:

If you don't mind waiting, you could just increase the timestamps until you get the desired collision. (If you still want them to be correct, trying 4000000 times would about 6 weeks though :).

On Thu, Oct 20, 2011 at 3:38 AM, Mikael Magnusson <mikachu@gmail.com> wrote:

But the nice thing is that we have both author and committer dates to twiddle with, meaning that if we need 4000000 different values to try then it's only 2000 for each of those two dates, i.e. we only need to be willing to let those dates float by about half an hour.

Ævar Arnfjörð Bjarmason wrote:

Just for the record (and I think you understood this already): it is not quite so simple. Clients are allowed to assume that no "unknown" header lines will appear before any of the known fields. A future git version could even assume that, say, a

	length-of-remainder-of-header

field appears before any lines after encoding and the GPG stuff.

So it would definitely be frowned upon to add new lines to that part of the commit object without at least discussing it on this list. Jeff mentioned one way to get your lulz without violating that constraint. ;-)

http://thread.gmane.org/gmane.comp.version-control.git/138848/focus=138921