[RFC PATCH 00/12] Base SHA-256 algorithm implementation

[RFC PATCH 00/12] Base SHA-256 algorithm implementation

[brian m. carlson]

This RFC series provides an actual SHA-256 implementation and wires it
up, along with a few housekeeping patches to make it usable for testing.

As discussed in some threads, this changes the algorithm name from
"sha-1" to "sha1" (and also adds "sha256") because it's far easier to
type.

I introduced some basic tests for the hash algorithms in use.  Since I
did not import the SHA-256 implementation verbatim, I felt it was
necessary to ensure that the hash algorithm implementations continued to
function as expected.  My main changes were to adjust the code to use
our endianness functions, to adopt something closer to our style, and to
make use of memcpy and friends for performance reasons.

I opted to place all the implementation code for SHA-256 into one
directory, as opposed to the various directories we have for the SHA-1
implementations, mostly for tidiness and ease of use.

I wired up OpenSSL because we already have it and libgcrypt because it
performs better than SHA-1.  I didn't provide an implementation for
SHA-1 with libgcrypt because everybody should be using SHA1DC for
security.

I didn't provide an implementation based on libnettle because its x86-64
assembly implementation isn't vectorized and is pretty slow.  Since this
was written before I had access to a Mac, Apple Common Crypto hasn't
been wired up, either.  Patches welcome.

If libgit2 would like to import this SHA-256 implementation, they're
welcome to do so under their normal license terms.  If not, that's fine,
too.

brian m. carlson (12):
  sha1-file: rename algorithm to "sha1"
  sha1-file: provide functions to look up hash algorithms
  hex: introduce functions to print arbitrary hashes
  t: add basic tests for our SHA-1 implementation
  t: make the sha1 test-tool helper generic
  sha1-file: add a constant for hash block size
  t/helper: add a test helper to compute hash speed
  commit-graph: convert to using the_hash_algo
  Add a base implementation of SHA-256 support
  sha256: add an SHA-256 implementation using libgcrypt
  hash: add an SHA-256 implementation using OpenSSL
  commit-graph: specify OID version for SHA-256

 Makefile                              |  22 ++++
 cache.h                               |  28 ++--
 commit-graph.c                        |  38 +++---
 hash.h                                |  41 +++++-
 hex.c                                 |  32 +++--
 sha1-file.c                           |  70 +++++++++-
 sha256/block/sha256.c                 | 180 ++++++++++++++++++++++++++
 sha256/block/sha256.h                 |  26 ++++
 sha256/gcrypt.h                       |  30 +++++
 t/helper/test-hash-speed.c            |  61 +++++++++
 t/helper/{test-sha1.c => test-hash.c} |  19 +--
 t/helper/test-sha1.c                  |  52 +-------
 t/helper/test-sha256.c                |   7 +
 t/helper/test-tool.c                  |   2 +
 t/helper/test-tool.h                  |   4 +
 t/t0014-hash.sh                       |  54 ++++++++
 16 files changed, 573 insertions(+), 93 deletions(-)
 create mode 100644 sha256/block/sha256.c
 create mode 100644 sha256/block/sha256.h
 create mode 100644 sha256/gcrypt.h
 create mode 100644 t/helper/test-hash-speed.c
 copy t/helper/{test-sha1.c => test-hash.c} (66%)
 create mode 100644 t/helper/test-sha256.c
 create mode 100755 t/t0014-hash.sh

[RFC PATCH 01/12] sha1-file: rename algorithm to "sha1"

[brian m. carlson]

The transition plan anticipates us using a syntax such as "^{sha1}" for
disambiguation.  Since this is a syntax some people will be typing a
lot, it makes sense to provide a short, easy-to-type syntax.  Omitting
the dash doesn't create any ambiguity, but it does make it shorter and
easier to type, especially for touch typists.  In addition, the
transition plan already uses "sha1" in this context.

Rename the name of SHA-1 implementation to "sha1".

Note that this change creates no backwards compatibility concerns, since
we haven't yet used this field in any serialized data formats.

Signed-off-by: brian m. carlson <sandals@crustytoothpaste.net>
---
 sha1-file.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/sha1-file.c b/sha1-file.c
index 97b7423848..5223e3d1ce 100644
--- a/sha1-file.c
+++ b/sha1-file.c
@@ -97,7 +97,7 @@ const struct git_hash_algo hash_algos[GIT_HASH_NALGOS] = {
 		NULL,
 	},
 	{
-		"sha-1",
+		"sha1",
 		/* "sha1", big-endian */
 		0x73686131,
 		GIT_SHA1_RAWSZ,

[RFC PATCH 02/12] sha1-file: provide functions to look up hash algorithms

[brian m. carlson]

There are several ways we might refer to a hash algorithm: by name, such
as in the config file; by format ID, such as in a pack; or internally,
by a pointer to the hash_algos array.  Provide functions to look up hash
algorithms based on these various forms and return the internal constant
used for them.  If conversion to another form is necessary, this
internal constant can be used to look up the proper data in the
hash_algos array.

Signed-off-by: brian m. carlson <sandals@crustytoothpaste.net>
---
 hash.h      | 13 +++++++++++++
 sha1-file.c | 21 +++++++++++++++++++++
 2 files changed, 34 insertions(+)

diff --git a/hash.h b/hash.h
index 7c8238bc2e..90f4344619 100644
--- a/hash.h
+++ b/hash.h
@@ -98,4 +98,17 @@ struct git_hash_algo {
 };
 extern const struct git_hash_algo hash_algos[GIT_HASH_NALGOS];
 
+/*
+ * Return a GIT_HASH_* constant based on the name.  Returns GIT_HASH_UNKNOWN if
+ * the name doesn't match a known algorithm.
+ */
+int hash_algo_by_name(const char *name);
+/* Identical, except based on the format ID. */
+int hash_algo_by_id(uint32_t format_id);
+/* Identical, except for a pointer to struct git_hash_algo. */
+inline int hash_algo_by_ptr(const struct git_hash_algo *p)
+{
+	return p - hash_algos;
+}
+
 #endif
diff --git a/sha1-file.c b/sha1-file.c
index 5223e3d1ce..f6976b179f 100644
--- a/sha1-file.c
+++ b/sha1-file.c
@@ -122,6 +122,27 @@ const char *empty_blob_oid_hex(void)
 	return oid_to_hex_r(buf, the_hash_algo->empty_blob);
 }
 
+int hash_algo_by_name(const char *name)
+{
+	int i;
+	if (!name)
+		return GIT_HASH_UNKNOWN;
+	for (i = 1; i < GIT_HASH_NALGOS; i++)
+		if (!strcmp(name, hash_algos[i].name))
+			return i;
+	return GIT_HASH_UNKNOWN;
+}
+
+int hash_algo_by_id(uint32_t format_id)
+{
+	int i;
+	for (i = 1; i < GIT_HASH_NALGOS; i++)
+		if (format_id == hash_algos[i].format_id)
+			return i;
+	return GIT_HASH_UNKNOWN;
+}
+
+
 /*
  * This is meant to hold a *small* number of objects that you would
  * want read_sha1_file() to be able to return, but yet you do not want

[RFC PATCH 03/12] hex: introduce functions to print arbitrary hashes

[brian m. carlson]

Currently, we have functions that turn an arbitrary SHA-1 value or an
object ID into hex format, either using a static buffer or with a
user-provided buffer.  Add variants of these functions that can handle
an arbitrary hash algorithm, specified by constant.  Update the
documentation as well.

While we're at it, remove the "extern" declaration from this family of
functions, since it's not needed and our style now recommends against
it.

We use the variant taking the algorithm structure pointer as the
internal variant, since in the future we'll want to replace sha1_to_hex
with a hash_to_hex that handles the_hash_algo, and taking an algorithm
pointer is the easiest way to handle all of the variants in use.

Signed-off-by: brian m. carlson <sandals@crustytoothpaste.net>
---
 cache.h | 14 ++++++++------
 hex.c   | 32 ++++++++++++++++++++++++--------
 2 files changed, 32 insertions(+), 14 deletions(-)

diff --git a/cache.h b/cache.h
index 4d014541ab..3cb953445c 100644
--- a/cache.h
+++ b/cache.h
@@ -1351,9 +1351,9 @@ extern int get_oid_hex(const char *hex, struct object_id *sha1);
 extern int hex_to_bytes(unsigned char *binary, const char *hex, size_t len);
 
 /*
- * Convert a binary sha1 to its hex equivalent. The `_r` variant is reentrant,
+ * Convert a binary hash to its hex equivalent. The `_r` variant is reentrant,
  * and writes the NUL-terminated output to the buffer `out`, which must be at
- * least `GIT_SHA1_HEXSZ + 1` bytes, and returns a pointer to out for
+ * least `GIT_MAX_HEXSZ + 1` bytes, and returns a pointer to out for
  * convenience.
  *
  * The non-`_r` variant returns a static buffer, but uses a ring of 4
@@ -1361,10 +1361,12 @@ extern int hex_to_bytes(unsigned char *binary, const char *hex, size_t len);
  *
  *   printf("%s -> %s", sha1_to_hex(one), sha1_to_hex(two));
  */
