Skip to contentSkip to conversation

Re-integrate sha1dc

PATCH In review Linus Torvalds 3 participants 20 messages Mar 16, 2017 – Mar 17, 2017 Kbuild

lore
Share & tools
lore
#0 lore raw

cover Re-integrate sha1dc

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

#1 lore raw
Quoted 2 lines · 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.

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

Quoted 3 lines

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.

Quoted 3 lines

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

#2 lore raw

PATCH 2/5 sha1dc: adjust header includes for git

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.

---
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(-)
sha1dc/sha1.c +3 -7
index 8d12b832b..da516c14c 100644
@@ -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"
 
 
 /* 
sha1dc/sha1.h +4 -2
index e867724c0..8a5bf0847 100644
@@ -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 */
sha1dc/ubc_check.c +2 -2
index 27d0976da..089dd4743 100644
@@ -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;
sha1dc/ubc_check.h +0 -2
index b349bed92..b64c306d7 100644
@@ -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[];
Signature · 1 line
2.12.0.623.g86ec6c963
#3 lore raw

PATCH 3/5 sha1dc: disable safe_hash feature

In reply to 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).

---
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(-)
sha1dc/sha1.c +1 -1
index da516c14c..00760c352 100644
@@ -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;
Signature · 1 line
2.12.0.623.g86ec6c963
#4 lore raw

PATCH 4/5 Makefile: add USE_SHA1DC knob

In reply to 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.

---
 Makefile      | 10 ++++++++++
 hash.h        |  2 ++
 sha1dc/sha1.c | 20 ++++++++++++++++++++
 sha1dc/sha1.h | 15 +++++++++++++++
 4 files changed, 47 insertions(+)
Makefile +10 -0
index 9f9561147..0aa483890 100644
@@ -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
hash.h +2 -0
index f0d9ddd0c..3760f436e 100644
@@ -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
sha1dc/sha1.c +20 -0
index 00760c352..3ce0a4f39 100644
@@ -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);
+}
sha1dc/sha1.h +15 -0
index 8a5bf0847..aa883df01 100644
@@ -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
Signature · 1 line
2.12.0.623.g86ec6c963
#5 lore raw

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

Makefile ifdef APPLE_COMMON_CRYPTO · line 1393

Quoted 4 lines · Jeff King
Makefile +4 -0
+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.

#6 lore raw

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

Quoted 9 lines · Junio C Hamano

Makefile ifdef APPLE_COMMON_CRYPTO · line 1393

Quoted 4 lines · Jeff King
Makefile +4 -0
+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.

Quoted 5 lines

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

#7 lore raw

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

Quoted 12 lines · Jeff King
Quoted 9 lines · Junio C Hamano

Makefile ifdef APPLE_COMMON_CRYPTO · line 1393

Quoted 4 lines · Jeff King
Makefile +4 -0
+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?

Quoted 2 lines

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.

Quoted 7 lines
Quoted 5 lines

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.

#8 lore raw

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

Quoted 14 lines · Junio C Hamano
Quoted 12 lines · Jeff King
Quoted 9 lines · Junio C Hamano

Makefile ifdef APPLE_COMMON_CRYPTO · line 1393

Quoted 4 lines · Jeff King
Makefile +4 -0
+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?

Quoted 8 lines
Quoted 2 lines

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

#9 lore raw

cover Git integration update for DC-SHA1

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
Signature · 1 line
2.12.0-317-g32c43f595f
#10 lore raw

PATCH 1/3 Makefile: add DC_SHA1 knob

From: Jeff King <[email protected]>

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.

---
 Makefile      | 10 ++++++++++
 hash.h        |  2 ++
 sha1dc/sha1.c | 20 ++++++++++++++++++++
 sha1dc/sha1.h | 15 +++++++++++++++
 4 files changed, 47 insertions(+)
Makefile +10 -0
index 25c21f08b1..05a96d7177 100644
@@ -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
hash.h +2 -0
index f0d9ddd0c2..a11fc9233f 100644
@@ -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
sha1dc/sha1.c +20 -0
index 8ff2321dfb..6dd0da3608 100644
@@ -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);
+}
sha1dc/sha1.h +15 -0
index 7d4d423b9d..bd8bd928fb 100644
@@ -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
Signature · 1 line
2.12.0-317-g32c43f595f
#11 lore raw

PATCH 3/3 Makefile: make DC_SHA1 the default

In reply to 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".

---
 Makefile | 16 ++++++++++------
 1 file changed, 10 insertions(+), 6 deletions(-)
Makefile +10 -6
index fc9d89498b..fd4421eeb8 100644
@@ -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
Signature · 1 line
2.12.0-317-g32c43f595f
#12 lore raw

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

In reply to Junio C Hamano
Quoted 19 lines · 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

Quoted 9 lines
 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.

Makefile +4 -4
index b01111c581..fc9d89498b 100644
@@ -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
hash.h +1 -1
index 3760f436ec..a11fc9233f 100644
@@ -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"
t/t0013-sha1dc.sh +2 -2
index 4d43f7bf64..6d655cb161 100755
@@ -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
 
#13 lore raw

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

In reply to Junio C Hamano
Quoted 11 lines · 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.

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

#14 lore raw
In reply to Jeff King
Quoted 9 lines · Jeff King

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

#15 lore raw
Quoted 11 lines · Jeff King
Quoted 9 lines · Jeff King

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.

Quoted 5 lines

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.

#16 lore raw
Quoted 4 lines · Junio C Hamano

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

#17 lore raw
Quoted 13 lines · Jeff King
Quoted 4 lines · Junio C Hamano

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.

Quoted 5 lines

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.

#18 lore raw
Quoted 5 lines · Junio C Hamano

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

#19 lore raw
In reply to Jeff King
Quoted 7 lines · Jeff King

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.

Quoted 6 lines

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