Re: pushing for a new hash, was Re: [PATCH 2/3] rebase: Add tests for console output

Hi Dscho,

Johannes Schindelin wrote:

Thanks for offering. ;-)

Here's a rough list of some useful tasks, in no particular order:

1. bc/object-id: This patch series continues, eliminating assumptions
   about the size of object ids by encapsulating them in a struct.
   One straightforward way to find code that still needs to be
   converted is to grep for "sha" --- often the conversion patches
   change function and variable names to refer to oid_ where they used
   to use sha1_, making the stragglers easier to spot.

2. Hard-coded object ids in tests: As Stefan hinted, many tests beyond
   t00* make assumptions about the exact values of object ids.  That's
   bad for maintainability for other reasons beyond the hash function
   transition, too.

   It should be possible to suss them out by patching git's sha1
   routine to use the ones-complement of sha1 (~sha1) instead and
   seeing which tests fail.

3. Repository format extension to use a different hash function: we
   want git to be able to work with two hash functions: sha1 and
   something else.  For interoperability and simplity, it is useful
   for a single git binary to support both hash functions.

   That means a repository needs to be able to specify what hash
   function is used for the objects in that repository.  This can be
   configured by setting '[core] repositoryformatversion=1' (to avoid
   confusing old versions of git) and
   '[extensions] experimentalNewHashFunction = true'.
   Documentation/technical/repository-version.txt has more details.

   We can start experimenting with this using e.g. the ~sha1 function
   described at (2), or the 160-bit hash of the patch author's choice
   (e.g. truncated blake2bp-256).

4. When choosing a hash function, people may argue about performance.
   It would be useful for run some benchmarks for git (running
   the test suite, t/perf tests, etc) using a variety of hash
   functions as input to such a discussion.

5. Longer hash: Even once all object id references in git use struct
   object_id (see (1)), we need to tackle other assumptions about
   object id size in git and its tests.

   It should be possible to suss them out by replacing git's sha1
   routine with a 40-byte hash: sha1 with each byte repeated (sha1+sha1)
   and seeing what fails.

6. Repository format extension for longer hash: As in (3), we could
   add a repository format extension to experiment with using the
   sha1+sha1 function.

7. Avoiding wasted memory from unused hash functions: struct object_id
   has definition 'unsigned char hash[GIT_MAX_RAWSZ]', where
   GIT_MAX_RAWSZ is the size of the largest supported hash function.
   When operating on a repository that only uses sha1, this wastes
   memory.

   Avoid that by making object identifiers variable-sized.  That is,
   something like

     struct object_id {
     	union {
	  unsigned char hash20[20];
	  unsigned char hash32[32];
	} *hash;
     }

   or

     struct object_id {
       unsigned char *hash;
     }

   The hard part is that allocation and destruction have to be
   explicit instead of happening automatically when an object_id is an
   automatic variable.

8. Implement
   http://public-inbox.org/git/20170307001709.GC26789@aiede.mtv.corp.google.com/
   :)  I'd like to send a breakdown of that too, but that probably
   should happen in a separate message.

9. We can use help from security experts in all of this.  Fuzzing,
   analysis of how we use cryptography, security review of other parts
   of the design, and information to help choose a hash function are
   all appreciated.

Do you have some ideas in mind here?

How did you get the impression that their opinion had no impact? We have been getting feedback about the choice of hash function both on and off list from a variety of people, some indisputably security experts. Sometimes the best one can do is to just listen.

For what it's worth my personal opinion is currently leaning toward blake2bp-256 as choice of hash function, not SHA2 or SHA3. But we still have time to learn more and make a better decision.

Thanks and hope that helps, Jonathan