-extern char *sha1_to_hex_r(char *out, const unsigned char *sha1);
-extern char *oid_to_hex_r(char *out, const struct object_id *oid);
-extern char *sha1_to_hex(const unsigned char *sha1);	/* static buffer result! */
-extern char *oid_to_hex(const struct object_id *oid);	/* same static buffer as sha1_to_hex */
+char *hash_to_hex_algo_r(char *buffer, const unsigned char *hash, int algo);
+char *sha1_to_hex_r(char *out, const unsigned char *sha1);
+char *oid_to_hex_r(char *out, const struct object_id *oid);
+char *hash_to_hex_algo(const unsigned char *hash, int algo);	/* static buffer result! */
+char *sha1_to_hex(const unsigned char *sha1);			/* same static buffer */
+char *oid_to_hex(const struct object_id *oid);			/* same static buffer */
 
 /*
  * Parse a 40-character hexadecimal object ID starting from hex, updating the
diff --git a/hex.c b/hex.c
index 10af1a29e8..870032a868 100644
--- a/hex.c
+++ b/hex.c
@@ -73,14 +73,15 @@ int parse_oid_hex(const char *hex, struct object_id *oid, const char **end)
 	return ret;
 }
 
-char *sha1_to_hex_r(char *buffer, const unsigned char *sha1)
+static inline char *hash_to_hex_algop_r(char *buffer, const unsigned char *hash,
+					const struct git_hash_algo *algop)
 {
 	static const char hex[] = "0123456789abcdef";
 	char *buf = buffer;
 	int i;
 
-	for (i = 0; i < the_hash_algo->rawsz; i++) {
-		unsigned int val = *sha1++;
+	for (i = 0; i < algop->rawsz; i++) {
+		unsigned int val = *hash++;
 		*buf++ = hex[val >> 4];
 		*buf++ = hex[val & 0xf];
 	}
@@ -89,20 +90,35 @@ char *sha1_to_hex_r(char *buffer, const unsigned char *sha1)
 	return buffer;
 }
 
-char *oid_to_hex_r(char *buffer, const struct object_id *oid)
+char *hash_to_hex_algo_r(char *buffer, const unsigned char *hash, int algo)
 {
-	return sha1_to_hex_r(buffer, oid->hash);
+	return hash_to_hex_algop_r(buffer, hash, &hash_algos[algo]);
 }
 
-char *sha1_to_hex(const unsigned char *sha1)
+char *sha1_to_hex_r(char *buffer, const unsigned char *sha1)
+{
+	return hash_to_hex_algo_r(buffer, sha1, GIT_HASH_SHA1);
+}
+
+char *oid_to_hex_r(char *buffer, const struct object_id *oid)
+{
+	return hash_to_hex_algop_r(buffer, oid->hash, the_hash_algo);
+}
+
+char *hash_to_hex_algo(const unsigned char *hash, int algo)
 {
 	static int bufno;
 	static char hexbuffer[4][GIT_MAX_HEXSZ + 1];
 	bufno = (bufno + 1) % ARRAY_SIZE(hexbuffer);
-	return sha1_to_hex_r(hexbuffer[bufno], sha1);
+	return hash_to_hex_algo_r(hexbuffer[bufno], hash, algo);
+}
+
+char *sha1_to_hex(const unsigned char *sha1)
+{
+	return hash_to_hex_algo(sha1, GIT_HASH_SHA1);
 }
 
 char *oid_to_hex(const struct object_id *oid)
 {
-	return sha1_to_hex(oid->hash);
+	return hash_to_hex_algo(oid->hash, hash_algo_by_ptr(the_hash_algo));
 }

[RFC PATCH 04/12] t: add basic tests for our SHA-1 implementation

[brian m. carlson]

We have in the past had some unfortunate endianness issues with some
SHA-1 implementations we ship, especially on big-endian machines.  Add
an explicit test using the test helper to catch these issues and point
them out prominently.  This test can also be used as a staging ground
for people testing additional algorithms to verify that their
implementations are working as expected.

Signed-off-by: brian m. carlson <sandals@crustytoothpaste.net>
---
 t/t0014-hash.sh | 29 +++++++++++++++++++++++++++++
 1 file changed, 29 insertions(+)
 create mode 100755 t/t0014-hash.sh

diff --git a/t/t0014-hash.sh b/t/t0014-hash.sh
new file mode 100755
index 0000000000..8e763c2c3d
--- /dev/null
+++ b/t/t0014-hash.sh
@@ -0,0 +1,29 @@
+#!/bin/sh
+
+test_description='test basic hash implementation'
+. ./test-lib.sh
+
+
+test_expect_success 'test basic SHA-1 hash values' '
+	test-tool sha1 </dev/null >actual &&
+	grep da39a3ee5e6b4b0d3255bfef95601890afd80709 actual &&
+	printf "a" | test-tool sha1 >actual &&
+	grep 86f7e437faa5a7fce15d1ddcb9eaeaea377667b8 actual &&
+	printf "abc" | test-tool sha1 >actual &&
+	grep a9993e364706816aba3e25717850c26c9cd0d89d actual &&
+	printf "message digest" | test-tool sha1 >actual &&
+	grep c12252ceda8be8994d5fa0290a47231c1d16aae3 actual &&
+	printf "abcdefghijklmnopqrstuvwxyz" | test-tool sha1 >actual &&
+	grep 32d10c7b8cf96570ca04ce37f2a19d84240d3a89 actual &&
+	perl -E "for (1..100000) { print q{aaaaaaaaaa}; }" | \
+		test-tool sha1 >actual &&
+	grep 34aa973cd4c4daa4f61eeb2bdbad27316534016f actual &&
+	printf "blob 0\0" | test-tool sha1 >actual &&
+	grep e69de29bb2d1d6434b8b29ae775ad8c2e48c5391 actual &&
+	printf "blob 3\0abc" | test-tool sha1 >actual &&
+	grep f2ba8f84ab5c1bce84a7b441cb1959cfc7093b7f actual &&
+	printf "tree 0\0" | test-tool sha1 >actual &&
+	grep 4b825dc642cb6eb9a060e54bf8d69288fbee4904 actual
+'
+
+test_done

[RFC PATCH 05/12] t: make the sha1 test-tool helper generic

[brian m. carlson]

Since we're going to have multiple hash algorithms to test, it makes
sense to share as much of the test code as possible.  Convert the sha1
helper for the test-tool to be generic and move it out into its own
module.  This will allow us to share most of this code with our NewHash
implementation.

Signed-off-by: brian m. carlson <sandals@crustytoothpaste.net>
---
 Makefile                              |  1 +
 t/helper/{test-sha1.c => test-hash.c} | 19 +++++-----
 t/helper/test-sha1.c                  | 52 +--------------------------
 t/helper/test-tool.h                  |  2 ++
 4 files changed, 14 insertions(+), 60 deletions(-)
 copy t/helper/{test-sha1.c => test-hash.c} (66%)

diff --git a/Makefile b/Makefile
index 5a969f5830..eb1a080cc9 100644
--- a/Makefile
+++ b/Makefile
@@ -712,6 +712,7 @@ TEST_BUILTINS_OBJS += test-dump-cache-tree.o
 TEST_BUILTINS_OBJS += test-dump-split-index.o
 TEST_BUILTINS_OBJS += test-example-decorate.o
 TEST_BUILTINS_OBJS += test-genrandom.o
+TEST_BUILTINS_OBJS += test-hash.o
 TEST_BUILTINS_OBJS += test-hashmap.o
 TEST_BUILTINS_OBJS += test-index-version.o
 TEST_BUILTINS_OBJS += test-json-writer.o
diff --git a/t/helper/test-sha1.c b/t/helper/test-hash.c
similarity index 66%
copy from t/helper/test-sha1.c
copy to t/helper/test-hash.c
index 1ba0675c75..9992de2212 100644
--- a/t/helper/test-sha1.c
+++ b/t/helper/test-hash.c
@@ -1,13 +1,14 @@
 #include "test-tool.h"
 #include "cache.h"
 
-int cmd__sha1(int ac, const char **av)
+int cmd_hash_impl(int ac, const char **av, int algo)
 {
-	git_SHA_CTX ctx;
-	unsigned char sha1[20];
+	git_hash_ctx ctx;
+	unsigned char hash[GIT_MAX_HEXSZ];
 	unsigned bufsz = 8192;
 	int binary = 0;
 	char *buffer;
+	const struct git_hash_algo *algop = &hash_algos[algo];
 
 	if (ac == 2) {
 		if (!strcmp(av[1], "-b"))
@@ -26,7 +27,7 @@ int cmd__sha1(int ac, const char **av)
 			die("OOPS");
 	}
 
-	git_SHA1_Init(&ctx);
+	algop->init_fn(&ctx);
 
 	while (1) {
 		ssize_t sz, this_sz;
@@ -38,20 +39,20 @@ int cmd__sha1(int ac, const char **av)
 			if (sz == 0)
 				break;
 			if (sz < 0)
-				die_errno("test-sha1");
+				die_errno("test-hash");
 			this_sz += sz;
 			cp += sz;
 			room -= sz;
 		}
 		if (this_sz == 0)
 			break;
-		git_SHA1_Update(&ctx, buffer, this_sz);
+		algop->update_fn(&ctx, buffer, this_sz);
 	}
-	git_SHA1_Final(sha1, &ctx);
+	algop->final_fn(hash, &ctx);
 
 	if (binary)
-		fwrite(sha1, 1, 20, stdout);
+		fwrite(hash, 1, algop->rawsz, stdout);
 	else
-		puts(sha1_to_hex(sha1));
+		puts(hash_to_hex_algo(hash, algo));
 	exit(0);
 }
diff --git a/t/helper/test-sha1.c b/t/helper/test-sha1.c
index 1ba0675c75..d860c387c3 100644
--- a/t/helper/test-sha1.c
+++ b/t/helper/test-sha1.c
@@ -3,55 +3,5 @@
 
 int cmd__sha1(int ac, const char **av)
 {
-	git_SHA_CTX ctx;
-	unsigned char sha1[20];
-	unsigned bufsz = 8192;
-	int binary = 0;
-	char *buffer;
-
-	if (ac == 2) {
-		if (!strcmp(av[1], "-b"))
-			binary = 1;
-		else
-			bufsz = strtoul(av[1], NULL, 10) * 1024 * 1024;
-	}
-
-	if (!bufsz)
-		bufsz = 8192;
-
-	while ((buffer = malloc(bufsz)) == NULL) {
-		fprintf(stderr, "bufsz %u is too big, halving...\n", bufsz);
-		bufsz /= 2;
-		if (bufsz < 1024)
-			die("OOPS");
-	}
-
-	git_SHA1_Init(&ctx);
-
-	while (1) {
-		ssize_t sz, this_sz;
-		char *cp = buffer;
-		unsigned room = bufsz;
-		this_sz = 0;
-		while (room) {
-			sz = xread(0, cp, room);
-			if (sz == 0)
-				break;
-			if (sz < 0)
-				die_errno("test-sha1");
-			this_sz += sz;
-			cp += sz;
-			room -= sz;
-		}
-		if (this_sz == 0)
-			break;
-		git_SHA1_Update(&ctx, buffer, this_sz);
-	}
-	git_SHA1_Final(sha1, &ctx);
-
-	if (binary)
-		fwrite(sha1, 1, 20, stdout);
-	else
-		puts(sha1_to_hex(sha1));
-	exit(0);
+	return cmd_hash_impl(ac, av, GIT_HASH_SHA1);
 }
diff --git a/t/helper/test-tool.h b/t/helper/test-tool.h
index e954e8c522..9026a8f608 100644
--- a/t/helper/test-tool.h
+++ b/t/helper/test-tool.h
@@ -41,4 +41,6 @@ int cmd__urlmatch_normalization(int argc, const char **argv);
 int cmd__wildmatch(int argc, const char **argv);
 int cmd__write_cache(int argc, const char **argv);
 
+int cmd_hash_impl(int ac, const char **av, int algo);
+
 #endif

[RFC PATCH 06/12] sha1-file: add a constant for hash block size

[brian m. carlson]

There is one place we need the hash algorithm block size: the HMAC code
for push certs.  Expose this constant in struct git_hash_algo and expose
values for SHA-1 and for the largest value of any hash.

Signed-off-by: brian m. carlson <sandals@crustytoothpaste.net>
---
 cache.h     | 4 ++++
 hash.h      | 3 +++
 sha1-file.c | 2 ++
 3 files changed, 9 insertions(+)

diff --git a/cache.h b/cache.h
index 3cb953445c..c1b5a7a337 100644
--- a/cache.h
+++ b/cache.h
@@ -45,10 +45,14 @@ unsigned long git_deflate_bound(git_zstream *, unsigned long);
 /* The length in bytes and in hex digits of an object name (SHA-1 value). */
 #define GIT_SHA1_RAWSZ 20
 #define GIT_SHA1_HEXSZ (2 * GIT_SHA1_RAWSZ)
+/* The block size of SHA-1. */
+#define GIT_SHA1_BLKSZ 64
 
 /* The length in byte and in hex digits of the largest possible hash value. */
 #define GIT_MAX_RAWSZ GIT_SHA1_RAWSZ
 #define GIT_MAX_HEXSZ GIT_SHA1_HEXSZ
