[PATCH 0/2] Re-integrate sha1dc

[PATCH 0/2] Re-integrate sha1dc

[Linus Torvalds]

I suspect the first patch will not make it to the list since it's over 
100kB in size, but oh well.. Junio and Jeff will see it.

This is sent as two patches, just to have the original upstream code as a 
first step, and then the second patch does the small modifications to 
integrate it with git.

It "WorksForMe(tm)" and the integration patches are now fairly trivial, 
since upstream already did the dieting and some of the semantic changes to 
gits more traditional C code.

I did leave the C++ wrapper lines that the sha1dc header files have grown 
in the meantime, I debated removing them but felt that "closer to 
upstream" was worth it.

               Linus

Re: [PATCH 0/2] Re-integrate sha1dc

[Jeff King]

On Thu, Mar 16, 2017 at 01:24:02PM -0700, Linus Torvalds wrote:

> I suspect the first patch will not make it to the list since it's over 
> 100kB in size, but oh well.. Junio and Jeff will see it.

Yep, it didn't make it, but I got it.

> It "WorksForMe(tm)" and the integration patches are now fairly trivial, 
> since upstream already did the dieting and some of the semantic changes to 
> gits more traditional C code.

There are a few things I think are worth changing. The die() message
should mention the sha1 we computed. That will be a big help if an old
version of git tries to unknowingly push a colliding object to a newer
version. The user will see "collision on sha1 1234.." which gives them a
starting point to figure out where they got the bad object from.

And to make that work, we have to disable the safe_hash feature (which
intentionally corrupts a colliding sha1). We _could_ rip it out
entirely, but since it only kicks in when we see a collision, I doubt
it's impacting anything.

I also updated the timings in my commit message, and added a basic test.

> I did leave the C++ wrapper lines that the sha1dc header files have grown 
> in the meantime, I debated removing them but felt that "closer to 
> upstream" was worth it.

Yeah, I independently made the same decision.

So here's my version. It's on top of the hash.h tweak, as well.

  [1/5]: add collision-detecting sha1 implementation
  [2/5]: sha1dc: adjust header includes for git
  [3/5]: sha1dc: disable safe_hash feature
  [4/5]: Makefile: add USE_SHA1DC knob
  [5/5]: t0013: add a basic sha1 collision detection test

 Makefile                |   11 +
 hash.h                  |    2 +
 sha1dc/LICENSE.txt      |   30 +
 sha1dc/sha1.c           | 1808 +++++++++++++++++++++++++++++++++++++++++++++++
 sha1dc/sha1.h           |  122 ++++
 sha1dc/ubc_check.c      |  363 ++++++++++
 sha1dc/ubc_check.h      |   44 ++
 t/t0013-sha1dc.sh       |   19 +
 t/t0013/shattered-1.pdf |  Bin 0 -> 422435 bytes
 9 files changed, 2399 insertions(+)
 create mode 100644 sha1dc/LICENSE.txt
 create mode 100644 sha1dc/sha1.c
 create mode 100644 sha1dc/sha1.h
 create mode 100644 sha1dc/ubc_check.c
 create mode 100644 sha1dc/ubc_check.h
 create mode 100755 t/t0013-sha1dc.sh
 create mode 100644 t/t0013/shattered-1.pdf

-Peff

[PATCH 2/5] sha1dc: adjust header includes for git

[Jeff King]

We can replace system includes with git-compat-util.h or
cache.h (and should make sure it is included first in all C
files).  And we can drop includes from headers entirely, as
every C file should include git-compat-util.h itself.

We will add in new include guards around the header files,
though (otherwise you get into trouble including both
sha1dc/sha1.h and cache.h).

And finally, we'll use the full "sha1dc/" path for including
related files. This isn't strictly necessary, but makes the
expected resolution more obvious.

Signed-off-by: Jeff King <peff@peff.net>
---
The cache.h thing is necessary if we want to use sha1_to_hex() later
(which I think we should).

 sha1dc/sha1.c      | 10 +++-------
 sha1dc/sha1.h      |  6 ++++--
 sha1dc/ubc_check.c |  4 ++--
 sha1dc/ubc_check.h |  2 --
 4 files changed, 9 insertions(+), 13 deletions(-)

diff --git a/sha1dc/sha1.c b/sha1dc/sha1.c
index 8d12b832b..da516c14c 100644
--- a/sha1dc/sha1.c
+++ b/sha1dc/sha1.c
@@ -5,13 +5,9 @@
 * https://opensource.org/licenses/MIT
 ***/
 
-#include <string.h>
-#include <memory.h>
-#include <stdio.h>
-#include <stdlib.h>
-
-#include "sha1.h"
-#include "ubc_check.h"
+#include "cache.h"
+#include "sha1dc/sha1.h"
+#include "sha1dc/ubc_check.h"
 
 
 /* 
diff --git a/sha1dc/sha1.h b/sha1dc/sha1.h
index e867724c0..8a5bf0847 100644
--- a/sha1dc/sha1.h
+++ b/sha1dc/sha1.h
@@ -4,13 +4,13 @@
 * See accompanying file LICENSE.txt or copy at
 * https://opensource.org/licenses/MIT
 ***/
