crypto/sha1: add native SHA1 instruction implementation for AMD64

[BenLubar]

I've transliterated the Linux kernel version of native SHA1 instructions to Go's flavor of assembly. The result is a 1.5x to 3x speed-up on my Ryzen 5 1600. Could this be included in Go, similar to the AVX2 implementation that is already in crypto/sha1?

[dsnet]

\cc @FiloSottile

[agnivade]

A quick note on our assembly policy - https://github.com/golang/go/wiki/AssemblyPolicy.

[ALTree]

I've transliterated the Linux kernel version of native SHA1 instructions to Go's flavor of assembly.

It's not allowed to translate/port GPL code and then include it in a BSD-licensed project.

EDIT: Ah, I see that that file has dual BSD/GPLv2. It should be ok.

[BenLubar]

The existing Go AVX implementation has a similar source:

go/src/crypto/sha1/sha1block_amd64.s

Lines 5 to 11 in 317afdc

	// AVX2 version by Intel, same algorithm as code in Linux kernel:
	// https://github.com/torvalds/linux/blob/master/arch/x86/crypto/sha1_avx2_x86_64_asm.S
	// Authors:
	// Ilya Albrekht <ilya.albrekht@intel.com>
	// Maxim Locktyukhin <maxim.locktyukhin@intel.com>
	// Ronen Zohar <ronen.zohar@intel.com>
	// Chandramouli Narayanan <mouli@linux.intel.com>

[TocarIP]

As far as I understand (and I'm not a lawyer) , problematic part is a copyright. I don't think that translating some piece of code removes the copyright of the original author, so submitting it to go isn't possible due to copyright transfer required by go CLA. Moving sha1 code was possible because original copyright holder (Intel) has CLA with google/go. It would be better if someone wrote a clean implementation from scratch.

[BenLubar]

Someone could contact one of the authors listed here:

https://github.com/torvalds/linux/blob/2601dd392dd1cabd11935448c0afe3293feb27a3/arch/x86/crypto/sha1_ni_asm.S#L20-L22

I'm pretty sure the only thing stopping Intel from submitting this code is that nobody has asked them to do it yet.

[FiloSottile]

A couple annoying legal clarifications: the CLA is not a copyright transfer, the original owner retains copyright; the original owner must not only have a CLA on file, but also give permission to submit the code under the CLA (either in writing or by sending the contribution themselves); and while we can take in BSD licensed code without a CLA, we have to carry its LICENSE notice and wall it off from the rest of the code, so we only do it when it's really worth it.

All that said, please do read the https://github.com/golang/go/wiki/AssemblyPolicy, it looks like those loops could be neatly generated, for example.

[gopherbot]

Change https://golang.org/cl/135378 mentions this issue: crypto/sha1: use SHA instructions on amd64, when possible

[TocarIP]

@BenLubar could you please check that https://go-review.googlesource.com/c/go/+/135378 works

[BenLubar]

Looks good to me.

ben@urist:~/go-16687a3bbfa27280d16eaa89e72833b7d7579a79/src$ ../bin/go test -bench . -benchmem crypto/sha1
goos: linux
goarch: amd64
pkg: crypto/sha1
BenchmarkHash8Bytes-12          10000000               153 ns/op          52.05 MB/s           0 B/op          0 allocs/op
BenchmarkHash320Bytes-12         2000000               619 ns/op         516.91 MB/s           0 B/op          0 allocs/op
BenchmarkHash1K-12               1000000              1285 ns/op         796.38 MB/s           0 B/op          0 allocs/op
BenchmarkHash8K-12                200000              8438 ns/op         970.85 MB/s           0 B/op          0 allocs/op
PASS
ok      crypto/sha1     6.688s

ben@urist:~/go-ecf65bbde81f199c131545ea794a6ff8dd629ff3/src$ ../bin/go test -bench . -benchmem crypto/sha1
goos: linux
goarch: amd64
pkg: crypto/sha1
BenchmarkHash8Bytes-12          20000000                85.3 ns/op        93.81 MB/s           0 B/op          0 allocs/op
BenchmarkHash320Bytes-12         5000000               253 ns/op        1260.53 MB/s           0 B/op          0 allocs/op
BenchmarkHash1K-12               2000000               616 ns/op        1660.82 MB/s           0 B/op          0 allocs/op
BenchmarkHash8K-12                300000              4344 ns/op        1885.82 MB/s           0 B/op          0 allocs/op
PASS
ok      crypto/sha1     6.583s

[aead]

Apart from the legal issues here, SHA-1 is a broken hash function. (Even though it provides (2nd) pre-image resistance at the moment). We recently removed RC4 assembly because it's a broken primitive. Therefore I don't think it's justified to added more manually written assembler code for SHA-1.

[TocarIP]

@aead, SHA-1 may be broken for security purposes, but it is still widely used in other areas. If we use https://github.com/golang/go/wiki/Benchmarks as an representative sample of go programs, faster SHA-1 is beneficial , e. g. satori/go.uuid/BenchmarkNewV5 gets ~15% faster with https://golang.org/cl/135378
It is also used in git and (unfortunately) in older crypto-related stuff.

[aead]

@TocarIP Regarding git and legacy crypto:

• Git is going to support other hash functions. See e.g commit and the documentation
• Optimizing SHA-1 for legacy crypto also sounds a bit odd to me w.r.t. https://github.com/golang/go/wiki/AssemblyPolicy - esp. when assembler implementations (probably) won't be accepted for non-broken primitives - like proposal: crypto/tls: add support for AES-CCM #27484 (comment).

In addition for projects like satori/go.uuid there are other, better suited primitives available. However the asm patch is quite small. Here it's probably on the edge...