x/crypto/sha3: cSHAKE initialization misbehaves for extremely (unrealistically) large N or S

[Yawning]

Go version

go version go1.22.1 linux/amd64

Output of go env in your module/workspace:

GO111MODULE=''
GOARCH='amd64'
GOBIN=''
GOCACHE='[REDACTED]'
GOENV='[REDACTED]'
GOEXE=''
GOEXPERIMENT=''
GOFLAGS=''
GOHOSTARCH='amd64'
GOHOSTOS='linux'
GOINSECURE=''
GOMODCACHE='[REDACTED]'
GONOPROXY=''
GONOSUMDB=''
GOOS='linux'
GOPATH='[REDACTED]'
GOPRIVATE=''
GOPROXY='direct'
GOROOT='/usr/lib/go'
GOSUMDB='off'
GOTMPDIR=''
GOTOOLCHAIN='auto'
GOTOOLDIR='/usr/lib/go/pkg/tool/linux_amd64'
GOVCS=''
GOVERSION='go1.22.1'
GCCGO='gccgo'
GOAMD64='v1'
AR='ar'
CC='gcc'
CXX='g++'
CGO_ENABLED='1'
GOMOD='[REDACTED]'
GOWORK=''
CGO_CFLAGS='-O2 -g'
CGO_CPPFLAGS=''
CGO_CXXFLAGS='-O2 -g'
CGO_FFLAGS='-O2 -g'
CGO_LDFLAGS='-O2 -g'
PKG_CONFIG='pkg-config'
GOGCCFLAGS='-fPIC -m64 -pthread -Wl,--no-gc-sections -fmessage-length=0 -ffile-prefix-map=/tmp/go-build3832971843=/tmp/go-build -gno-record-gcc-switches'

What did you do?

Manual code review.

https://github.com/golang/crypto/blob/7067223927c4e3f3bb91a5c6e0d2aae83df74e7a/sha3/shake.go#L83

What did you see happen?

newCShake will silently misbehave if passed an extremely (unrealistically) large N or S, due to the multiply overflowing.

What did you expect to see?

There should be overflow checks for the multiplications in the following calls:
c.initBlock = append(c.initBlock, leftEncode(uint64(len(N)*8))...)
c.initBlock = append(c.initBlock, leftEncode(uint64(len(S)*8))...)

Alternatively leftEncode could be modified to support the full range of possible slice lengths.

[FiloSottile]

This can only happen if int is 32 bits, and can be fixed by switching to uint64(len(N))*8, right?

[MingLLuo]

following “cSHAKE implementations is based on NIST SP 800-185 [2]” 3.3 Definition, I think we should check the length validity, len(N) and len(S) should less than 2040bit(255 byte). I make a pr for this~

[Yawning]

This can only happen if int is 32 bits, and can be fixed by switching to uint64(len(N))*8, right?

Because the value is "length of N or S" in bits, 64 bit int can also overflow (though not on any current production silicon) with unfathomably large N or S, due to (2^63-1) * 8 overflowing.

following “cSHAKE implementations is based on NIST SP 800-185 [2]” 3.3 Definition, I think we should check the length validity, len(N) and len(S) should less than 2040bit(255 byte). I make a pr for this~

Unfortunately that's not correct. The upper limit for all N and S is "2^2040-1 bits".

[MingLLuo]

following “cSHAKE implementations is based on NIST SP 800-185 [2]” 3.3 Definition, I think we should check the length validity, len(N) and len(S) should less than 2040bit(255 byte). I make a pr for this~

Unfortunately that's not correct. The upper limit for all N and S is "2^2040-1 bits".

I misunderstood. You were right.

[FiloSottile]

This can only happen if int is 32 bits, and can be fixed by switching to uint64(len(N))*8, right?

Because the value is "length of N or S" in bits, 64 bit int can also overflow (though not on any current production silicon) with unfathomably large N or S, due to (2^63-1) * 8 overflowing.

The max length of a Go slice is 2^48, so len(x) * 8 is at most 51 bits.

go/src/runtime/malloc.go

Lines 213 to 218 in 3a41bfa

	// maxAlloc is the maximum size of an allocation. On 64-bit,
	// it's theoretically possible to allocate 1<<heapAddrBits bytes. On
	// 32-bit, however, this is one less than 1<<32 because the
	// number of bytes in the address space doesn't actually fit
	// in a uintptr.
	maxAlloc = (1 << heapAddrBits) - (1-_64bit)*1

Also, I think we can safely assume no machine has more than 2 exabyte of memory.

If we agree it would fix the 32-bit platforms and that 64-bit platforms are unaffected, I would appreciate a CL to switch to uint64(len(X))*8.

[Yawning]

The max length of a Go slice is 2^48, so len(x) * 8 is at most 51 bits.

go/src/runtime/malloc.go

Lines 213 to 218 in 3a41bfa

	// maxAlloc is the maximum size of an allocation. On 64-bit,
	// it's theoretically possible to allocate 1<<heapAddrBits bytes. On
	// 32-bit, however, this is one less than 1<<32 because the
	// number of bytes in the address space doesn't actually fit
	// in a uintptr.
	maxAlloc = (1 << heapAddrBits) - (1-_64bit)*1

Also, I think we can safely assume no machine has more than 2 exabyte of memory.

Ah ok. I didn't know about the limit on slice sizes. TIL.

If we agree it would fix the 32-bit platforms and that 64-bit platforms are unaffected, I would appreciate a CL to switch to uint64(len(X))*8.

The fix sounds good to me.

[gopherbot]

Change https://go.dev/cl/570876 mentions this issue: sha3: fix cSHAKE initialization for extremely large N and or S

[gopherbot]

Change https://go.dev/cl/616576 mentions this issue: sha3: fix padding for long cSHAKE parameters