sha1: Add collision resistent implementation

Implement the same SHA1 collision resistent algorithm used by both the
Git CLI and libgit2.

Only commits with input that match the unavoidable bit conditions will be further
processed, which will result in different hashes.
Which is the same behaviour experienced in the Git CLI and Libgit2.

Users can override the hash algorithm used with:

hash.RegisterHash(crypto.SHA1, sha1.New)

xref links:
https://github.com/libgit2/libgit2/pull/4136/commits/2dfd1294f7a694bfa9e864a9489ae3cb318a5ed0
https://github.com/git/git/commit/28dc98e343ca4eb370a29ceec4c19beac9b5c01e

Signed-off-by: Paulo Gomes <pjbgf@linux.com>

10 files changed, 184 insertions, 17 deletions

diff --git a/go.mod b/go.mod
index 68bafbd..ee0c196 100644
--- a/go.mod
+++ b/go.mod
@@ -16,6 +16,7 @@ require (
 	github.com/jbenet/go-context v0.0.0-20150711004518-d14ea06fba99
 	github.com/jessevdk/go-flags v1.5.0
 	github.com/kevinburke/ssh_config v0.0.0-20201106050909-4977a11b4351
+	github.com/pjbgf/sha1cd v0.2.0
 	github.com/sergi/go-diff v1.1.0
 	github.com/skeema/knownhosts v1.1.0
 	github.com/xanzy/ssh-agent v0.3.1
diff --git a/go.sum b/go.sum
index 4bda7c4..775e89a 100644
--- a/go.sum
+++ b/go.sum
@@ -44,6 +44,8 @@ github.com/kr/text v0.2.0/go.mod h1:eLer722TekiGuMkidMxC/pM04lWEeraHUUmBw8l2grE=
 github.com/matryer/is v1.2.0 h1:92UTHpy8CDwaJ08GqLDzhhuixiBUUD1p3AU6PHddz4A=
 github.com/matryer/is v1.2.0/go.mod h1:2fLPjFQM9rhQ15aVEtbuwhJinnOqrmgXPNdZsdwlWXA=
 github.com/niemeyer/pretty v0.0.0-20200227124842-a10e7caefd8e/go.mod h1:zD1mROLANZcx1PVRCS0qkT7pwLkGfwJo4zjcN/Tysno=
+github.com/pjbgf/sha1cd v0.2.0 h1:gIsJVwjbRviE4gydidGztxH1IlJQoYBcCrwG4Dz8wvM=
+github.com/pjbgf/sha1cd v0.2.0/go.mod h1:HOK9QrgzdHpbc2Kzip0Q1yi3M2MFGPADtR6HjG65m5M=
 github.com/pkg/errors v0.9.1 h1:FEBLx1zS214owpjy7qsBeixbURkuhQAwrK5UwLGTwt4=
 github.com/pkg/errors v0.9.1/go.mod h1:bwawxfHBFNV+L2hUp1rHADufV3IMtnDRdf1r5NINEl0=
 github.com/pmezard/go-difflib v1.0.0 h1:4DBwDE0NGyQoBHbLQYPwSUPoCMWR5BEzIk/f1lZbAQM=
diff --git a/plumbing/format/commitgraph/encoder.go b/plumbing/format/commitgraph/encoder.go
index d34076f..bcf7d03 100644
--- a/plumbing/format/commitgraph/encoder.go
+++ b/plumbing/format/commitgraph/encoder.go
@@ -1,11 +1,11 @@
 package commitgraph

 

 import (

-	"crypto/sha1"

-	"hash"

+	"crypto"

 	"io"

 

 	"github.com/go-git/go-git/v5/plumbing"

+	"github.com/go-git/go-git/v5/plumbing/hash"

 	"github.com/go-git/go-git/v5/utils/binary"

 )

 

@@ -17,7 +17,7 @@ type Encoder struct {
 

 // NewEncoder returns a new stream encoder that writes to w.

 func NewEncoder(w io.Writer) *Encoder {

-	h := sha1.New()

+	h := hash.New(crypto.SHA1)

 	mw := io.MultiWriter(w, h)

 	return &Encoder{mw, h}

 }

diff --git a/plumbing/format/idxfile/encoder.go b/plumbing/format/idxfile/encoder.go
index 26b2e4d..6ac445f 100644
--- a/plumbing/format/idxfile/encoder.go
+++ b/plumbing/format/idxfile/encoder.go
@@ -1,10 +1,10 @@
 package idxfile
 
 import (
-	"crypto/sha1"
-	"hash"
+	"crypto"
 	"io"
 
+	"github.com/go-git/go-git/v5/plumbing/hash"
 	"github.com/go-git/go-git/v5/utils/binary"
 )
 
@@ -16,7 +16,7 @@ type Encoder struct {
 
 // NewEncoder returns a new stream encoder that writes to w.
 func NewEncoder(w io.Writer) *Encoder {
-	h := sha1.New()
+	h := hash.New(crypto.SHA1)
 	mw := io.MultiWriter(w, h)
 	return &Encoder{mw, h}
 }
diff --git a/plumbing/format/index/decoder.go b/plumbing/format/index/decoder.go
index 036b636..c4da20c 100644
--- a/plumbing/format/index/decoder.go
+++ b/plumbing/format/index/decoder.go
@@ -3,15 +3,15 @@ package index
 import (
 	"bufio"
 	"bytes"
-	"crypto/sha1"
+	"crypto"
 	"errors"
-	"hash"
 	"io"
 	"io/ioutil"
 	"strconv"
 	"time"
 
 	"github.com/go-git/go-git/v5/plumbing"
+	"github.com/go-git/go-git/v5/plumbing/hash"
 	"github.com/go-git/go-git/v5/utils/binary"
 )
 
@@ -49,7 +49,7 @@ type Decoder struct {
 
 // NewDecoder returns a new decoder that reads from r.
 func NewDecoder(r io.Reader) *Decoder {
-	h := sha1.New()
+	h := hash.New(crypto.SHA1)
 	return &Decoder{
 		r:         io.TeeReader(r, h),
 		hash:      h,
diff --git a/plumbing/format/index/encoder.go b/plumbing/format/index/encoder.go
index 2c94d93..a915378 100644
--- a/plumbing/format/index/encoder.go
+++ b/plumbing/format/index/encoder.go
@@ -2,13 +2,13 @@ package index
 
 import (
 	"bytes"
-	"crypto/sha1"
+	"crypto"
 	"errors"
-	"hash"
 	"io"
 	"sort"
 	"time"
 
+	"github.com/go-git/go-git/v5/plumbing/hash"
 	"github.com/go-git/go-git/v5/utils/binary"
 )
 
@@ -29,7 +29,7 @@ type Encoder struct {
 
 // NewEncoder returns a new encoder that writes to w.
 func NewEncoder(w io.Writer) *Encoder {
-	h := sha1.New()
+	h := hash.New(crypto.SHA1)
 	mw := io.MultiWriter(w, h)
 	return &Encoder{mw, h}
 }
diff --git a/plumbing/format/packfile/encoder.go b/plumbing/format/packfile/encoder.go
index 5501f88..a8a7e96 100644
--- a/plumbing/format/packfile/encoder.go
+++ b/plumbing/format/packfile/encoder.go
@@ -2,11 +2,12 @@ package packfile
 
 import (
 	"compress/zlib"
-	"crypto/sha1"
+	"crypto"
 	"fmt"
 	"io"
 
 	"github.com/go-git/go-git/v5/plumbing"
+	"github.com/go-git/go-git/v5/plumbing/hash"
 	"github.com/go-git/go-git/v5/plumbing/storer"
 	"github.com/go-git/go-git/v5/utils/binary"
 	"github.com/go-git/go-git/v5/utils/ioutil"
@@ -28,7 +29,7 @@ type Encoder struct {
 // OFSDeltaObject. To use Reference deltas, set useRefDeltas to true.
 func NewEncoder(w io.Writer, s storer.EncodedObjectStorer, useRefDeltas bool) *Encoder {
 	h := plumbing.Hasher{
-		Hash: sha1.New(),
+		Hash: hash.New(crypto.SHA1),
 	}
 	mw := io.MultiWriter(w, h)
 	ow := newOffsetWriter(mw)
diff --git a/plumbing/hash.go b/plumbing/hash.go
index afc602a..2fab759 100644
--- a/plumbing/hash.go
+++ b/plumbing/hash.go
@@ -2,11 +2,12 @@ package plumbing
 
 import (
 	"bytes"
-	"crypto/sha1"
+	"crypto"
 	"encoding/hex"
-	"hash"
 	"sort"
 	"strconv"
+
+	"github.com/go-git/go-git/v5/plumbing/hash"
 )
 
 // Hash SHA1 hashed content
@@ -46,7 +47,7 @@ type Hasher struct {
 }
 
 func NewHasher(t ObjectType, size int64) Hasher {
-	h := Hasher{sha1.New()}
+	h := Hasher{hash.New(crypto.SHA1)}
 	h.Write(t.Bytes())
 	h.Write([]byte(" "))
 	h.Write([]byte(strconv.FormatInt(size, 10)))
diff --git a/plumbing/hash/hash.go b/plumbing/hash/hash.go
new file mode 100644
index 0000000..fe3bf76
--- /dev/null
+++ b/plumbing/hash/hash.go
@@ -0,0 +1,59 @@
+// package hash provides a way for managing the
+// underlying hash implementations used across go-git.
+package hash
+
+import (
+	"crypto"
+	"fmt"
+	"hash"
+
+	"github.com/pjbgf/sha1cd/cgo"
+)
+
+// algos is a map of hash algorithms.
+var algos = map[crypto.Hash]func() hash.Hash{}
+
+func init() {
+	reset()
+}
+
+// reset resets the default algos value. Can be used after running tests
+// that registers new algorithms to avoid side effects.
+func reset() {
+	// For performance reasons the cgo version of the collision
+	// detection algorithm is being used.
+	algos[crypto.SHA1] = cgo.New
+}
+
+// RegisterHash allows for the hash algorithm used to be overriden.
+// This ensures the hash selection for go-git must be explicit, when
+// overriding the default value.
+func RegisterHash(h crypto.Hash, f func() hash.Hash) error {
+	if f == nil {
+		return fmt.Errorf("cannot register hash: f is nil")
+	}
+
+	switch h {
+	case crypto.SHA1:
+		algos[h] = f
+	default:
+		return fmt.Errorf("unsupported hash function: %v", h)
+	}
+	return nil
+}
+
+// Hash is the same as hash.Hash. This allows consumers
+// to not having to import this package alongside "hash".
+type Hash interface {
+	hash.Hash
+}
+
+// New returns a new Hash for the given hash function.
+// It panics if the hash function is not registered.
+func New(h crypto.Hash) Hash {
+	hh, ok := algos[h]
+	if !ok {
+		panic(fmt.Sprintf("hash algorithm not registered: %v", h))
+	}
+	return hh()
+}
diff --git a/plumbing/hash/hash_test.go b/plumbing/hash/hash_test.go
new file mode 100644
index 0000000..f70ad11
--- /dev/null
+++ b/plumbing/hash/hash_test.go
@@ -0,0 +1,103 @@
+package hash
+
+import (
+	"crypto"
+	"crypto/sha1"
+	"crypto/sha512"
+	"encoding/hex"
+	"hash"
+	"strings"
+	"testing"
+)
+
+func TestRegisterHash(t *testing.T) {
+	// Reset default hash to avoid side effects.
+	defer reset()
+
+	tests := []struct {
+		name    string
+		hash    crypto.Hash
+		new     func() hash.Hash
+		wantErr string
+	}{
+		{
+			name: "sha1",
+			hash: crypto.SHA1,
+			new:  sha1.New,
+		},
+		{
+			name:    "sha1",
+			hash:    crypto.SHA1,
+			wantErr: "cannot register hash: f is nil",
+		},
+		{
+			name:    "sha512",
+			hash:    crypto.SHA512,
+			new:     sha512.New,
+			wantErr: "unsupported hash function",
+		},
+	}
+
+	for _, tt := range tests {
+		t.Run(tt.name, func(t *testing.T) {
+			err := RegisterHash(tt.hash, tt.new)
+			if tt.wantErr == "" && err != nil {
+				t.Errorf("unexpected error: %v", err)
+			} else if tt.wantErr != "" && err == nil {
+				t.Errorf("expected error: %v got: nil", tt.wantErr)
+			} else if err != nil && !strings.Contains(err.Error(), tt.wantErr) {
+				t.Errorf("expected error: %v got: %v", tt.wantErr, err)
+			}
+		})
+	}
+}
+
+// Verifies that the SHA1 implementation used is collision-resistant
+// by default.
+func TestSha1Collision(t *testing.T) {
+	defer reset()
+
+	tests := []struct {
+		name    string
+		content string
+		hash    string
+		before  func()
+	}{
+		{
+			name:    "sha-mbles-1: with collision detection",
+			content: "99040d047fe81780012000ff4b65792069732070617274206f66206120636f6c6c6973696f6e212049742773206120747261702179c61af0afcc054515d9274e7307624b1dc7fb23988bb8de8b575dba7b9eab31c1674b6d974378a827732ff5851c76a2e60772b5a47ce1eac40bb993c12d8c70e24a4f8d5fcdedc1b32c9cf19e31af2429759d42e4dfdb31719f587623ee552939b6dcdc459fca53553b70f87ede30a247ea3af6c759a2f20b320d760db64ff479084fd3ccb3cdd48362d96a9c430617caff6c36c637e53fde28417f626fec54ed7943a46e5f5730f2bb38fb1df6e0090010d00e24ad78bf92641993608e8d158a789f34c46fe1e6027f35a4cbfb827076c50eca0e8b7cca69bb2c2b790259f9bf9570dd8d4437a3115faff7c3cac09ad25266055c27104755178eaeff825a2caa2acfb5de64ce7641dc59a541a9fc9c756756e2e23dc713c8c24c9790aa6b0e38a7f55f14452a1ca2850ddd9562fd9a18ad42496aa97008f74672f68ef461eb88b09933d626b4f918749cc027fddd6c425fc4216835d0134d15285bab2cb784a4f7cbb4fb514d4bf0f6237cf00a9e9f132b9a066e6fd17f6c42987478586ff651af96747fb426b9872b9a88e4063f59bb334cc00650f83a80c42751b71974d300fc2819a2e8f1e32c1b51cb18e6bfc4db9baef675d4aaf5b1574a047f8f6dd2ec153a93412293974d928f88ced9363cfef97ce2e742bf34c96b8ef3875676fea5cca8e5f7dea0bab2413d4de00ee71ee01f162bdb6d1eafd925e6aebaae6a354ef17cf205a404fbdb12fc454d41fdd95cf2459664a2ad032d1da60a73264075d7f1e0d6c1403ae7a0d861df3fe5707188dd5e07d1589b9f8b6630553f8fc352b3e0c27da80bddba4c64020d",
+			hash:    "4f3d9be4a472c4dae83c6314aa6c36a064c1fd14",
+		},
+		{
+			name:    "sha-mbles-1: with default SHA1",
+			content: "99040d047fe81780012000ff4b65792069732070617274206f66206120636f6c6c6973696f6e212049742773206120747261702179c61af0afcc054515d9274e7307624b1dc7fb23988bb8de8b575dba7b9eab31c1674b6d974378a827732ff5851c76a2e60772b5a47ce1eac40bb993c12d8c70e24a4f8d5fcdedc1b32c9cf19e31af2429759d42e4dfdb31719f587623ee552939b6dcdc459fca53553b70f87ede30a247ea3af6c759a2f20b320d760db64ff479084fd3ccb3cdd48362d96a9c430617caff6c36c637e53fde28417f626fec54ed7943a46e5f5730f2bb38fb1df6e0090010d00e24ad78bf92641993608e8d158a789f34c46fe1e6027f35a4cbfb827076c50eca0e8b7cca69bb2c2b790259f9bf9570dd8d4437a3115faff7c3cac09ad25266055c27104755178eaeff825a2caa2acfb5de64ce7641dc59a541a9fc9c756756e2e23dc713c8c24c9790aa6b0e38a7f55f14452a1ca2850ddd9562fd9a18ad42496aa97008f74672f68ef461eb88b09933d626b4f918749cc027fddd6c425fc4216835d0134d15285bab2cb784a4f7cbb4fb514d4bf0f6237cf00a9e9f132b9a066e6fd17f6c42987478586ff651af96747fb426b9872b9a88e4063f59bb334cc00650f83a80c42751b71974d300fc2819a2e8f1e32c1b51cb18e6bfc4db9baef675d4aaf5b1574a047f8f6dd2ec153a93412293974d928f88ced9363cfef97ce2e742bf34c96b8ef3875676fea5cca8e5f7dea0bab2413d4de00ee71ee01f162bdb6d1eafd925e6aebaae6a354ef17cf205a404fbdb12fc454d41fdd95cf2459664a2ad032d1da60a73264075d7f1e0d6c1403ae7a0d861df3fe5707188dd5e07d1589b9f8b6630553f8fc352b3e0c27da80bddba4c64020d",
+			hash:    "8ac60ba76f1999a1ab70223f225aefdc78d4ddc0",
+			before: func() {
+				RegisterHash(crypto.SHA1, sha1.New)
+			},
+		},
+	}
+
+	for _, tt := range tests {
+		t.Run(tt.name, func(t *testing.T) {
+			if tt.before != nil {
+				tt.before()
+			}
+
+			h := New(crypto.SHA1)
+			data, err := hex.DecodeString(tt.content)
+			if err != nil {
+				t.Fatal(err)
+			}
+
+			h.Reset()
+			h.Write(data)
+			sum := h.Sum(nil)
+			got := hex.EncodeToString(sum)
+
+			if tt.hash != got {
+				t.Errorf("\n   got: %q\nwanted: %q", got, tt.hash)
+			}
+		})
+	}
+}