+#ifndef SHA1DC_SHA1_H
+#define SHA1DC_SHA1_H
 
 #if defined(__cplusplus)
 extern "C" {
 #endif
 
-#include <stdint.h>
-
 /* uses SHA-1 message expansion to expand the first 16 words of W[] to 80 words */
 /* void sha1_message_expansion(uint32_t W[80]); */
 
@@ -103,3 +103,5 @@ int  SHA1DCFinal(unsigned char[20], SHA1_CTX*);
 #if defined(__cplusplus)
 }
 #endif
+
+#endif /* SHA1DC_SHA1_H */
diff --git a/sha1dc/ubc_check.c b/sha1dc/ubc_check.c
index 27d0976da..089dd4743 100644
--- a/sha1dc/ubc_check.c
+++ b/sha1dc/ubc_check.c
@@ -24,8 +24,8 @@
 // ubc_check has been verified against ubc_check_verify using the 'ubc_check_test' program in the tools section
 */
 
-#include <stdint.h>
-#include "ubc_check.h"
+#include "git-compat-util.h"
+#include "sha1dc/ubc_check.h"
 
 static const uint32_t DV_I_43_0_bit 	= (uint32_t)(1) << 0;
 static const uint32_t DV_I_44_0_bit 	= (uint32_t)(1) << 1;
diff --git a/sha1dc/ubc_check.h b/sha1dc/ubc_check.h
index b349bed92..b64c306d7 100644
--- a/sha1dc/ubc_check.h
+++ b/sha1dc/ubc_check.h
@@ -27,8 +27,6 @@
 extern "C" {
 #endif
 
-#include <stdint.h>
-
 #define DVMASKSIZE 1
 typedef struct { int dvType; int dvK; int dvB; int testt; int maski; int maskb; uint32_t dm[80]; } dv_info_t;
 extern dv_info_t sha1_dvs[];
-- 
2.12.0.623.g86ec6c963

[PATCH 3/5] sha1dc: disable safe_hash feature

[Jeff King]

The safe_hash feature is designed to make sha1dc a drop-in
replacement for sha1, where colliding entries will get a
permuted hash to un-collide them. However, since we're
handling the collision case ourselves, this isn't helpful
(and is actually harmful, as it means you get the wrong
object id if you want to show it in a log message).

Signed-off-by: Jeff King <peff@peff.net>
---
We could also disable this at runtime, but there's not really any point.
And this way we know that we won't miss a call.

 sha1dc/sha1.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/sha1dc/sha1.c b/sha1dc/sha1.c
index da516c14c..00760c352 100644
--- a/sha1dc/sha1.c
+++ b/sha1dc/sha1.c
@@ -1661,7 +1661,7 @@ void SHA1DCInit(SHA1_CTX* ctx)
 	ctx->ihv[3] = 0x10325476;
 	ctx->ihv[4] = 0xC3D2E1F0;
 	ctx->found_collision = 0;
-	ctx->safe_hash = 1;
+	ctx->safe_hash = 0;
 	ctx->ubc_check = 1;
 	ctx->detect_coll = 1;
 	ctx->reduced_round_coll = 0;
-- 
2.12.0.623.g86ec6c963

[PATCH 4/5] Makefile: add USE_SHA1DC knob

[Jeff King]

This knob lets you use the sha1dc implementation from:

      https://github.com/cr-marcstevens/sha1collisiondetection

which can detect certain types of collision attacks (even
when we only see half of the colliding pair). So it
mitigates any attack which consists of getting the "good"
half of a collision into a trusted repository, and then
later replacing it with the "bad" half. The "good" half is
rejected by the victim's version of Git (and even if they
run an old version of Git, any sha1dc-enabled git will
complain loudly if it ever has to interact with the object).

The big downside is that it's slower than either the openssl
or block-sha1 implementations.

Here are some timings based off of linux.git:

  - compute sha1 over whole packfile
      sha1dc: 3.580s
    blk-sha1: 2.046s (-43%)
     openssl: 1.335s (-62%)

  - rev-list --all --objects
      sha1dc: 33.512s
    blk-sha1: 33.514s (+0.0%)
     openssl: 33.650s (+0.4%)

  - git log --no-merges -10000 -p
      sha1dc: 8.124s
    blk-sha1: 7.986s (-1.6%)
     openssl: 8.203s (+0.9%)

  - index-pack --verify
      sha1dc: 4m19s
    blk-sha1: 2m57s (-32%)
     openssl: 2m19s (-42%)

So overall the sha1 computation with collision detection is
about 1.75x slower than block-sha1, and 2.7x slower than
sha1. But of course most operations do more than just sha1.
Normal object access isn't really slowed at all (both the
+/- changes there are well within the run-to-run noise); any
changes are drowned out by the other work Git is doing.

The most-affected operation is `index-pack --verify`, which
is essentially just computing the sha1 on every object. This
is similar to the `index-pack` invocation that the receiver
of a push or fetch would perform. So clearly there's some
extra CPU load here.

There will also be some latency for the user, though keep in
mind that such an operation will generally be network bound
(this is about a 1.2GB packfile). Some of that extra CPU is
"free" in the sense that we use it while the pack is
streaming in anyway. But most of it comes during the
delta-resolution phase, after the whole pack has been
received. So we can imagine that for this (quite large)
push, the user might have to wait an extra 100 seconds over
openssl (which is what we use now). If we assume they can
push to us at 20Mbit/s, that's 480s for a 1.2GB pack, which
is only 20% slower.

Signed-off-by: Jeff King <peff@peff.net>
---
 Makefile      | 10 ++++++++++
 hash.h        |  2 ++
 sha1dc/sha1.c | 20 ++++++++++++++++++++
 sha1dc/sha1.h | 15 +++++++++++++++
 4 files changed, 47 insertions(+)