+/* The largest possible block size for any supported hash. */
+#define GIT_MAX_BLKSZ GIT_SHA1_BLKSZ
 
 struct object_id {
 	unsigned char hash[GIT_MAX_RAWSZ];
diff --git a/hash.h b/hash.h
index 90f4344619..46dff69eb3 100644
--- a/hash.h
+++ b/hash.h
@@ -81,6 +81,9 @@ struct git_hash_algo {
 	/* The length of the hash in hex characters. */
 	size_t hexsz;
 
+	/* The block size of the hash. */
+	size_t blksz;
+
 	/* The hash initialization function. */
 	git_hash_init_fn init_fn;
 
diff --git a/sha1-file.c b/sha1-file.c
index f6976b179f..a1ad1b8268 100644
--- a/sha1-file.c
+++ b/sha1-file.c
@@ -90,6 +90,7 @@ const struct git_hash_algo hash_algos[GIT_HASH_NALGOS] = {
 		0x00000000,
 		0,
 		0,
+		0,
 		git_hash_unknown_init,
 		git_hash_unknown_update,
 		git_hash_unknown_final,
@@ -102,6 +103,7 @@ const struct git_hash_algo hash_algos[GIT_HASH_NALGOS] = {
 		0x73686131,
 		GIT_SHA1_RAWSZ,
 		GIT_SHA1_HEXSZ,
+		GIT_SHA1_BLKSZ,
 		git_hash_sha1_init,
 		git_hash_sha1_update,
 		git_hash_sha1_final,

[RFC PATCH 07/12] t/helper: add a test helper to compute hash speed

[brian m. carlson]

Add a utility (which is less for the testsuite and more for developers)
that can compute hash speeds for whatever hash algorithms are
implemented.  This allows developers to test their personal systems to
determine the performance characteristics of various algorithms.

Signed-off-by: brian m. carlson <sandals@crustytoothpaste.net>
---
 Makefile                   |  1 +
 t/helper/test-hash-speed.c | 61 ++++++++++++++++++++++++++++++++++++++
 t/helper/test-tool.c       |  1 +
 t/helper/test-tool.h       |  1 +
 4 files changed, 64 insertions(+)
 create mode 100644 t/helper/test-hash-speed.c

diff --git a/Makefile b/Makefile
index eb1a080cc9..e047dea988 100644
--- a/Makefile
+++ b/Makefile
@@ -714,6 +714,7 @@ TEST_BUILTINS_OBJS += test-example-decorate.o
 TEST_BUILTINS_OBJS += test-genrandom.o
 TEST_BUILTINS_OBJS += test-hash.o
 TEST_BUILTINS_OBJS += test-hashmap.o
+TEST_BUILTINS_OBJS += test-hash-speed.o
 TEST_BUILTINS_OBJS += test-index-version.o
 TEST_BUILTINS_OBJS += test-json-writer.o
 TEST_BUILTINS_OBJS += test-lazy-init-name-hash.o
diff --git a/t/helper/test-hash-speed.c b/t/helper/test-hash-speed.c
new file mode 100644
index 0000000000..432233c7f0
--- /dev/null
+++ b/t/helper/test-hash-speed.c
@@ -0,0 +1,61 @@
+#include "test-tool.h"
+#include "cache.h"
+
+#define NUM_SECONDS 3
+
+static inline void compute_hash(const struct git_hash_algo *algo, git_hash_ctx *ctx, uint8_t *final, const void *p, size_t len)
+{
+	algo->init_fn(ctx);
+	algo->update_fn(ctx, p, len);
+	algo->final_fn(final, ctx);
+}
+
+int cmd__hash_speed(int ac, const char **av)
+{
+	git_hash_ctx ctx;
+	unsigned char hash[GIT_MAX_RAWSZ];
+	clock_t initial, start, end;
+	unsigned bufsizes[] = { 64, 256, 1024, 8192, 16384 };
+	int i;
+	void *p;
+	const struct git_hash_algo *algo = NULL;
+
+	if (ac == 2) {
+		for (i = 1; i < GIT_HASH_NALGOS; i++) {
+			if (!strcmp(av[1], hash_algos[i].name)) {
+				algo = &hash_algos[i];
+				break;
+			}
+		}
+	}
+	if (!algo)
+		die("usage: test-tool hash-speed algo_name");
+
+	/* Use this as an offset to make overflow less likely. */
+	initial = clock();
+
+	printf("algo: %s\n", algo->name);
+
+	for (i = 0; i < ARRAY_SIZE(bufsizes); i++) {
+		unsigned long j, kb;
+		double kb_per_sec;
+		p = xcalloc(1, bufsizes[i]);
+		start = end = clock() - initial;
+		for (j = 0; ((end - start) / CLOCKS_PER_SEC) < NUM_SECONDS; j++) {
+			compute_hash(algo, &ctx, hash, p, bufsizes[i]);
+
+			/*
+			 * Only check elapsed time every 128 iterations to avoid
+			 * dominating the runtime with system calls.
+			 */
+			if (!(j & 127))
+				end = clock() - initial;
+		}
+		kb = j * bufsizes[i];
+		kb_per_sec = kb / (1024 * ((double)end - start) / CLOCKS_PER_SEC);
+		printf("size %u: %lu iters; %lu KiB; %0.2f KiB/s\n", bufsizes[i], j, kb, kb_per_sec);
+		free(p);
+	}
+
+	exit(0);
+}
diff --git a/t/helper/test-tool.c b/t/helper/test-tool.c
index 0edafcfd65..c0d3eecc36 100644
--- a/t/helper/test-tool.c
+++ b/t/helper/test-tool.c
@@ -18,6 +18,7 @@ static struct test_cmd cmds[] = {
 	{ "example-decorate", cmd__example_decorate },
 	{ "genrandom", cmd__genrandom },
 	{ "hashmap", cmd__hashmap },
+	{ "hash-speed", cmd__hash_speed },
 	{ "index-version", cmd__index_version },
 	{ "json-writer", cmd__json_writer },
 	{ "lazy-init-name-hash", cmd__lazy_init_name_hash },
diff --git a/t/helper/test-tool.h b/t/helper/test-tool.h
index 9026a8f608..abe3a253d5 100644
--- a/t/helper/test-tool.h
+++ b/t/helper/test-tool.h
@@ -14,6 +14,7 @@ int cmd__dump_split_index(int argc, const char **argv);
 int cmd__example_decorate(int argc, const char **argv);
 int cmd__genrandom(int argc, const char **argv);
 int cmd__hashmap(int argc, const char **argv);
+int cmd__hash_speed(int argc, const char **argv);
 int cmd__index_version(int argc, const char **argv);
 int cmd__json_writer(int argc, const char **argv);
 int cmd__lazy_init_name_hash(int argc, const char **argv);

[RFC PATCH 08/12] commit-graph: convert to using the_hash_algo

[brian m. carlson]

Instead of using hard-coded constants for object sizes, use
the_hash_algo to look them up.  In addition, use a function call to look
up the object ID version and produce the correct value.

Signed-off-by: brian m. carlson <sandals@crustytoothpaste.net>
---
 commit-graph.c | 31 ++++++++++++++++---------------
 1 file changed, 16 insertions(+), 15 deletions(-)

diff --git a/commit-graph.c b/commit-graph.c
index 8a1bec7b8a..29356d84a2 100644
--- a/commit-graph.c
+++ b/commit-graph.c
@@ -25,11 +25,6 @@
 #define GRAPH_VERSION_1 0x1
 #define GRAPH_VERSION GRAPH_VERSION_1
 
-#define GRAPH_OID_VERSION_SHA1 1
-#define GRAPH_OID_LEN_SHA1 GIT_SHA1_RAWSZ
-#define GRAPH_OID_VERSION GRAPH_OID_VERSION_SHA1
-#define GRAPH_OID_LEN GRAPH_OID_LEN_SHA1
-
 #define GRAPH_OCTOPUS_EDGES_NEEDED 0x80000000
 #define GRAPH_PARENT_MISSING 0x7fffffff
 #define GRAPH_EDGE_LAST_MASK 0x7fffffff
@@ -41,13 +36,18 @@
 #define GRAPH_FANOUT_SIZE (4 * 256)
 #define GRAPH_CHUNKLOOKUP_WIDTH 12
 #define GRAPH_MIN_SIZE (GRAPH_HEADER_SIZE + 4 * GRAPH_CHUNKLOOKUP_WIDTH \
-			+ GRAPH_FANOUT_SIZE + GRAPH_OID_LEN)
+			+ GRAPH_FANOUT_SIZE + the_hash_algo->rawsz)
 
 char *get_commit_graph_filename(const char *obj_dir)
 {
 	return xstrfmt("%s/info/commit-graph", obj_dir);
 }
 
+static uint8_t oid_version(void)
+{
+	return 1;
+}
+
 static struct commit_graph *alloc_commit_graph(void)
 {
 	struct commit_graph *g = xcalloc(1, sizeof(*g));
@@ -100,15 +100,15 @@ struct commit_graph *load_commit_graph_one(const char *graph_file)
 	}
 
 	hash_version = *(unsigned char*)(data + 5);
-	if (hash_version != GRAPH_OID_VERSION) {
+	if (hash_version != oid_version()) {
 		error(_("hash version %X does not match version %X"),
-		      hash_version, GRAPH_OID_VERSION);
+		      hash_version, oid_version());
 		goto cleanup_fail;
 	}
 
 	graph = alloc_commit_graph();
 
-	graph->hash_len = GRAPH_OID_LEN;
+	graph->hash_len = the_hash_algo->rawsz;
 	graph->num_chunks = *(unsigned char*)(data + 6);
 	graph->graph_fd = fd;
 	graph->data = graph_map;
@@ -124,7 +124,7 @@ struct commit_graph *load_commit_graph_one(const char *graph_file)
 
 		chunk_lookup += GRAPH_CHUNKLOOKUP_WIDTH;
 
-		if (chunk_offset > graph_size - GIT_MAX_RAWSZ) {
+		if (chunk_offset > graph_size - the_hash_algo->rawsz) {
 			error(_("improper chunk offset %08x%08x"), (uint32_t)(chunk_offset >> 32),
 			      (uint32_t)chunk_offset);
 			goto cleanup_fail;
@@ -692,6 +692,7 @@ void write_commit_graph(const char *obj_dir,
 	int num_chunks;
 	int num_extra_edges;
 	struct commit_list *parent;
+	const unsigned hashsz = the_hash_algo->rawsz;
 
 	oids.nr = 0;
 	oids.alloc = approximate_object_count() / 4;
@@ -812,7 +813,7 @@ void write_commit_graph(const char *obj_dir,
 	hashwrite_be32(f, GRAPH_SIGNATURE);
 
 	hashwrite_u8(f, GRAPH_VERSION);
-	hashwrite_u8(f, GRAPH_OID_VERSION);
+	hashwrite_u8(f, oid_version());
 	hashwrite_u8(f, num_chunks);
 	hashwrite_u8(f, 0); /* unused padding byte */
 
@@ -827,8 +828,8 @@ void write_commit_graph(const char *obj_dir,
 
 	chunk_offsets[0] = 8 + (num_chunks + 1) * GRAPH_CHUNKLOOKUP_WIDTH;
 	chunk_offsets[1] = chunk_offsets[0] + GRAPH_FANOUT_SIZE;
-	chunk_offsets[2] = chunk_offsets[1] + GRAPH_OID_LEN * commits.nr;
-	chunk_offsets[3] = chunk_offsets[2] + (GRAPH_OID_LEN + 16) * commits.nr;
+	chunk_offsets[2] = chunk_offsets[1] + hashsz * commits.nr;
+	chunk_offsets[3] = chunk_offsets[2] + (hashsz + 16) * commits.nr;
 	chunk_offsets[4] = chunk_offsets[3] + 4 * num_extra_edges;
 
 	for (i = 0; i <= num_chunks; i++) {
@@ -841,8 +842,8 @@ void write_commit_graph(const char *obj_dir,
 	}
 
 	write_graph_chunk_fanout(f, commits.list, commits.nr);
-	write_graph_chunk_oids(f, GRAPH_OID_LEN, commits.list, commits.nr);
-	write_graph_chunk_data(f, GRAPH_OID_LEN, commits.list, commits.nr);
+	write_graph_chunk_oids(f, hashsz, commits.list, commits.nr);
+	write_graph_chunk_data(f, hashsz, commits.list, commits.nr);
 	write_graph_chunk_large_edges(f, commits.list, commits.nr);
 
 	close_commit_graph();

Re: [RFC PATCH 08/12] commit-graph: convert to using the_hash_algo

[Derrick Stolee]

On 8/28/2018 8:58 PM, brian m. carlson wrote:
> Instead of using hard-coded constants for object sizes, use
> the_hash_algo to look them up.  In addition, use a function call to look
> up the object ID version and produce the correct value.

The C code in this patch looks good to me. The only issue is that I 
predict failure in the 'git commit-graph verify' tests in 
t5318-commit-graph.sh. Squashing in this commit should help (assuming 
that test_oid works, it doesn't at my current branch):

-->8--

Subject: [PATCH] t5318-commit-graph.sh: use test_oid for HASH_LEN

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
  t/t5318-commit-graph.sh | 2 +-
  1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/t/t5318-commit-graph.sh b/t/t5318-commit-graph.sh
index 6aee861f78..676c1a9ae0 100755
--- a/t/t5318-commit-graph.sh
+++ b/t/t5318-commit-graph.sh
@@ -333,7 +333,7 @@ test_expect_success 'git commit-graph verify' '

  NUM_COMMITS=9
  NUM_OCTOPUS_EDGES=2
-HASH_LEN=20
+HASH_LEN="$(test_oid rawsz)"
  GRAPH_BYTE_VERSION=4
  GRAPH_BYTE_HASH=5
  GRAPH_BYTE_CHUNK_COUNT=6
--
2.19.0.rc1

Re: [RFC PATCH 08/12] commit-graph: convert to using the_hash_algo

[brian m. carlson]

[-- Attachment #1: Type: text/plain, Size: 838 bytes --]

On Wed, Aug 29, 2018 at 08:41:36AM -0400, Derrick Stolee wrote:
> On 8/28/2018 8:58 PM, brian m. carlson wrote:
> > Instead of using hard-coded constants for object sizes, use
> > the_hash_algo to look them up.  In addition, use a function call to look
> > up the object ID version and produce the correct value.
> 
> The C code in this patch looks good to me. The only issue is that I predict
> failure in the 'git commit-graph verify' tests in t5318-commit-graph.sh.
> Squashing in this commit should help (assuming that test_oid works, it
> doesn't at my current branch):

Yeah, this is a separate series not based on the other one.  If I
finally submit this after the other series lands, I'll squash that
change in.

Thanks for the patch.
-- 
brian m. carlson: Houston, Texas, US
OpenPGP: https://keybase.io/bk2204

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 867 bytes --]

Re: [RFC PATCH 08/12] commit-graph: convert to using the_hash_algo

[brian m. carlson]

[-- Attachment #1: Type: text/plain, Size: 716 bytes --]

On Wed, Aug 29, 2018 at 08:41:36AM -0400, Derrick Stolee wrote:
> diff --git a/t/t5318-commit-graph.sh b/t/t5318-commit-graph.sh
> index 6aee861f78..676c1a9ae0 100755
> --- a/t/t5318-commit-graph.sh
> +++ b/t/t5318-commit-graph.sh
> @@ -333,7 +333,7 @@ test_expect_success 'git commit-graph verify' '
> 
>  NUM_COMMITS=9
>  NUM_OCTOPUS_EDGES=2
> -HASH_LEN=20
> +HASH_LEN="$(test_oid rawsz)"
>  GRAPH_BYTE_VERSION=4
>  GRAPH_BYTE_HASH=5
>  GRAPH_BYTE_CHUNK_COUNT=6

I dropped this at the end of my hash-independent fixes series and I
slipped in a use of test_oid_init, which is now required.  Thanks for
the patch.
-- 
brian m. carlson: Houston, Texas, US
OpenPGP: https://keybase.io/bk2204

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 868 bytes --]

[RFC PATCH 09/12] Add a base implementation of SHA-256 support

[brian m. carlson]

SHA-1 is weak and we need to transition to a new hash function.  For
some time, we have referred to this new function as NewHash.

The selection criteria for NewHash specify that it should (a) be 256
bits in length, (b) have high quality implementations available, (c)
should match Git's needs in terms of security, and (d) ideally, be fast
to compute.

SHA-256 has a variety of high quality implementations across various
libraries.  It is implemented by every cryptographic library we support
and is available on every platform and in almost every programming
language.  It is often highly optimized, since it is commonly used in
TLS and elsewhere.  Additionally, there are various command line
utilities that implement it, which is useful for educational and testing
purposes.

SHA-256 is presently considered secure and has received a reasonable
amount of cryptanalysis in the literature.  It is, admittedly, not
resistant to length extension attacks, but Git object storage is immune
to those due to the length field at the beginning.

SHA-256 is somewhat slower to compute than SHA-1 in software.  However,
since our default SHA-1 implementation is collision-detecting, a
reasonable cryptographic library implementation of SHA-256 will actually
be faster than SHA-256.  In addition, modern ARM and AMD processors (and
some Intel processors) contain instructions for implementing SHA-256 in
hardware, making it the fastest possible option.

There are other reasons to select SHA-256.  With signed commits and
tags, it's possible to use SHA-256 for signatures and therefore have to
rely on only one hash algorithm for security.

Add a basic implementation of SHA-256 based off libtomcrypt, which is in
the public domain.  Optimize it and tidy it somewhat.

Wire up SHA-256 in the list of hash algorithms, and add a test that the
algorithm works correctly.

Note that with this patch, it is still not possible to switch to using
SHA-256 in Git.  Additional patches are needed to prepare the code to
handle a larger hash algorithm and further test fixes are needed.

Signed-off-by: brian m. carlson <sandals@crustytoothpaste.net>
---
 Makefile               |   4 +
 cache.h                |  12 ++-
 hash.h                 |  19 ++++-
 sha1-file.c            |  45 +++++++++++
 sha256/block/sha256.c  | 180 +++++++++++++++++++++++++++++++++++++++++
 sha256/block/sha256.h  |  26 ++++++
 t/helper/test-sha256.c |   7 ++
 t/helper/test-tool.c   |   1 +
 t/helper/test-tool.h   |   1 +
 t/t0014-hash.sh        |  25 ++++++
 10 files changed, 316 insertions(+), 4 deletions(-)
 create mode 100644 sha256/block/sha256.c
 create mode 100644 sha256/block/sha256.h
 create mode 100644 t/helper/test-sha256.c

diff --git a/Makefile b/Makefile
index e047dea988..624d852e79 100644
--- a/Makefile
+++ b/Makefile
@@ -733,6 +733,7 @@ TEST_BUILTINS_OBJS += test-run-command.o
 TEST_BUILTINS_OBJS += test-scrap-cache-tree.o
 TEST_BUILTINS_OBJS += test-sha1-array.o
 TEST_BUILTINS_OBJS += test-sha1.o
+TEST_BUILTINS_OBJS += test-sha256.o
 TEST_BUILTINS_OBJS += test-sigchain.o
 TEST_BUILTINS_OBJS += test-strcmp-offset.o
 TEST_BUILTINS_OBJS += test-string-list.o
@@ -1623,6 +1624,9 @@ endif
 endif
 endif
 
+LIB_OBJS += sha256/block/sha256.o
+BASIC_CFLAGS += -DSHA256_BLK
+
 ifdef SHA1_MAX_BLOCK_SIZE
 	LIB_OBJS += compat/sha1-chunked.o
 	BASIC_CFLAGS += -DSHA1_MAX_BLOCK_SIZE="$(SHA1_MAX_BLOCK_SIZE)"
diff --git a/cache.h b/cache.h
index c1b5a7a337..5a35497b34 100644
--- a/cache.h
+++ b/cache.h
@@ -48,11 +48,17 @@ unsigned long git_deflate_bound(git_zstream *, unsigned long);
 /* The block size of SHA-1. */
 #define GIT_SHA1_BLKSZ 64
 
+/* The length in bytes and in hex digits of an object name (SHA-256 value). */
+#define GIT_SHA256_RAWSZ 32
+#define GIT_SHA256_HEXSZ (2 * GIT_SHA256_RAWSZ)
+/* The block size of SHA-256. */
+#define GIT_SHA256_BLKSZ 64
+
 /* The length in byte and in hex digits of the largest possible hash value. */
-#define GIT_MAX_RAWSZ GIT_SHA1_RAWSZ
-#define GIT_MAX_HEXSZ GIT_SHA1_HEXSZ
+#define GIT_MAX_RAWSZ GIT_SHA256_RAWSZ
+#define GIT_MAX_HEXSZ GIT_SHA256_HEXSZ
 /* The largest possible block size for any supported hash. */
-#define GIT_MAX_BLKSZ GIT_SHA1_BLKSZ
+#define GIT_MAX_BLKSZ GIT_SHA256_BLKSZ
 
 struct object_id {
 	unsigned char hash[GIT_MAX_RAWSZ];
diff --git a/hash.h b/hash.h
index 46dff69eb3..88d18896d7 100644
--- a/hash.h
+++ b/hash.h
@@ -15,6 +15,8 @@
 #include "block-sha1/sha1.h"
 #endif
 
+#include "sha256/block/sha256.h"
+
 #ifndef platform_SHA_CTX
 /*
  * platform's underlying implementation of SHA-1; could be OpenSSL,
@@ -34,6 +36,18 @@
 #define git_SHA1_Update		platform_SHA1_Update
 #define git_SHA1_Final		platform_SHA1_Final
 
+#ifndef platform_SHA256_CTX
+#define platform_SHA256_CTX	SHA256_CTX
+#define platform_SHA256_Init	SHA256_Init
+#define platform_SHA256_Update	SHA256_Update
+#define platform_SHA256_Final	SHA256_Final
+#endif
+
+#define git_SHA256_CTX		platform_SHA256_CTX
+#define git_SHA256_Init		platform_SHA256_Init
+#define git_SHA256_Update	platform_SHA256_Update
+#define git_SHA256_Final	platform_SHA256_Final
+
 #ifdef SHA1_MAX_BLOCK_SIZE
 #include "compat/sha1-chunked.h"
 #undef git_SHA1_Update
@@ -52,12 +66,15 @@
 #define GIT_HASH_UNKNOWN 0
 /* SHA-1 */
 #define GIT_HASH_SHA1 1
+/* SHA-256  */
+#define GIT_HASH_SHA256 2
 /* Number of algorithms supported (including unknown). */
-#define GIT_HASH_NALGOS (GIT_HASH_SHA1 + 1)
+#define GIT_HASH_NALGOS (GIT_HASH_SHA256 + 1)
 
 /* A suitably aligned type for stack allocations of hash contexts. */
 union git_hash_ctx {
 	git_SHA_CTX sha1;
+	git_SHA256_CTX sha256;
 };
 typedef union git_hash_ctx git_hash_ctx;
 
diff --git a/sha1-file.c b/sha1-file.c
index a1ad1b8268..495c890c80 100644
--- a/sha1-file.c
+++ b/sha1-file.c
@@ -40,10 +40,20 @@
 #define EMPTY_TREE_SHA1_BIN_LITERAL \
 	 "\x4b\x82\x5d\xc6\x42\xcb\x6e\xb9\xa0\x60" \
 	 "\xe5\x4b\xf8\xd6\x92\x88\xfb\xee\x49\x04"
+#define EMPTY_TREE_SHA256_BIN_LITERAL \
+	"\x6e\xf1\x9b\x41\x22\x5c\x53\x69\xf1\xc1" \
+	"\x04\xd4\x5d\x8d\x85\xef\xa9\xb0\x57\xb5" \
+	"\x3b\x14\xb4\xb9\xb9\x39\xdd\x74\xde\xcc" \
+	"\x53\x21"
 
 #define EMPTY_BLOB_SHA1_BIN_LITERAL \
 	"\xe6\x9d\xe2\x9b\xb2\xd1\xd6\x43\x4b\x8b" \
 	"\x29\xae\x77\x5a\xd8\xc2\xe4\x8c\x53\x91"
+#define EMPTY_BLOB_SHA256_BIN_LITERAL \
+	"\x47\x3a\x0f\x4c\x3b\xe8\xa9\x36\x81\xa2" \
+	"\x67\xe3\xb1\xe9\xa7\xdc\xda\x11\x85\x43" \
+	"\x6f\xe1\x41\xf7\x74\x91\x20\xa3\x03\x72" \
+	"\x18\x13"
 
 const unsigned char null_sha1[GIT_MAX_RAWSZ];
 const struct object_id null_oid;
@@ -53,6 +63,12 @@ static const struct object_id empty_tree_oid = {
 static const struct object_id empty_blob_oid = {
 	EMPTY_BLOB_SHA1_BIN_LITERAL
 };
+static const struct object_id empty_tree_oid_sha256 = {
+	EMPTY_TREE_SHA256_BIN_LITERAL
+};
+static const struct object_id empty_blob_oid_sha256 = {
+	EMPTY_BLOB_SHA256_BIN_LITERAL
+};
 
 static void git_hash_sha1_init(git_hash_ctx *ctx)
 {
@@ -69,6 +85,22 @@ static void git_hash_sha1_final(unsigned char *hash, git_hash_ctx *ctx)
 	git_SHA1_Final(hash, &ctx->sha1);
 }
 
+
+static void git_hash_sha256_init(git_hash_ctx *ctx)
+{
+	git_SHA256_Init(&ctx->sha256);
+}
+
+static void git_hash_sha256_update(git_hash_ctx *ctx, const void *data, size_t len)
+{
+	git_SHA256_Update(&ctx->sha256, data, len);
+}
+
+static void git_hash_sha256_final(unsigned char *hash, git_hash_ctx *ctx)
+{
+	git_SHA256_Final(hash, &ctx->sha256);
+}
+
 static void git_hash_unknown_init(git_hash_ctx *ctx)
 {
 	BUG("trying to init unknown hash");
@@ -110,6 +142,19 @@ const struct git_hash_algo hash_algos[GIT_HASH_NALGOS] = {
 		&empty_tree_oid,
 		&empty_blob_oid,
 	},
+	{
+		"sha256",
+		/* "s256", big-endian */
+		0x73323536,
+		GIT_SHA256_RAWSZ,
+		GIT_SHA256_HEXSZ,
+		GIT_SHA256_BLKSZ,
+		git_hash_sha256_init,
+		git_hash_sha256_update,
+		git_hash_sha256_final,
+		&empty_tree_oid_sha256,
+		&empty_blob_oid_sha256,
+	}
 };
 
 const char *empty_tree_oid_hex(void)
diff --git a/sha256/block/sha256.c b/sha256/block/sha256.c
new file mode 100644
index 0000000000..18350c161a
--- /dev/null
+++ b/sha256/block/sha256.c
@@ -0,0 +1,180 @@
+#include "git-compat-util.h"
+#include "./sha256.h"
+
+#define BLKSIZE blk_SHA256_BLKSIZE
+
+void blk_SHA256_Init(blk_SHA256_CTX *ctx)
+{
+	ctx->offset = 0;
+	ctx->length = 0;
+	ctx->state[0] = 0x6A09E667UL;
+	ctx->state[1] = 0xBB67AE85UL;
+	ctx->state[2] = 0x3C6EF372UL;
+	ctx->state[3] = 0xA54FF53AUL;
+	ctx->state[4] = 0x510E527FUL;
+	ctx->state[5] = 0x9B05688CUL;
+	ctx->state[6] = 0x1F83D9ABUL;
+	ctx->state[7] = 0x5BE0CD19UL;
+}
+
+static inline uint32_t ror(uint32_t x, unsigned n)
+{
+	return (x >> n) | (x << (32 - n));
+}
+
+#define Ch(x,y,z)       (z ^ (x & (y ^ z)))
+#define Maj(x,y,z)      (((x | y) & z) | (x & y))
+#define S(x, n)         ror((x),(n))
+#define R(x, n)         ((x)>>(n))
+#define Sigma0(x)       (S(x, 2) ^ S(x, 13) ^ S(x, 22))
+#define Sigma1(x)       (S(x, 6) ^ S(x, 11) ^ S(x, 25))
+#define Gamma0(x)       (S(x, 7) ^ S(x, 18) ^ R(x, 3))
+#define Gamma1(x)       (S(x, 17) ^ S(x, 19) ^ R(x, 10))
+
+static void blk_SHA256_Transform(blk_SHA256_CTX *ctx, const unsigned char *buf)
+{
+
+	uint32_t S[8], W[64], t0, t1;
+	int i;
+
+	/* copy state into S */
+	for (i = 0; i < 8; i++) {
+		S[i] = ctx->state[i];
+	}
+
+	/* copy the state into 512-bits into W[0..15] */
+	for (i = 0; i < 16; i++, buf += sizeof(uint32_t)) {
+		W[i] = get_be32(buf);
+	}
+
+	/* fill W[16..63] */
+	for (i = 16; i < 64; i++) {
+		W[i] = Gamma1(W[i - 2]) + W[i - 7] + Gamma0(W[i - 15]) + W[i - 16];
+	}
+
+#define RND(a,b,c,d,e,f,g,h,i,ki)                    \
+	t0 = h + Sigma1(e) + Ch(e, f, g) + ki + W[i];   \
+	t1 = Sigma0(a) + Maj(a, b, c);                  \
+	d += t0;                                        \
+	h  = t0 + t1;
+
+	RND(S[0],S[1],S[2],S[3],S[4],S[5],S[6],S[7],0,0x428a2f98);
+	RND(S[7],S[0],S[1],S[2],S[3],S[4],S[5],S[6],1,0x71374491);
+	RND(S[6],S[7],S[0],S[1],S[2],S[3],S[4],S[5],2,0xb5c0fbcf);
+	RND(S[5],S[6],S[7],S[0],S[1],S[2],S[3],S[4],3,0xe9b5dba5);
+	RND(S[4],S[5],S[6],S[7],S[0],S[1],S[2],S[3],4,0x3956c25b);
+	RND(S[3],S[4],S[5],S[6],S[7],S[0],S[1],S[2],5,0x59f111f1);
+	RND(S[2],S[3],S[4],S[5],S[6],S[7],S[0],S[1],6,0x923f82a4);
+	RND(S[1],S[2],S[3],S[4],S[5],S[6],S[7],S[0],7,0xab1c5ed5);
+	RND(S[0],S[1],S[2],S[3],S[4],S[5],S[6],S[7],8,0xd807aa98);
+	RND(S[7],S[0],S[1],S[2],S[3],S[4],S[5],S[6],9,0x12835b01);
+	RND(S[6],S[7],S[0],S[1],S[2],S[3],S[4],S[5],10,0x243185be);
+	RND(S[5],S[6],S[7],S[0],S[1],S[2],S[3],S[4],11,0x550c7dc3);
+	RND(S[4],S[5],S[6],S[7],S[0],S[1],S[2],S[3],12,0x72be5d74);
+	RND(S[3],S[4],S[5],S[6],S[7],S[0],S[1],S[2],13,0x80deb1fe);
+	RND(S[2],S[3],S[4],S[5],S[6],S[7],S[0],S[1],14,0x9bdc06a7);
+	RND(S[1],S[2],S[3],S[4],S[5],S[6],S[7],S[0],15,0xc19bf174);
+	RND(S[0],S[1],S[2],S[3],S[4],S[5],S[6],S[7],16,0xe49b69c1);
+	RND(S[7],S[0],S[1],S[2],S[3],S[4],S[5],S[6],17,0xefbe4786);
+	RND(S[6],S[7],S[0],S[1],S[2],S[3],S[4],S[5],18,0x0fc19dc6);
+	RND(S[5],S[6],S[7],S[0],S[1],S[2],S[3],S[4],19,0x240ca1cc);
+	RND(S[4],S[5],S[6],S[7],S[0],S[1],S[2],S[3],20,0x2de92c6f);
+	RND(S[3],S[4],S[5],S[6],S[7],S[0],S[1],S[2],21,0x4a7484aa);
+	RND(S[2],S[3],S[4],S[5],S[6],S[7],S[0],S[1],22,0x5cb0a9dc);
+	RND(S[1],S[2],S[3],S[4],S[5],S[6],S[7],S[0],23,0x76f988da);
+	RND(S[0],S[1],S[2],S[3],S[4],S[5],S[6],S[7],24,0x983e5152);
+	RND(S[7],S[0],S[1],S[2],S[3],S[4],S[5],S[6],25,0xa831c66d);
+	RND(S[6],S[7],S[0],S[1],S[2],S[3],S[4],S[5],26,0xb00327c8);
+	RND(S[5],S[6],S[7],S[0],S[1],S[2],S[3],S[4],27,0xbf597fc7);
+	RND(S[4],S[5],S[6],S[7],S[0],S[1],S[2],S[3],28,0xc6e00bf3);
+	RND(S[3],S[4],S[5],S[6],S[7],S[0],S[1],S[2],29,0xd5a79147);
+	RND(S[2],S[3],S[4],S[5],S[6],S[7],S[0],S[1],30,0x06ca6351);
+	RND(S[1],S[2],S[3],S[4],S[5],S[6],S[7],S[0],31,0x14292967);
+	RND(S[0],S[1],S[2],S[3],S[4],S[5],S[6],S[7],32,0x27b70a85);
+	RND(S[7],S[0],S[1],S[2],S[3],S[4],S[5],S[6],33,0x2e1b2138);
+	RND(S[6],S[7],S[0],S[1],S[2],S[3],S[4],S[5],34,0x4d2c6dfc);
+	RND(S[5],S[6],S[7],S[0],S[1],S[2],S[3],S[4],35,0x53380d13);
+	RND(S[4],S[5],S[6],S[7],S[0],S[1],S[2],S[3],36,0x650a7354);
+	RND(S[3],S[4],S[5],S[6],S[7],S[0],S[1],S[2],37,0x766a0abb);
+	RND(S[2],S[3],S[4],S[5],S[6],S[7],S[0],S[1],38,0x81c2c92e);
+	RND(S[1],S[2],S[3],S[4],S[5],S[6],S[7],S[0],39,0x92722c85);
+	RND(S[0],S[1],S[2],S[3],S[4],S[5],S[6],S[7],40,0xa2bfe8a1);
+	RND(S[7],S[0],S[1],S[2],S[3],S[4],S[5],S[6],41,0xa81a664b);
+	RND(S[6],S[7],S[0],S[1],S[2],S[3],S[4],S[5],42,0xc24b8b70);
+	RND(S[5],S[6],S[7],S[0],S[1],S[2],S[3],S[4],43,0xc76c51a3);
+	RND(S[4],S[5],S[6],S[7],S[0],S[1],S[2],S[3],44,0xd192e819);
+	RND(S[3],S[4],S[5],S[6],S[7],S[0],S[1],S[2],45,0xd6990624);
+	RND(S[2],S[3],S[4],S[5],S[6],S[7],S[0],S[1],46,0xf40e3585);
+	RND(S[1],S[2],S[3],S[4],S[5],S[6],S[7],S[0],47,0x106aa070);
+	RND(S[0],S[1],S[2],S[3],S[4],S[5],S[6],S[7],48,0x19a4c116);
+	RND(S[7],S[0],S[1],S[2],S[3],S[4],S[5],S[6],49,0x1e376c08);
+	RND(S[6],S[7],S[0],S[1],S[2],S[3],S[4],S[5],50,0x2748774c);
+	RND(S[5],S[6],S[7],S[0],S[1],S[2],S[3],S[4],51,0x34b0bcb5);
+	RND(S[4],S[5],S[6],S[7],S[0],S[1],S[2],S[3],52,0x391c0cb3);
+	RND(S[3],S[4],S[5],S[6],S[7],S[0],S[1],S[2],53,0x4ed8aa4a);
+	RND(S[2],S[3],S[4],S[5],S[6],S[7],S[0],S[1],54,0x5b9cca4f);
+	RND(S[1],S[2],S[3],S[4],S[5],S[6],S[7],S[0],55,0x682e6ff3);
+	RND(S[0],S[1],S[2],S[3],S[4],S[5],S[6],S[7],56,0x748f82ee);
+	RND(S[7],S[0],S[1],S[2],S[3],S[4],S[5],S[6],57,0x78a5636f);
+	RND(S[6],S[7],S[0],S[1],S[2],S[3],S[4],S[5],58,0x84c87814);
+	RND(S[5],S[6],S[7],S[0],S[1],S[2],S[3],S[4],59,0x8cc70208);
+	RND(S[4],S[5],S[6],S[7],S[0],S[1],S[2],S[3],60,0x90befffa);
+	RND(S[3],S[4],S[5],S[6],S[7],S[0],S[1],S[2],61,0xa4506ceb);
+	RND(S[2],S[3],S[4],S[5],S[6],S[7],S[0],S[1],62,0xbef9a3f7);
+	RND(S[1],S[2],S[3],S[4],S[5],S[6],S[7],S[0],63,0xc67178f2);
+
+#undef RND
+
+	for (i = 0; i < 8; i++) {
+		ctx->state[i] = ctx->state[i] + S[i];
+	}
+}
+
+#define MIN(x, y) ((x) < (y) ? (x) : (y))
+void blk_SHA256_Update(blk_SHA256_CTX *ctx, const void *data, size_t len)
+{
+	const unsigned char *in = data;
+	size_t n;
+	ctx->length += len;
+	while (len > 0) {
+		if (!ctx->offset && len >= BLKSIZE) {
+			blk_SHA256_Transform(ctx, in);
+			in += BLKSIZE;
+			len -= BLKSIZE;
+		} else {
+			n = MIN(len, (BLKSIZE - ctx->offset));
+			memcpy(ctx->buf + ctx->offset, in, n);
+			ctx->offset += n;
+			in += n;
+			len -= n;
+			if (ctx->offset == BLKSIZE) {
+				blk_SHA256_Transform(ctx, ctx->buf);
+				ctx->offset = 0;
+			}
+		}
+	}
+}
+
+void blk_SHA256_Final(unsigned char *digest, blk_SHA256_CTX *ctx)
+{
+	const unsigned trip = BLKSIZE - sizeof(ctx->length);
+	int i;
+
+	ctx->length <<= 3;
+	ctx->buf[ctx->offset++] = 0x80;
+
+	if (ctx->offset > trip) {
+		memset(ctx->buf + ctx->offset, 0, BLKSIZE - ctx->offset);
+		blk_SHA256_Transform(ctx, ctx->buf);
+		ctx->offset = 0;
+	}
+
+	memset(ctx->buf + ctx->offset, 0, BLKSIZE - ctx->offset - sizeof(ctx->length));
+
+	put_be64(ctx->buf + trip, ctx->length);
+	blk_SHA256_Transform(ctx, ctx->buf);
+
+	/* copy output */
+	for (i = 0; i < 8; i++, digest += sizeof(uint32_t))
+		put_be32(digest, ctx->state[i]);
+}
diff --git a/sha256/block/sha256.h b/sha256/block/sha256.h
new file mode 100644
index 0000000000..ad8b178ad3
--- /dev/null
+++ b/sha256/block/sha256.h
@@ -0,0 +1,26 @@
+#ifndef SHA256_BLOCK_SHA256_H
+#define SHA256_BLOCK_SHA256_H
+
+#include "git-compat-util.h"
+
+#define blk_SHA256_BLKSIZE 64
+
+struct blk_SHA256_CTX {
+	uint32_t state[8];
+	uint64_t length;
+	uint32_t offset;
+	uint8_t buf[blk_SHA256_BLKSIZE];
+};
+
+typedef struct blk_SHA256_CTX blk_SHA256_CTX;
+
+void blk_SHA256_Init(blk_SHA256_CTX *ctx);
+void blk_SHA256_Update(blk_SHA256_CTX *ctx, const void *data, size_t len);
+void blk_SHA256_Final(unsigned char *digest, blk_SHA256_CTX *ctx);
+
+#define platform_SHA256_CTX blk_SHA256_CTX
+#define platform_SHA256_Init blk_SHA256_Init
+#define platform_SHA256_Update blk_SHA256_Update
+#define platform_SHA256_Final blk_SHA256_Final
+
+#endif
diff --git a/t/helper/test-sha256.c b/t/helper/test-sha256.c
new file mode 100644
index 0000000000..0ac6a99d5f
--- /dev/null
+++ b/t/helper/test-sha256.c
@@ -0,0 +1,7 @@
+#include "test-tool.h"
+#include "cache.h"
+
+int cmd__sha256(int ac, const char **av)
+{
+	return cmd_hash_impl(ac, av, GIT_HASH_SHA256);
+}
diff --git a/t/helper/test-tool.c b/t/helper/test-tool.c
index c0d3eecc36..f189c18453 100644
--- a/t/helper/test-tool.c
+++ b/t/helper/test-tool.c
@@ -37,6 +37,7 @@ static struct test_cmd cmds[] = {
 	{ "scrap-cache-tree", cmd__scrap_cache_tree },
 	{ "sha1-array", cmd__sha1_array },
 	{ "sha1", cmd__sha1 },
+	{ "sha256", cmd__sha256 },
 	{ "sigchain", cmd__sigchain },
 	{ "strcmp-offset", cmd__strcmp_offset },
 	{ "string-list", cmd__string_list },
diff --git a/t/helper/test-tool.h b/t/helper/test-tool.h
index abe3a253d5..2bc4efb68b 100644
--- a/t/helper/test-tool.h
+++ b/t/helper/test-tool.h
@@ -33,6 +33,7 @@ int cmd__run_command(int argc, const char **argv);
 int cmd__scrap_cache_tree(int argc, const char **argv);
 int cmd__sha1_array(int argc, const char **argv);
 int cmd__sha1(int argc, const char **argv);
+int cmd__sha256(int argc, const char **argv);
 int cmd__sigchain(int argc, const char **argv);
 int cmd__strcmp_offset(int argc, const char **argv);
 int cmd__string_list(int argc, const char **argv);
diff --git a/t/t0014-hash.sh b/t/t0014-hash.sh
index 8e763c2c3d..f8e639743f 100755
--- a/t/t0014-hash.sh
+++ b/t/t0014-hash.sh
@@ -26,4 +26,29 @@ test_expect_success 'test basic SHA-1 hash values' '
 	grep 4b825dc642cb6eb9a060e54bf8d69288fbee4904 actual
 '
 
+test_expect_success 'test basic SHA-256 hash values' '
+	test-tool sha256 </dev/null >actual &&
+	grep e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855 actual &&
+	printf "a" | test-tool sha256 >actual &&
+	grep ca978112ca1bbdcafac231b39a23dc4da786eff8147c4e72b9807785afee48bb actual &&
+	printf "abc" | test-tool sha256 >actual &&
+	grep ba7816bf8f01cfea414140de5dae2223b00361a396177a9cb410ff61f20015ad actual &&
+	printf "message digest" | test-tool sha256 >actual &&
+	grep f7846f55cf23e14eebeab5b4e1550cad5b509e3348fbc4efa3a1413d393cb650 actual &&
+	printf "abcdefghijklmnopqrstuvwxyz" | test-tool sha256 >actual &&
+	grep 71c480df93d6ae2f1efad1447c66c9525e316218cf51fc8d9ed832f2daf18b73 actual &&
+	perl -E "for (1..100000) { print q{aaaaaaaaaa}; }" | \
+		test-tool sha256 >actual &&
+	grep cdc76e5c9914fb9281a1c7e284d73e67f1809a48a497200e046d39ccc7112cd0 actual &&
+	perl -E "for (1..100000) { print q{abcdefghijklmnopqrstuvwxyz}; }" | \
+		test-tool sha256 >actual &&
+	grep e406ba321ca712ad35a698bf0af8d61fc4dc40eca6bdcea4697962724ccbde35 actual &&
+	printf "blob 0\0" | test-tool sha256 >actual &&
+	grep 473a0f4c3be8a93681a267e3b1e9a7dcda1185436fe141f7749120a303721813 actual &&
+	printf "blob 3\0abc" | test-tool sha256 >actual &&
+	grep c1cf6e465077930e88dc5136641d402f72a229ddd996f627d60e9639eaba35a6 actual &&
+	printf "tree 0\0" | test-tool sha256 >actual &&
+	grep 6ef19b41225c5369f1c104d45d8d85efa9b057b53b14b4b9b939dd74decc5321 actual
+'
+
 test_done

Re: [RFC PATCH 09/12] Add a base implementation of SHA-256 support

[Ævar Arnfjörð Bjarmason]

On Wed, Aug 29 2018, brian m. carlson wrote:

> SHA-1 is weak and we need to transition to a new hash function.  For
> some time, we have referred to this new function as NewHash.
>
> The selection criteria for NewHash specify that it should (a) be 256
> bits in length, (b) have high quality implementations available, (c)
> should match Git's needs in terms of security, and (d) ideally, be fast
> to compute.
>
> SHA-256 has a variety of high quality implementations across various
> libraries.  It is implemented by every cryptographic library we support
> and is available on every platform and in almost every programming
> language.  It is often highly optimized, since it is commonly used in
> TLS and elsewhere.  Additionally, there are various command line
> utilities that implement it, which is useful for educational and testing
> purposes.
>
> SHA-256 is presently considered secure and has received a reasonable
> amount of cryptanalysis in the literature.  It is, admittedly, not
> resistant to length extension attacks, but Git object storage is immune
> to those due to the length field at the beginning.
>
> SHA-256 is somewhat slower to compute than SHA-1 in software.  However,
> since our default SHA-1 implementation is collision-detecting, a
> reasonable cryptographic library implementation of SHA-256 will actually
> be faster than SHA-256.  In addition, modern ARM and AMD processors (and
> some Intel processors) contain instructions for implementing SHA-256 in
> hardware, making it the fastest possible option.
>
> There are other reasons to select SHA-256.  With signed commits and
> tags, it's possible to use SHA-256 for signatures and therefore have to
> rely on only one hash algorithm for security.

None of this is wrong, but I think this would be better off as a simple
"See Documentation/technical/hash-function-transition.txt for why we're
switching to SHA-256", and to the extent that something is said here
that isn't said there it could be a patch to amend that document.

> Add a basic implementation of SHA-256 based off libtomcrypt, which is in
> the public domain.  Optimize it and tidy it somewhat.

For future changes & maintenance of this, let's do that in two
steps. One where we add the upstream code as-is, and another where the
tidying / cleanup / git specific stuff is wired, which makes it easy to
audit upstream as-is v.s. our changes in isolation. Also in the first of
those commits, say in the commit message "add a [libtomcrypt] copy from
such-and-such a URL at such-and-such a version", so that it's easy to
reproduce the import & find out how to re-update it.

Is this something we see ourselves perma-forking? Or as with sha1dc are
we likely to pull in upstream changes from time-to-time?SHA256 obiously
isn't under active development, but there's been some churn in the
upstream code since it was added, and if you're doing some optimizing /
tidying that's presumably something upstream could benefit from as well,
as well as just us being nicer open source citizens feeding
e.g. portability fixes to upstream (since git tends to get ported a
lot).

So I wonder if we can't convince them to add a few macros to their code,
and then do something like what I did in a0103914c2 ("sha1dc: update
from upstream", 2017-05-20) for sha1dc allowing us to use their code
as-is with some defines in the Makefile, which both makes it easier to
update, and sets up a process where our default approach is to submit
changes upstream, instead of working on our perma-fork.

Re: [RFC PATCH 09/12] Add a base implementation of SHA-256 support

[brian m. carlson]

[-- Attachment #1: Type: text/plain, Size: 4758 bytes --]

On Wed, Aug 29, 2018 at 11:32:08AM +0200, Ævar Arnfjörð Bjarmason wrote:
> 
> On Wed, Aug 29 2018, brian m. carlson wrote:
> 
> > SHA-1 is weak and we need to transition to a new hash function.  For
> > some time, we have referred to this new function as NewHash.
> >
> > The selection criteria for NewHash specify that it should (a) be 256
> > bits in length, (b) have high quality implementations available, (c)
> > should match Git's needs in terms of security, and (d) ideally, be fast
> > to compute.
> >
> > SHA-256 has a variety of high quality implementations across various
> > libraries.  It is implemented by every cryptographic library we support
> > and is available on every platform and in almost every programming
> > language.  It is often highly optimized, since it is commonly used in
> > TLS and elsewhere.  Additionally, there are various command line
> > utilities that implement it, which is useful for educational and testing
> > purposes.
> >
> > SHA-256 is presently considered secure and has received a reasonable
> > amount of cryptanalysis in the literature.  It is, admittedly, not
> > resistant to length extension attacks, but Git object storage is immune
> > to those due to the length field at the beginning.
> >
> > SHA-256 is somewhat slower to compute than SHA-1 in software.  However,
> > since our default SHA-1 implementation is collision-detecting, a
> > reasonable cryptographic library implementation of SHA-256 will actually
> > be faster than SHA-256.  In addition, modern ARM and AMD processors (and
> > some Intel processors) contain instructions for implementing SHA-256 in
> > hardware, making it the fastest possible option.
> >
> > There are other reasons to select SHA-256.  With signed commits and
> > tags, it's possible to use SHA-256 for signatures and therefore have to
> > rely on only one hash algorithm for security.
> 
> None of this is wrong, but I think this would be better off as a simple
> "See Documentation/technical/hash-function-transition.txt for why we're
> switching to SHA-256", and to the extent that something is said here
> that isn't said there it could be a patch to amend that document.

I can certainly shorten this somewhat.  I wrote this back when there
wasn't a consensus on hash algorithm and Junio was going to leave it to
me to make a decision.  I was therefore obligated to provide a coherent
rationale for that decision.

> > Add a basic implementation of SHA-256 based off libtomcrypt, which is in
> > the public domain.  Optimize it and tidy it somewhat.
> 
> For future changes & maintenance of this, let's do that in two
> steps. One where we add the upstream code as-is, and another where the
> tidying / cleanup / git specific stuff is wired, which makes it easy to
> audit upstream as-is v.s. our changes in isolation. Also in the first of
> those commits, say in the commit message "add a [libtomcrypt] copy from
> such-and-such a URL at such-and-such a version", so that it's easy to
> reproduce the import & find out how to re-update it.

Doing what you suggest basically means importing a large amount of
libtomcrypt into our codebase, since there are a large number of reused
macros all over libtomcrypt (such as for processing a generic hash and
for memcpy).

This isn't surprising for a general purpose crypto library, but I did a
decent amount to change it, condense it into a small number of files,
and make it meet our code standards.  The phrase "somewhat" may have
been an understatement.

This is also why I added tests: because I'm human and making a small
change in a crypto library can result in wrong output very quickly.

> Is this something we see ourselves perma-forking? Or as with sha1dc are
> we likely to pull in upstream changes from time-to-time?SHA256 obiously
> isn't under active development, but there's been some churn in the
> upstream code since it was added, and if you're doing some optimizing /
> tidying that's presumably something upstream could benefit from as well,
> as well as just us being nicer open source citizens feeding
> e.g. portability fixes to upstream (since git tends to get ported a
> lot).

This is a permafork.  We need a basic SHA-256 implementation, and this
one was faster than the one I'd written some time ago.  Similarly to the
block-sha1 implementation, I see this as something that we'll be
shipping forever with little updating.

I expect with the amount of changes we're making, they're unlikely to
want our code.  Also, any changes to our code would be under the GPLv2,
which would be unappealing to a public domain library.
-- 
brian m. carlson: Houston, Texas, US
OpenPGP: https://keybase.io/bk2204

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 867 bytes --]

Re: [RFC PATCH 09/12] Add a base implementation of SHA-256 support

[Derrick Stolee]

On 8/28/2018 8:58 PM, brian m. carlson wrote:
> SHA-256 is somewhat slower to compute than SHA-1 in software.  However,
> since our default SHA-1 implementation is collision-detecting, a
> reasonable cryptographic library implementation of SHA-256 will actually
> be faster than SHA-256.

Nit: do you mean "faster than SHA-1DC"?

[RFC PATCH 10/12] sha256: add an SHA-256 implementation using libgcrypt

[brian m. carlson]

Generally, one gets better performance out of cryptographic routines
written in assembly than C, and this is also true for SHA-256.  In
addition, most Linux distributions cannot distribute Git linked against
OpenSSL for licensing reasons.

Most systems with GnuPG will also have libgcrypt, since it is a
dependency of GnuPG.  libgcrypt is also faster than the SHA1DC
implementation for messages of a few KiB and larger. It is licensed
under the LGPL 2.1, which is compatible with the GPL.

Add an implementation of SHA-256 that uses libgcrypt.

Signed-off-by: brian m. carlson <sandals@crustytoothpaste.net>
---
 Makefile        | 13 +++++++++++--
 hash.h          |  4 ++++
 sha256/gcrypt.h | 30 ++++++++++++++++++++++++++++++
 3 files changed, 45 insertions(+), 2 deletions(-)
 create mode 100644 sha256/gcrypt.h

diff --git a/Makefile b/Makefile
index 624d852e79..86867af083 100644
--- a/Makefile
+++ b/Makefile
@@ -179,6 +179,10 @@ all::
 # in one call to the platform's SHA1_Update(). e.g. APPLE_COMMON_CRYPTO
 # wants 'SHA1_MAX_BLOCK_SIZE=1024L*1024L*1024L' defined.
 #
+# Define BLK_SHA256 to use the built-in SHA-256 routines.
+#
+# Define GCRYPT_SHA256 to use the SHA-256 routines in libgcrypt.
+#
 # Define NEEDS_CRYPTO_WITH_SSL if you need -lcrypto when using -lssl (Darwin).
 #
 # Define NEEDS_SSL_WITH_CRYPTO if you need -lssl when using -lcrypto (Darwin).
@@ -1624,8 +1628,13 @@ endif
 endif
 endif
 
-LIB_OBJS += sha256/block/sha256.o
-BASIC_CFLAGS += -DSHA256_BLK
+ifdef GCRYPT_SHA256
+	BASIC_CFLAGS += -DSHA256_GCRYPT
+	EXTLIBS += -lgcrypt
+else
+	LIB_OBJS += sha256/block/sha256.o
+	BASIC_CFLAGS += -DSHA256_BLK
+endif
 
 ifdef SHA1_MAX_BLOCK_SIZE
 	LIB_OBJS += compat/sha1-chunked.o
diff --git a/hash.h b/hash.h
index 88d18896d7..9df562f2f6 100644
--- a/hash.h
+++ b/hash.h
@@ -15,7 +15,11 @@
 #include "block-sha1/sha1.h"
 #endif
 
+#if defined(SHA256_GCRYPT)
+#include "sha256/gcrypt.h"
+#else
 #include "sha256/block/sha256.h"
+#endif
 
 #ifndef platform_SHA_CTX
 /*
diff --git a/sha256/gcrypt.h b/sha256/gcrypt.h
new file mode 100644
index 0000000000..09bd8bb200
--- /dev/null
+++ b/sha256/gcrypt.h
@@ -0,0 +1,30 @@
+#ifndef SHA256_GCRYPT_H
+#define SHA256_GCRYPT_H
+
+#include <gcrypt.h>
+
+#define SHA256_DIGEST_SIZE 32
+
+typedef gcry_md_hd_t gcrypt_SHA256_CTX;
+
+inline void gcrypt_SHA256_Init(gcrypt_SHA256_CTX *ctx)
+{
+	gcry_md_open(ctx, GCRY_MD_SHA256, 0);
+}
+
+inline void gcrypt_SHA256_Update(gcrypt_SHA256_CTX *ctx, const void *data, size_t len)
+{
+	gcry_md_write(*ctx, data, len);
+}
+
+inline void gcrypt_SHA256_Final(unsigned char *digest, gcrypt_SHA256_CTX *ctx)
+{
+	memcpy(digest, gcry_md_read(*ctx, GCRY_MD_SHA256), SHA256_DIGEST_SIZE);
+}
+
+#define platform_SHA256_CTX gcrypt_SHA256_CTX
+#define platform_SHA256_Init gcrypt_SHA256_Init
+#define platform_SHA256_Update gcrypt_SHA256_Update
+#define platform_SHA256_Final gcrypt_SHA256_Final
+
+#endif

Re: [RFC PATCH 10/12] sha256: add an SHA-256 implementation using libgcrypt

[Ævar Arnfjörð Bjarmason]

On Wed, Aug 29 2018, brian m. carlson wrote:

> Generally, one gets better performance out of cryptographic routines
> written in assembly than C, and this is also true for SHA-256

It makes sense to have a libgcrypt implementation...

> In addition, most Linux distributions cannot distribute Git linked
> against OpenSSL for licensing reasons.

...but I'm curious to know what licensing reasons these are, e.g. Debian
who's usually the most strict about these things distributes git linked
to OpenSSL:

    $ dpkg -S /usr/lib/git-core/git-imap-send; apt policy git 2>/dev/null|grep -F '***'; ldd -r /usr/lib/git-core/git-imap-send|grep ssl; uname -m
    git: /usr/lib/git-core/git-imap-send
     *** 1:2.19.0~rc1+next.20180828-1 1001
            libssl.so.1.0.2 => /usr/lib/x86_64-linux-gnu/libssl.so.1.0.2 (0x00007fd3cc8bb000)
    x86_64
    $ dpkg -S /usr/lib/x86_64-linux-gnu/libssl.so.1.0.2
    libssl1.0.2:amd64: /usr/lib/x86_64-linux-gnu/libssl.so.1.0.2
    $ apt show libssl1.0.2 2>&1 |grep ssl
    Package: libssl1.0.2
    Source: openssl1.0
    Maintainer: Debian OpenSSL Team <pkg-openssl-devel@lists.alioth.debian.org>
    Homepage: https://www.openssl.org

Re: [RFC PATCH 10/12] sha256: add an SHA-256 implementation using libgcrypt

[brian m. carlson]

[-- Attachment #1: Type: text/plain, Size: 2615 bytes --]

On Wed, Aug 29, 2018 at 10:53:01AM +0200, Ævar Arnfjörð Bjarmason wrote:
> 
> On Wed, Aug 29 2018, brian m. carlson wrote:
> 
> > Generally, one gets better performance out of cryptographic routines
> > written in assembly than C, and this is also true for SHA-256
> 
> It makes sense to have a libgcrypt implementation...
> 
> > In addition, most Linux distributions cannot distribute Git linked
> > against OpenSSL for licensing reasons.
> 
> ...but I'm curious to know what licensing reasons these are, e.g. Debian
> who's usually the most strict about these things distributes git linked
> to OpenSSL:

On my Debian system, that's linked to libgnutls.

The reason is section 3 of the GPLv2 (emphasis mine):

  3. You may copy and distribute the Program (or a work based on it,
  under Section 2) in object code or executable form **under the terms
  of Sections 1 and 2 above** provided that you also do one of the
  following:

  [provide source somehow]

  The source code for a work means the preferred form of the work for
  making modifications to it.  For an executable work, complete source
  code means all the source code for all modules it contains, plus any
  associated interface definition files, plus the scripts used to
  control compilation and installation of the executable.  **However, as
  a special exception, the source code distributed need not include
  anything that is normally distributed (in either source or binary
  form) with the major components (compiler, kernel, and so on) of the
  operating system on which the executable runs, unless that component
  itself accompanies the executable.**

Basically, you can only distribute binary versions of Git under the
terms of the GPLv2, and you have to distribute source for the entire
thing under those terms.  OpenSSL is licensed incompatibly with the
GPLv2, so you can't legally comply with that part, but if you use the
system OpenSSL and don't distribute that OpenSSL with Git, you're
exempt.  This is called the system library exception.

Debian (and Red Hat, and every other Linux distro) ships Git and OpenSSL
side by side on the same mirrors, and hence "that component [OpenSSL]
accompanies the executable."  Consequently, they can't take advantage of
the exception, and must link it to a GPLv2 compatible library.  Debian
uses GnuTLS for libcurl, and Red Hat uses NSS.

A more comprehensive explanation of the whole thing is here:
https://people.gnome.org/~markmc/openssl-and-the-gpl.html
-- 
brian m. carlson: Houston, Texas, US
OpenPGP: https://keybase.io/bk2204

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 867 bytes --]

[RFC PATCH 11/12] hash: add an SHA-256 implementation using OpenSSL

[brian m. carlson]

We already have OpenSSL routines available for SHA-1, so add routines
for SHA-256 as well.

Signed-off-by: brian m. carlson <sandals@crustytoothpaste.net>
---
 Makefile | 7 +++++++
 hash.h   | 2 ++
 2 files changed, 9 insertions(+)

diff --git a/Makefile b/Makefile
index 86867af083..8b7df4dfc5 100644
--- a/Makefile
+++ b/Makefile
@@ -183,6 +183,8 @@ all::
 #
 # Define GCRYPT_SHA256 to use the SHA-256 routines in libgcrypt.
 #
+# Define OPENSSL_SHA256 to use the SHA-256 routines in OpenSSL.
+#
 # Define NEEDS_CRYPTO_WITH_SSL if you need -lcrypto when using -lssl (Darwin).
 #
 # Define NEEDS_SSL_WITH_CRYPTO if you need -lssl when using -lcrypto (Darwin).
@@ -1628,6 +1630,10 @@ endif
 endif
 endif
 
+ifdef OPENSSL_SHA256
+	EXTLIBS += $(LIB_4_CRYPTO)
+	BASIC_CFLAGS += -DSHA256_OPENSSL
+else
 ifdef GCRYPT_SHA256
 	BASIC_CFLAGS += -DSHA256_GCRYPT
 	EXTLIBS += -lgcrypt
@@ -1635,6 +1641,7 @@ else
 	LIB_OBJS += sha256/block/sha256.o
 	BASIC_CFLAGS += -DSHA256_BLK
 endif
+endif
 
 ifdef SHA1_MAX_BLOCK_SIZE
 	LIB_OBJS += compat/sha1-chunked.o
diff --git a/hash.h b/hash.h
index 9df562f2f6..9df06d56b4 100644
--- a/hash.h
+++ b/hash.h
@@ -17,6 +17,8 @@
 
 #if defined(SHA256_GCRYPT)
 #include "sha256/gcrypt.h"
+#elif defined(SHA256_OPENSSL)
+#include <openssl/sha.h>
 #else
 #include "sha256/block/sha256.h"
 #endif

[RFC PATCH 12/12] commit-graph: specify OID version for SHA-256

[brian m. carlson]

Since the commit-graph code wants to serialize the hash algorithm into
the data store, specify a version number for each supported algorithm.
Note that we don't use the values of the constants themselves, as they
are internal and could change in the future.

Signed-off-by: brian m. carlson <sandals@crustytoothpaste.net>
---
 commit-graph.c | 9 ++++++++-
 1 file changed, 8 insertions(+), 1 deletion(-)

diff --git a/commit-graph.c b/commit-graph.c
index 29356d84a2..5b86acdb43 100644
--- a/commit-graph.c
+++ b/commit-graph.c
@@ -45,7 +45,14 @@ char *get_commit_graph_filename(const char *obj_dir)
 
 static uint8_t oid_version(void)
 {
-	return 1;
+	switch (hash_algo_by_ptr(the_hash_algo)) {
+		case GIT_HASH_SHA1:
+			return 1;
+		case GIT_HASH_SHA256:
+			return 2;
+		default:
+			BUG("unknown hash algorithm");
+	}
 }
 
 static struct commit_graph *alloc_commit_graph(void)

Re: [RFC PATCH 00/12] Base SHA-256 algorithm implementation

[Ævar Arnfjörð Bjarmason]

On Wed, Aug 29 2018, brian m. carlson wrote:

> If libgit2 would like to import this SHA-256 implementation, they're
> welcome to do so under their normal license terms.  If not, that's fine,
> too.

For them and anyone else interested in such re-use, can you elaborate on
which parts?

It seems to me that aside from t/helper/test-hash-speed.c and
t/t0014-hash.sh everything being added here modifies existing files with
many authors, and would thus also need their permission to re-license as
anything except GPLv2.

Or do you mean whatever fixes/changes you did to libtomcrypt (living in
sha256/block/ in this series) you consider e.g. LPGL instead of GPL?

Re: [RFC PATCH 00/12] Base SHA-256 algorithm implementation

[brian m. carlson]

[-- Attachment #1: Type: text/plain, Size: 803 bytes --]

On Wed, Aug 29, 2018 at 11:37:25AM +0200, Ævar Arnfjörð Bjarmason wrote:

> It seems to me that aside from t/helper/test-hash-speed.c and
> t/t0014-hash.sh everything being added here modifies existing files with
> many authors, and would thus also need their permission to re-license as
> anything except GPLv2.
> 
> Or do you mean whatever fixes/changes you did to libtomcrypt (living in
> sha256/block/ in this series) you consider e.g. LPGL instead of GPL?

Yes, that's what I mean, specifically the code in sha256/block.  libgit2
is GPLv2 with a linking exception, I believe, but either way I'd be fine
with it.

It wasn't my intention to offer code I didn't wholly author, so thanks
for clarifying.
-- 
brian m. carlson: Houston, Texas, US
OpenPGP: https://keybase.io/bk2204

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 867 bytes --]

Re: [RFC PATCH 00/12] Base SHA-256 algorithm implementation

[brian m. carlson]

[-- Attachment #1: Type: text/plain, Size: 1144 bytes --]

On Thu, Aug 30, 2018 at 02:21:51AM +0000, brian m. carlson wrote:
> On Wed, Aug 29, 2018 at 11:37:25AM +0200, Ævar Arnfjörð Bjarmason wrote:
> 
> > It seems to me that aside from t/helper/test-hash-speed.c and
> > t/t0014-hash.sh everything being added here modifies existing files with
> > many authors, and would thus also need their permission to re-license as
> > anything except GPLv2.
> > 
> > Or do you mean whatever fixes/changes you did to libtomcrypt (living in
> > sha256/block/ in this series) you consider e.g. LPGL instead of GPL?
> 
> Yes, that's what I mean, specifically the code in sha256/block.  libgit2
> is GPLv2 with a linking exception, I believe, but either way I'd be fine
> with it.
> 
> It wasn't my intention to offer code I didn't wholly author, so thanks
> for clarifying.

I should clarify further: I obviously didn't wholly author the code.  I
do, however, have permission to license it under alternative terms,
since the original was public domain.  I apologize for my
mischaracterization of the situation.
-- 
brian m. carlson: Houston, Texas, US
OpenPGP: https://keybase.io/bk2204

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 867 bytes --]