Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

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

Open
Yawning opened this issue Mar 10, 2024 · 7 comments · May be fixed by golang/crypto#286
Open

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

Yawning opened this issue Mar 10, 2024 · 7 comments · May be fixed by golang/crypto#286
Labels
NeedsFix The path to resolution is known, but the work has not been done.
Milestone
Unreleased

Comments

@Yawning
Copy link

Yawning commented Mar 10, 2024

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.
@gopherbot gopherbot added this to the Unreleased milestone Mar 10, 2024
@FiloSottile FiloSottile added the NeedsFix The path to resolution is known, but the work has not been done. label Mar 11, 2024
@FiloSottile
Copy link
Contributor

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

@MingLLuo
Copy link

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~

@MingLLuo MingLLuo mentioned this issue Mar 11, 2024
Closed
@Yawning
Copy link
Author

Yawning commented Mar 11, 2024

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
Copy link

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
Copy link
Contributor

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
Copy link
Author

Yawning commented Mar 11, 2024

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.

Yawning added a commit to Yawning/crypto that referenced this issue Mar 11, 2024
@Yawning
sha3: fix cSHAKE initialization for extremely large N ana and or S
ca7a141 
While both impractical and unlikely, the multiplication could overflow
on 32-bit architectures.

The 64-bit architecture case is unaffected by both the maximum length
of Go slices being too small to trigger the overflow (everything except
s390), and it being safe to assume no machine has more than 2 EiB of
memory.

Fixes golang/go#66232
Yawning added a commit to Yawning/crypto that referenced this issue Mar 11, 2024
@Yawning
sha3: fix cSHAKE initialization for extremely large N and or S
503e180 
While both impractical and unlikely, the multiplication could overflow
on 32-bit architectures.

The 64-bit architecture case is unaffected by both the maximum length
of Go slices being too small to trigger the overflow (everything except
s390), and it being safe to assume no machine has more than 2 EiB of
memory.

Fixes golang/go#66232
@Yawning Yawning linked a pull request Mar 11, 2024 that will close this issue
Open
@gopherbot
Copy link

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
NeedsFix The path to resolution is known, but the work has not been done.
Projects
None yet
Milestone
Unreleased
4 participants
@FiloSottile @Yawning @gopherbot @MingLLuo