diff --git a/Makefile b/Makefile
index 9f9561147..0aa483890 100644
--- a/Makefile
+++ b/Makefile
@@ -140,6 +140,10 @@ all::
 # Define PPC_SHA1 environment variable when running make to make use of
 # a bundled SHA1 routine optimized for PowerPC.
 #
+# Define USE_SHA1DC to unconditionally enable the collision-detecting sha1
+# algorithm. This is slower, but may detect attempted collision attacks.
+# Takes priority over other *_SHA1 knobs.
+#
 # Define SHA1_MAX_BLOCK_SIZE to limit the amount of data that will be hashed
 # in one call to the platform's SHA1_Update(). e.g. APPLE_COMMON_CRYPTO
 # wants 'SHA1_MAX_BLOCK_SIZE=1024L*1024L*1024L' defined.
@@ -1383,6 +1387,11 @@ ifdef APPLE_COMMON_CRYPTO
 	SHA1_MAX_BLOCK_SIZE = 1024L*1024L*1024L
 endif
 
+ifdef USE_SHA1DC
+	LIB_OBJS += sha1dc/sha1.o
+	LIB_OBJS += sha1dc/ubc_check.o
+	BASIC_CFLAGS += -DSHA1_SHA1DC
+else
 ifdef BLK_SHA1
 	LIB_OBJS += block-sha1/sha1.o
 	BASIC_CFLAGS += -DSHA1_BLK
@@ -1400,6 +1409,7 @@ else
 endif
 endif
 endif
+endif
 
 ifdef SHA1_MAX_BLOCK_SIZE
 	LIB_OBJS += compat/sha1-chunked.o
diff --git a/hash.h b/hash.h
index f0d9ddd0c..3760f436e 100644
--- a/hash.h
+++ b/hash.h
@@ -7,6 +7,8 @@
 #include <CommonCrypto/CommonDigest.h>
 #elif defined(SHA1_OPENSSL)
 #include <openssl/sha.h>
+#elif defined(SHA1_SHA1DC)
+#include "sha1dc/sha1.h"
 #else /* SHA1_BLK */
 #include "block-sha1/sha1.h"
 #endif
diff --git a/sha1dc/sha1.c b/sha1dc/sha1.c
index 00760c352..3ce0a4f39 100644
--- a/sha1dc/sha1.c
+++ b/sha1dc/sha1.c
@@ -1786,3 +1786,23 @@ int SHA1DCFinal(unsigned char output[20], SHA1_CTX *ctx)
 	output[19] = (unsigned char)(ctx->ihv[4]);
 	return ctx->found_collision;
 }
+
+void git_SHA1DCFinal(unsigned char hash[20], SHA1_CTX *ctx)
+{
+	if (!SHA1DCFinal(hash, ctx))
+		return;
+	die("SHA-1 appears to be part of a collision attack: %s",
+	    sha1_to_hex(hash));
+}
+
+void git_SHA1DCUpdate(SHA1_CTX *ctx, const void *vdata, unsigned long len)
+{
+	const char *data = vdata;
+	/* We expect an unsigned long, but sha1dc only takes an int */
+	while (len > INT_MAX) {
+		SHA1DCUpdate(ctx, data, INT_MAX);
+		data += INT_MAX;
+		len -= INT_MAX;
+	}
+	SHA1DCUpdate(ctx, data, len);
+}
diff --git a/sha1dc/sha1.h b/sha1dc/sha1.h
index 8a5bf0847..aa883df01 100644
--- a/sha1dc/sha1.h
+++ b/sha1dc/sha1.h
@@ -100,6 +100,21 @@ void SHA1DCUpdate(SHA1_CTX*, const char*, size_t);
 /* returns: 0 = no collision detected, otherwise = collision found => warn user for active attack */
 int  SHA1DCFinal(unsigned char[20], SHA1_CTX*); 
 
+/*
+ * Same as SHA1DCFinal, but convert collision attack case into a verbose die().
+ */
+void git_SHA1DCFinal(unsigned char [20], SHA1_CTX *);
+
+/*
+ * Same as SHA1DCUpdate, but adjust types to match git's usual interface.
+ */
+void git_SHA1DCUpdate(SHA1_CTX *ctx, const void *data, unsigned long len);
+
+#define platform_SHA_CTX SHA1_CTX
+#define platform_SHA1_Init SHA1DCInit
+#define platform_SHA1_Update git_SHA1DCUpdate
+#define platform_SHA1_Final git_SHA1DCFinal
+
 #if defined(__cplusplus)
 }
 #endif
-- 
2.12.0.623.g86ec6c963

Re: [PATCH 0/2] Re-integrate sha1dc

[Jeff King]

On Thu, Mar 16, 2017 at 06:04:56PM -0400, Jeff King wrote:

> So here's my version. It's on top of the hash.h tweak, as well.
> 
>   [1/5]: add collision-detecting sha1 implementation
>   [2/5]: sha1dc: adjust header includes for git
>   [3/5]: sha1dc: disable safe_hash feature
>   [4/5]: Makefile: add USE_SHA1DC knob
>   [5/5]: t0013: add a basic sha1 collision detection test
> [...]
>  t/t0013/shattered-1.pdf |  Bin 0 -> 422435 bytes

