Re: Git and SHA-1 security (again)

Hi Brian,

On Mon, 18 Jul 2016, brian m. carlson wrote:

On Mon, Jul 18, 2016 at 09:00:06AM +0200, Johannes Schindelin wrote:

quoted

FWIW it never crossed my mind to allow different same-sized hash
algorithms. So I never thought we'd need a way to distinguish, say,
BLAKE2b-256 from SHA-256.

Is there a good reason to add the maintenance burden of several 256-bit
hash algorithms, apart from speed (which in my mind should decide which
one to use, always, rather than letting the user choose)? It would also
complicate transport even further, let alone subtree merges from
differently-hashed repositories.

There are really three candidates:

* SHA-256 (the SHA-2 algorithm): While this looks good right now,
  cryptanalysis is advancing.  This is not a good choice for a long-term
  solution.
* SHA3-256 (the SHA-3 algorithm): This is the conservative choice.  It's
  also faster than SHA-256 on 64-bit systems.  It has a very
  conservative security margin and is a good long-term choice.
* BLAKE2b-256: This is the blisteringly fast choice.  It outperforms
  SHA-1 and even MD5 on 64-bit systems.  This algorithm was designed so
  that nobody would have a reason to use an insecure algorithm.  It will
  probably be secure for some time, but maybe not as long as SHA3-256.

I'm only considering 256-bit hashes, because anything longer won't fit
on an 80-column terminal in hex form.

The reason I had considered implementing both SHA3-256 and BLAKE2b-256
is that I want there to be no reason not to upgrade.  People who need a
FIPS-approved algorithm or want a long-term, conservative choice should
use SHA3-256.  People who want even better performance than current Git
would use BLAKE2b-256.

Performance comparison (my implementations):
SHA-1:     437 MiB/s
SHA-256:   196 MiB/s
SHA3-256:  273 MiB/s
BLAKE2b:   649 MiB/s

Those are impressive numbers on BLAKE2b. However, Keccak was chosen as
SHA-3 because it can be implemented in hardware more efficiently than
BLAKE (and hence, probably, also BLAKE2). Given that there are already SSE
instructions implementing SHA-1/SHA-256 on some CPUs [*1*], I would not be
surprised if SHA3 would also see some hardware support.

So speed seems less of a concern to me. We are talking about a multi-year
roadmap, after all.

And given the complications for public repository hosters, I would like to
settle for a single 256-bit hash. That'll be challenging enough.

Ciao,
Dscho

Footnote *1*: https://en.wikipedia.org/wiki/Intel_SHA_extensions