Why own sha-3 implementation?

[UladzimirTrehubenka]

The project is using internal/sha3 which is derived from golang.org/x/crypto/sha3.
As I understand the main reason is some fundamental issues (and some optimizations/improvements).
However if so is it possible to contribute improved sha3 code to the golang std lib and use it instead own implementation?

[bwesterb]

First, what is your concern for the fork?

One big reason we keep the fork is that we expose the underlying struct, so that we can use SHA3 without having to move the inputs to the heap. (Google "golang heap escapes".) That reduces allocation significantly, which would otherwise be a big bottleneck in cryptographic primitives such as Kyber. This application is kind of niche and I doubt upstream would take that.

Also there are parallel implementations of SHA3, which again are very useful for cryptographic primitives such as Kyber.

[UladzimirTrehubenka]

This is not a concern, just for now as I understand std golang sha3 is not so good/fast as sha3 from the project.
But nobody can use sha3 from the project because it is unexported (internal).

[bwesterb]

For implementing PQC you'd want to use the low-level SIMD version, which is public. For usual applications (like hashing a file), the difference between our implementation and the upstream API should be minimal.

[VladimirTregubenko]

BTW for now I don't see a significant difference in performance:
commit d26845f

go test -bench="BenchmarkSha3|BenchmarkShake"
goos: linux
goarch: amd64
pkg: github.com/cloudflare/circl/internal/sha3
cpu: AMD Ryzen 9 3900X 12-Core Processor            
BenchmarkSha3_512_MTU-24     	  173608	      6850 ns/op	 197.09 MB/s
BenchmarkSha3_384_MTU-24     	  242770	      4928 ns/op	 273.92 MB/s
BenchmarkSha3_256_MTU-24     	  307231	      3907 ns/op	 345.56 MB/s
BenchmarkSha3_224_MTU-24     	  323571	      3710 ns/op	 363.84 MB/s
BenchmarkShake128_MTU-24     	  380232	      3153 ns/op	 428.10 MB/s
BenchmarkShake256_MTU-24     	  347889	      3446 ns/op	 391.73 MB/s
BenchmarkShake256_16x-24     	   24442	     51151 ns/op	 320.30 MB/s
BenchmarkShake256_1MiB-24    	     444	   2676574 ns/op	 391.76 MB/s
BenchmarkSha3_512_1MiB-24    	     241	   4969454 ns/op	 211.00 MB/s
PASS
ok  	github.com/cloudflare/circl/internal/sha3	12.387s

vs.
commit 3375612

go test -bench="BenchmarkSha3|BenchmarkShake"
goos: linux
goarch: amd64
pkg: golang.org/x/crypto/sha3
cpu: AMD Ryzen 9 3900X 12-Core Processor            
BenchmarkSha3_512_MTU-24     	  175977	      6810 ns/op	 198.23 MB/s
BenchmarkSha3_384_MTU-24     	  245632	      4888 ns/op	 276.17 MB/s
BenchmarkSha3_256_MTU-24     	  308929	      3876 ns/op	 348.32 MB/s
BenchmarkSha3_224_MTU-24     	  324548	      3696 ns/op	 365.22 MB/s
BenchmarkShake128_MTU-24     	  365518	      3279 ns/op	 411.68 MB/s
BenchmarkShake256_MTU-24     	  346371	      3467 ns/op	 389.40 MB/s
BenchmarkShake256_16x-24     	   24466	     48822 ns/op	 335.59 MB/s
BenchmarkShake256_1MiB-24    	     450	   2661981 ns/op	 393.91 MB/s
BenchmarkSha3_512_1MiB-24    	     240	   4976664 ns/op	 210.70 MB/s
PASS
ok  	golang.org/x/crypto/sha3	12.352s

[bwesterb]

You don't notice the heap escape issue in this microbenchmark, but you do notice it when you're using one or the other inside, say, Kyber.

[UladzimirTrehubenka]

BTW golang.org/x/crypto has already improvements sha3: make APIs usable with zero allocations (May 8, 2024) similar to sha3: prevent state from escaping to heap (Sep 17, 2021).

[paocalvi]

Is there any chance that CIRCL sha3 implementation will someday be 100% FIPS compliant?
golang (now embedded as absorbed from x/crypto to golang/crypto) implementation is not finished as it miss the bit-oriented implementation and half of the CAVP test vectors are impossible to run.
This is an old flaw affecting the SHA2 implementations, too.
Having brought the implementation inside the core makes now even more difficult to work it around.
Should be very nice if CIRCL could provide this missing part.

Paolo

[bwesterb]

Is there any chance that CIRCL sha3 implementation will someday be 100% FIPS compliant?

What do you mean with that? Our SHA3 implementation follows the standard correctly. On the other hand, we have no plan to attain an CMVP certificate.

[paocalvi]

Sorry for not being totally clear and thanks for reading.
I just meant that FIPS 202 para 5.1 (and consequently the example in B.2) are not implemented, and a sequence of bits is only hashable if the length is a multiple of 8 bits.
I know that most use cases foresee to hash an integer number of BYTES, but the FIPS 202 standard is definitely wider than just that.

In fact half of the TV of the official CAVP (https://csrc.nist.gov/projects/cryptographic-algorithm-validation-program/secure-hashing) cannot be verified with the golang core library nor with the CIRCL implementation (i.e. https://csrc.nist.gov/CSRC/media/Projects/Cryptographic-Algorithm-Validation-Program/documents/sha3/sha-3bittestvectors.zip), and it's a pity.

Paolo