So obviously I had the same 100K problem you did on the first patch, but
the fifth one also won't make it to the list. You can pull the whole
thing from:

  https://github.com/peff/git.git jk/sha1dc

-Peff

Re: [PATCH 0/2] Re-integrate sha1dc

[Junio C Hamano]

Jeff King <peff@peff.net> writes:

> On Thu, Mar 16, 2017 at 06:04:56PM -0400, Jeff King wrote:
>
>> So here's my version. It's on top of the hash.h tweak, as well.
>> 
>>   [1/5]: add collision-detecting sha1 implementation
>>   [2/5]: sha1dc: adjust header includes for git
>>   [3/5]: sha1dc: disable safe_hash feature
>>   [4/5]: Makefile: add USE_SHA1DC knob
>>   [5/5]: t0013: add a basic sha1 collision detection test
>> [...]
>>  t/t0013/shattered-1.pdf |  Bin 0 -> 422435 bytes

A 420k binary blob has become ~500k base85 binary patch, which is
larger than 100k.

> So obviously I had the same 100K problem you did on the first patch, but
> the fifth one also won't make it to the list. You can pull the whole
> thing from:
>
>   https://github.com/peff/git.git jk/sha1dc

Thanks.  

For today's integration, I have the one from Linus only because it
came earlier and today's integration cycle was already running.  I
agree with this series that disables the safe-hash thing.

I am wondering if we should queue another one for .travis.yml on top
to force use of USE_SHA1DC=YesPlease during the tests.  I expect
that we'd be encouraging its use for ordinary users without any
specific needs in the release notes in 2.13 release.

Re: [PATCH 0/2] Re-integrate sha1dc

[Linus Torvalds]

On Thu, Mar 16, 2017 at 3:04 PM, Jeff King <peff@peff.net> wrote:
>
> There are a few things I think are worth changing. The die() message
> should mention the sha1 we computed. That will be a big help if an old
> version of git tries to unknowingly push a colliding object to a newer
> version. The user will see "collision on sha1 1234.." which gives them a
> starting point to figure out where they got the bad object from.
>
> And to make that work, we have to disable the safe_hash feature (which
> intentionally corrupts a colliding sha1). We _could_ rip it out
> entirely, but since it only kicks in when we see a collision, I doubt
> it's impacting anything.
>
> I also updated the timings in my commit message, and added a basic test.

No complaints about your version.

               Linus

Re: [PATCH 4/5] Makefile: add USE_SHA1DC knob

[Junio C Hamano]

Jeff King <peff@peff.net> writes:

> +ifdef USE_SHA1DC
> +	LIB_OBJS += sha1dc/sha1.o
> +	LIB_OBJS += sha1dc/ubc_check.o
> +	BASIC_CFLAGS += -DSHA1_SHA1DC

The name of this CPP symbol is one difference between this and
Linus's version.  Wouldn't "-DSHA1_DC" make more sense?

Another difference is that your version adds USE_SHA1DC to
GIT-BUILD-OPTIONS in patch 5/5; I thought GIT-CFLAGS forces
rebuilding and that was sufficient, but GIT-BUILD-OPTIONS is
available to tests for introspection, so adding it is needed
for that reason.

Re: [PATCH 4/5] Makefile: add USE_SHA1DC knob

[Jeff King]

On Thu, Mar 16, 2017 at 03:43:13PM -0700, Junio C Hamano wrote:

> Jeff King <peff@peff.net> writes:
> 
> > +ifdef USE_SHA1DC
> > +	LIB_OBJS += sha1dc/sha1.o
> > +	LIB_OBJS += sha1dc/ubc_check.o
> > +	BASIC_CFLAGS += -DSHA1_SHA1DC
> 
> The name of this CPP symbol is one difference between this and
> Linus's version.  Wouldn't "-DSHA1_DC" make more sense?

I'm fine with either. Somehow SHA1_DC felt too short, but it doesn't
really matter in practice.

> Another difference is that your version adds USE_SHA1DC to
> GIT-BUILD-OPTIONS in patch 5/5; I thought GIT-CFLAGS forces
> rebuilding and that was sufficient, but GIT-BUILD-OPTIONS is
> available to tests for introspection, so adding it is needed
> for that reason.

Yep, exactly.

-Peff

Re: [PATCH 0/2] Re-integrate sha1dc

[Jeff King]

On Thu, Mar 16, 2017 at 03:23:59PM -0700, Junio C Hamano wrote:

> I am wondering if we should queue another one for .travis.yml on top
> to force use of USE_SHA1DC=YesPlease during the tests.  I expect
> that we'd be encouraging its use for ordinary users without any
> specific needs in the release notes in 2.13 release.

I don't think it would buy us much. There's not really any way for this
build to interact with the rest of the code in any interesting way, so
either it works as a SHA-1 implementation or it doesn't. If you just
want it exercised, I'll say that it's powering all of github.com right
now.

I did wonder if we should ship with it as the default (instead of
openssl). It's definitely slower, but maybe widespread safety is a good
thing. OTOH, I think we have a fair bit of time before we see any
real-life collisions, just given the time and expense of generating
them.

-Peff

Re: [PATCH 0/2] Re-integrate sha1dc

[Junio C Hamano]

Jeff King <peff@peff.net> writes:

> On Thu, Mar 16, 2017 at 03:23:59PM -0700, Junio C Hamano wrote:
>
>> I am wondering if we should queue another one for .travis.yml on top
>> to force use of USE_SHA1DC=YesPlease during the tests.  I expect
>> that we'd be encouraging its use for ordinary users without any
>> specific needs in the release notes in 2.13 release.
>
> I don't think it would buy us much. There's not really any way for this
> build to interact with the rest of the code in any interesting way, so
> either it works as a SHA-1 implementation or it doesn't. If you just
> want it exercised, I'll say that it's powering all of github.com right
> now.
>
> I did wonder if we should ship with it as the default (instead of
> openssl). It's definitely slower, but maybe widespread safety is a good
> thing. OTOH, I think we have a fair bit of time before we see any
> real-life collisions, just given the time and expense of generating
> them.

My .travis.yml suggestion was about testing with SHA1DC in
preparation for making it the default.  That would give us another
incentive to keep an eye on its performance, too, before we make it
the default in Makefile, at which time the forced selection in the
travis configuration can be removed.

Thanks.

Re: [PATCH 4/5] Makefile: add USE_SHA1DC knob

[Junio C Hamano]

Jeff King <peff@peff.net> writes:

> On Thu, Mar 16, 2017 at 03:43:13PM -0700, Junio C Hamano wrote:
>
>> Jeff King <peff@peff.net> writes:
>> 
>> > +ifdef USE_SHA1DC
>> > +	LIB_OBJS += sha1dc/sha1.o
>> > +	LIB_OBJS += sha1dc/ubc_check.o
>> > +	BASIC_CFLAGS += -DSHA1_SHA1DC
>> 
>> The name of this CPP symbol is one difference between this and
>> Linus's version.  Wouldn't "-DSHA1_DC" make more sense?
>
> I'm fine with either. Somehow SHA1_DC felt too short, but it doesn't
> really matter in practice.

I'm fine with either, too.  It was just double SHA1 felt a bit
strange, when the naming convention was SHA1_ followed by the
characteristic attribute of the implementation (e.g. came from
Mozilla, etc.) and I thought "Detecting Collision" was the notable
characteristic of this one.

>> Another difference is that your version adds USE_SHA1DC to
>> GIT-BUILD-OPTIONS in patch 5/5; I thought GIT-CFLAGS forces
>> rebuilding and that was sufficient, but GIT-BUILD-OPTIONS is
>> available to tests for introspection, so adding it is needed
>> for that reason.
>
> Yep, exactly.

Thanks.

Re: [PATCH 4/5] Makefile: add USE_SHA1DC knob

[Jeff King]

On Thu, Mar 16, 2017 at 10:24:32PM -0700, Junio C Hamano wrote:

> Jeff King <peff@peff.net> writes:
> 
> > On Thu, Mar 16, 2017 at 03:43:13PM -0700, Junio C Hamano wrote:
> >
> >> Jeff King <peff@peff.net> writes:
> >> 
> >> > +ifdef USE_SHA1DC
> >> > +	LIB_OBJS += sha1dc/sha1.o
> >> > +	LIB_OBJS += sha1dc/ubc_check.o
> >> > +	BASIC_CFLAGS += -DSHA1_SHA1DC
> >> 
> >> The name of this CPP symbol is one difference between this and
> >> Linus's version.  Wouldn't "-DSHA1_DC" make more sense?
> >
> > I'm fine with either. Somehow SHA1_DC felt too short, but it doesn't
> > really matter in practice.
> 
> I'm fine with either, too.  It was just double SHA1 felt a bit
> strange, when the naming convention was SHA1_ followed by the
> characteristic attribute of the implementation (e.g. came from
> Mozilla, etc.) and I thought "Detecting Collision" was the notable
> characteristic of this one.

Yeah, I thought "DC" by itself was funny, but I guess "BLK" by itself is
no less funny. I'm happy to re-roll it if you prefer the other.

-Peff

Re: [PATCH 0/2] Re-integrate sha1dc

[Jeff King]

On Thu, Mar 16, 2017 at 10:22:12PM -0700, Junio C Hamano wrote:

> My .travis.yml suggestion was about testing with SHA1DC in
> preparation for making it the default.  That would give us another
> incentive to keep an eye on its performance, too, before we make it
> the default in Makefile, at which time the forced selection in the
> travis configuration can be removed.

Yeah, I'm not opposed to that, though it requires somebody actually
paying attention to the timings differences. I'm not sure we can do that
automatically on Travis.

-Peff

[RFC PATCH 0/3] Git integration update for DC-SHA1

[Junio C Hamano]

Here are three patches to replace the last two patches from your
series.

 - The Makefile knob is named DC_SHA1, not USE_SHA1DC; this is to
   keep it consistent with existing BLK_SHA1 and PPC_SHA1.

 - The CPP macro is called SHA1_DC, not SHA1_SHA1DC; again this is
   for consistency with SHA1_BLK and SHA1_PPC.

 - Switch the default from OpenSSL's implementation to DC_SHA1.
   Those who want OpenSSL's one can ask with OPENSSL_SHA1.

Jeff King (2):
  Makefile: add DC_SHA1 knob
  t0013: add a basic sha1 collision detection test

Junio C Hamano (1):
  Makefile: make DC_SHA1 the default

 Makefile                |  19 +++++++++++++++++--
 hash.h                  |   2 ++
 sha1dc/sha1.c           |  20 ++++++++++++++++++++
 sha1dc/sha1.h           |  15 +++++++++++++++
 t/t0013-sha1dc.sh       |  19 +++++++++++++++++++
 t/t0013/shattered-1.pdf | Bin 0 -> 422435 bytes
 6 files changed, 73 insertions(+), 2 deletions(-)
 create mode 100755 t/t0013-sha1dc.sh
 create mode 100644 t/t0013/shattered-1.pdf

-- 
2.12.0-317-g32c43f595f

[PATCH 1/3] Makefile: add DC_SHA1 knob

[Junio C Hamano]

From: Jeff King <peff@peff.net>

This knob lets you use the sha1dc implementation from:

      https://github.com/cr-marcstevens/sha1collisiondetection

which can detect certain types of collision attacks (even
when we only see half of the colliding pair). So it
mitigates any attack which consists of getting the "good"
half of a collision into a trusted repository, and then
later replacing it with the "bad" half. The "good" half is
rejected by the victim's version of Git (and even if they
run an old version of Git, any sha1dc-enabled git will
complain loudly if it ever has to interact with the object).

The big downside is that it's slower than either the openssl
or block-sha1 implementations.

Here are some timings based off of linux.git:

  - compute sha1 over whole packfile
      sha1dc: 3.580s
    blk-sha1: 2.046s (-43%)
     openssl: 1.335s (-62%)

  - rev-list --all --objects
      sha1dc: 33.512s
    blk-sha1: 33.514s (+0.0%)
     openssl: 33.650s (+0.4%)

  - git log --no-merges -10000 -p
      sha1dc: 8.124s
    blk-sha1: 7.986s (-1.6%)
     openssl: 8.203s (+0.9%)

  - index-pack --verify
      sha1dc: 4m19s
    blk-sha1: 2m57s (-32%)
     openssl: 2m19s (-42%)

So overall the sha1 computation with collision detection is
about 1.75x slower than block-sha1, and 2.7x slower than
sha1. But of course most operations do more than just sha1.
Normal object access isn't really slowed at all (both the
+/- changes there are well within the run-to-run noise); any
changes are drowned out by the other work Git is doing.

The most-affected operation is `index-pack --verify`, which
is essentially just computing the sha1 on every object. This
is similar to the `index-pack` invocation that the receiver
of a push or fetch would perform. So clearly there's some
extra CPU load here.

There will also be some latency for the user, though keep in
mind that such an operation will generally be network bound
(this is about a 1.2GB packfile). Some of that extra CPU is
"free" in the sense that we use it while the pack is
streaming in anyway. But most of it comes during the
delta-resolution phase, after the whole pack has been
received. So we can imagine that for this (quite large)
push, the user might have to wait an extra 100 seconds over
openssl (which is what we use now). If we assume they can
push to us at 20Mbit/s, that's 480s for a 1.2GB pack, which
is only 20% slower.

Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 Makefile      | 10 ++++++++++
 hash.h        |  2 ++
 sha1dc/sha1.c | 20 ++++++++++++++++++++
 sha1dc/sha1.h | 15 +++++++++++++++
 4 files changed, 47 insertions(+)

diff --git a/Makefile b/Makefile
index 25c21f08b1..05a96d7177 100644
--- a/Makefile
+++ b/Makefile
@@ -142,6 +142,10 @@ all::
 # Define PPC_SHA1 environment variable when running make to make use of
 # a bundled SHA1 routine optimized for PowerPC.
 #
+# Define DC_SHA1 to unconditionally enable the collision-detecting sha1
+# algorithm. This is slower, but may detect attempted collision attacks.
+# Takes priority over other *_SHA1 knobs.
+#
 # Define SHA1_MAX_BLOCK_SIZE to limit the amount of data that will be hashed
 # in one call to the platform's SHA1_Update(). e.g. APPLE_COMMON_CRYPTO
 # wants 'SHA1_MAX_BLOCK_SIZE=1024L*1024L*1024L' defined.
@@ -1386,6 +1390,11 @@ ifdef APPLE_COMMON_CRYPTO
 	SHA1_MAX_BLOCK_SIZE = 1024L*1024L*1024L
 endif
 
+ifdef DC_SHA1
+	LIB_OBJS += sha1dc/sha1.o
+	LIB_OBJS += sha1dc/ubc_check.o
+	BASIC_CFLAGS += -DSHA1_DC
+else
 ifdef BLK_SHA1
 	LIB_OBJS += block-sha1/sha1.o
 	BASIC_CFLAGS += -DSHA1_BLK
@@ -1403,6 +1412,7 @@ else
 endif
 endif
 endif
+endif
 
 ifdef SHA1_MAX_BLOCK_SIZE
 	LIB_OBJS += compat/sha1-chunked.o
diff --git a/hash.h b/hash.h
index f0d9ddd0c2..a11fc9233f 100644
--- a/hash.h
+++ b/hash.h
@@ -7,6 +7,8 @@
 #include <CommonCrypto/CommonDigest.h>
 #elif defined(SHA1_OPENSSL)
 #include <openssl/sha.h>
+#elif defined(SHA1_DC)
+#include "sha1dc/sha1.h"
 #else /* SHA1_BLK */
 #include "block-sha1/sha1.h"
 #endif
diff --git a/sha1dc/sha1.c b/sha1dc/sha1.c
index 8ff2321dfb..6dd0da3608 100644
--- a/sha1dc/sha1.c
+++ b/sha1dc/sha1.c
@@ -1786,3 +1786,23 @@ int SHA1DCFinal(unsigned char output[20], SHA1_CTX *ctx)
 	output[19] = (unsigned char)(ctx->ihv[4]);
 	return ctx->found_collision;
 }
+
+void git_SHA1DCFinal(unsigned char hash[20], SHA1_CTX *ctx)
+{
+	if (!SHA1DCFinal(hash, ctx))
+		return;
+	die("SHA-1 appears to be part of a collision attack: %s",
+	    sha1_to_hex(hash));
+}
+
+void git_SHA1DCUpdate(SHA1_CTX *ctx, const void *vdata, unsigned long len)
+{
+	const char *data = vdata;
+	/* We expect an unsigned long, but sha1dc only takes an int */
+	while (len > INT_MAX) {
+		SHA1DCUpdate(ctx, data, INT_MAX);
+		data += INT_MAX;
+		len -= INT_MAX;
+	}
+	SHA1DCUpdate(ctx, data, len);
+}
diff --git a/sha1dc/sha1.h b/sha1dc/sha1.h
index 7d4d423b9d..bd8bd928fb 100644
--- a/sha1dc/sha1.h
+++ b/sha1dc/sha1.h
@@ -100,6 +100,21 @@ void SHA1DCUpdate(SHA1_CTX*, const char*, size_t);
 /* returns: 0 = no collision detected, otherwise = collision found => warn user for active attack */
 int  SHA1DCFinal(unsigned char[20], SHA1_CTX*);
 
+/*
+ * Same as SHA1DCFinal, but convert collision attack case into a verbose die().
+ */
+void git_SHA1DCFinal(unsigned char [20], SHA1_CTX *);
+
+/*
+ * Same as SHA1DCUpdate, but adjust types to match git's usual interface.
+ */
+void git_SHA1DCUpdate(SHA1_CTX *ctx, const void *data, unsigned long len);
+
+#define platform_SHA_CTX SHA1_CTX
+#define platform_SHA1_Init SHA1DCInit
+#define platform_SHA1_Update git_SHA1DCUpdate
+#define platform_SHA1_Final git_SHA1DCFinal
+
 #if defined(__cplusplus)
 }
 #endif
-- 
2.12.0-317-g32c43f595f

[PATCH 3/3] Makefile: make DC_SHA1 the default

[Junio C Hamano]

We used to use the SHA1 implementation from the OpenSSL library by
default.  As we are trying to be careful against collision attacks
after the recent "shattered" announcement, switch the default to
encourage people to use DC_SHA1 implementation instead.  Those who
want to use the implementation from OpenSSL can explicitly ask for
it by OPENSSL_SHA1=YesPlease when running "make".

Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 Makefile | 16 ++++++++++------
 1 file changed, 10 insertions(+), 6 deletions(-)

diff --git a/Makefile b/Makefile
index fc9d89498b..fd4421eeb8 100644
--- a/Makefile
+++ b/Makefile
@@ -146,6 +146,9 @@ all::
 # algorithm. This is slower, but may detect attempted collision attacks.
 # Takes priority over other *_SHA1 knobs.
 #
+# Define OPENSSL_SHA1 environment variable when running make to link
+# with the SHA1 routine from openssl library.
+#
 # Define SHA1_MAX_BLOCK_SIZE to limit the amount of data that will be hashed
 # in one call to the platform's SHA1_Update(). e.g. APPLE_COMMON_CRYPTO
 # wants 'SHA1_MAX_BLOCK_SIZE=1024L*1024L*1024L' defined.
@@ -1390,10 +1393,9 @@ ifdef APPLE_COMMON_CRYPTO
 	SHA1_MAX_BLOCK_SIZE = 1024L*1024L*1024L
 endif
 
-ifdef DC_SHA1
-	LIB_OBJS += sha1dc/sha1.o
-	LIB_OBJS += sha1dc/ubc_check.o
-	BASIC_CFLAGS += -DSHA1_DC
+ifdef OPENSSL_SHA1
+	EXTLIBS += $(LIB_4_CRYPTO)
+	BASIC_CFLAGS += -DSHA1_OPENSSL
 else
 ifdef BLK_SHA1
 	LIB_OBJS += block-sha1/sha1.o
@@ -1407,8 +1409,10 @@ ifdef APPLE_COMMON_CRYPTO
 	COMPAT_CFLAGS += -DCOMMON_DIGEST_FOR_OPENSSL
 	BASIC_CFLAGS += -DSHA1_APPLE
 else
-	EXTLIBS += $(LIB_4_CRYPTO)
-	BASIC_CFLAGS += -DSHA1_OPENSSL
+	DC_SHA1 := YesPlease
+	LIB_OBJS += sha1dc/sha1.o
+	LIB_OBJS += sha1dc/ubc_check.o
+	BASIC_CFLAGS += -DSHA1_DC
 endif
 endif
 endif
-- 
2.12.0-317-g32c43f595f

Re: [RFC PATCH 0/3] Git integration update for DC-SHA1

[Junio C Hamano]

Junio C Hamano <gitster@pobox.com> writes:

> Here are three patches to replace the last two patches from your
> series.
>
>  - The Makefile knob is named DC_SHA1, not USE_SHA1DC; this is to
>    keep it consistent with existing BLK_SHA1 and PPC_SHA1.
>
>  - The CPP macro is called SHA1_DC, not SHA1_SHA1DC; again this is
>    for consistency with SHA1_BLK and SHA1_PPC.
>
>  - Switch the default from OpenSSL's implementation to DC_SHA1.
>    Those who want OpenSSL's one can ask with OPENSSL_SHA1.
>
> Jeff King (2):
>   Makefile: add DC_SHA1 knob
>   t0013: add a basic sha1 collision detection test
>
> Junio C Hamano (1):
>   Makefile: make DC_SHA1 the default
>
>  Makefile                |  19 +++++++++++++++++--
>  hash.h                  |   2 ++
>  sha1dc/sha1.c           |  20 ++++++++++++++++++++
>  sha1dc/sha1.h           |  15 +++++++++++++++
>  t/t0013-sha1dc.sh       |  19 +++++++++++++++++++
>  t/t0013/shattered-1.pdf | Bin 0 -> 422435 bytes
>  6 files changed, 73 insertions(+), 2 deletions(-)
>  create mode 100755 t/t0013-sha1dc.sh
>  create mode 100644 t/t0013/shattered-1.pdf

For a rather obvious reason, patch 2/3 cannot be seen on the list.
The "interdiff" between jk/sha1dc topic and applying patches 1 and 2
(but not 3) looks like this.

diff --git a/Makefile b/Makefile
index b01111c581..fc9d89498b 100644
--- a/Makefile
+++ b/Makefile
@@ -142,7 +142,7 @@ all::
 # Define PPC_SHA1 environment variable when running make to make use of
 # a bundled SHA1 routine optimized for PowerPC.
 #
-# Define USE_SHA1DC to unconditionally enable the collision-detecting sha1
+# Define DC_SHA1 to unconditionally enable the collision-detecting sha1
 # algorithm. This is slower, but may detect attempted collision attacks.
 # Takes priority over other *_SHA1 knobs.
 #
@@ -1390,10 +1390,10 @@ ifdef APPLE_COMMON_CRYPTO
 	SHA1_MAX_BLOCK_SIZE = 1024L*1024L*1024L
 endif
 
-ifdef USE_SHA1DC
+ifdef DC_SHA1
 	LIB_OBJS += sha1dc/sha1.o
 	LIB_OBJS += sha1dc/ubc_check.o
-	BASIC_CFLAGS += -DSHA1_SHA1DC
+	BASIC_CFLAGS += -DSHA1_DC
 else
 ifdef BLK_SHA1
 	LIB_OBJS += block-sha1/sha1.o
@@ -2236,7 +2236,7 @@ GIT-BUILD-OPTIONS: FORCE
 	@echo NO_PYTHON=\''$(subst ','\'',$(subst ','\'',$(NO_PYTHON)))'\' >>$@+
 	@echo NO_UNIX_SOCKETS=\''$(subst ','\'',$(subst ','\'',$(NO_UNIX_SOCKETS)))'\' >>$@+
 	@echo PAGER_ENV=\''$(subst ','\'',$(subst ','\'',$(PAGER_ENV)))'\' >>$@+
-	@echo USE_SHA1DC=\''$(subst ','\'',$(subst ','\'',$(USE_SHA1DC)))'\' >>$@+
+	@echo DC_SHA1=\''$(subst ','\'',$(subst ','\'',$(DC_SHA1)))'\' >>$@+
 ifdef TEST_OUTPUT_DIRECTORY
 	@echo TEST_OUTPUT_DIRECTORY=\''$(subst ','\'',$(subst ','\'',$(TEST_OUTPUT_DIRECTORY)))'\' >>$@+
 endif
diff --git a/hash.h b/hash.h
index 3760f436ec..a11fc9233f 100644
--- a/hash.h
+++ b/hash.h
@@ -7,7 +7,7 @@
 #include <CommonCrypto/CommonDigest.h>
 #elif defined(SHA1_OPENSSL)
 #include <openssl/sha.h>
-#elif defined(SHA1_SHA1DC)
+#elif defined(SHA1_DC)
 #include "sha1dc/sha1.h"
 #else /* SHA1_BLK */
 #include "block-sha1/sha1.h"
diff --git a/t/t0013-sha1dc.sh b/t/t0013-sha1dc.sh
index 4d43f7bf64..6d655cb161 100755
--- a/t/t0013-sha1dc.sh
+++ b/t/t0013-sha1dc.sh
@@ -4,9 +4,9 @@ test_description='test sha1 collision detection'
 . ./test-lib.sh
 TEST_DATA="$TEST_DIRECTORY/t0013"
 
-if test -z "$USE_SHA1DC"
+if test -z "$DC_SHA1"
 then
-	skip_all='skipping sha1 collision tests, USE_SHA1DC not set'
+	skip_all='skipping sha1 collision tests, DC_SHA1 not set'
 	test_done
 fi
 

Re: [RFC PATCH 0/3] Git integration update for DC-SHA1

[Jeff King]

On Fri, Mar 17, 2017 at 10:09:35AM -0700, Junio C Hamano wrote:

> Here are three patches to replace the last two patches from your
> series.
> 
>  - The Makefile knob is named DC_SHA1, not USE_SHA1DC; this is to
>    keep it consistent with existing BLK_SHA1 and PPC_SHA1.
> 
>  - The CPP macro is called SHA1_DC, not SHA1_SHA1DC; again this is
>    for consistency with SHA1_BLK and SHA1_PPC.
> 
>  - Switch the default from OpenSSL's implementation to DC_SHA1.
>    Those who want OpenSSL's one can ask with OPENSSL_SHA1.

OK. DC_SHA1 exposed tothe user does look a little funny to me, but it is
at least consistent with the other names. The patches themselves look
obviously fine.

-Peff