crypto/rsa: severe VerifyPKCS1v15 performance regression in Go 1.20, Go 1.21 [freeze exception]

[nkatsaros]

What version of Go are you using (go version)?

$ go version
go version go1.21.3 linux/amd64

Does this issue reproduce with the latest release?

Yes, with the latest releases of Go 1.20 and Go 1.21.

What operating system and processor architecture are you using (go env)?

go env Output

$ ./go1.21.3.linux-amd64/bin/go env
GO111MODULE=''
GOARCH='amd64'
GOBIN=''
GOCACHE='/home/user/.cache/go-build'
GOENV='/home/user/.config/go/env'
GOEXE=''
GOEXPERIMENT=''
GOFLAGS=''
GOHOSTARCH='amd64'
GOHOSTOS='linux'
GOINSECURE=''
GOMODCACHE='/home/user/go/pkg/mod'
GONOPROXY=''
GONOSUMDB=''
GOOS='linux'
GOPATH='/home/user/go'
GOPRIVATE=''
GOPROXY='https://proxy.golang.org,direct'
GOROOT='/home/user/gorsabench/go1.21.3.linux-amd64'
GOSUMDB='sum.golang.org'
GOTMPDIR=''
GOTOOLCHAIN='auto'
GOTOOLDIR='/home/user/gorsabench/go1.21.3.linux-amd64/pkg/tool/linux_amd64'
GOVCS=''
GOVERSION='go1.21.3'
GCCGO='gccgo'
GOAMD64='v1'
AR='ar'
CC='gcc'
CXX='g++'
CGO_ENABLED='1'
GOMOD='/dev/null'
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-build1639202501=/tmp/go-build -gno-record-gcc-switches'

What did you do?

Some of our services started seeing severe performance degradation after upgrading to Go 1.20. Applications which verify many RS256 signed JWT tokens saw dramatic increases to CPU usage and profiles indicated that rsa.VerifyPKCS1v15 was the problematic function call.

I copied the BenchmarkVerifyPKCS1v15 benchmark to Go 1.19 and ran benchmarks on Go 1.19.13, Go 1.20.10, Go 1.21.3 and Go 1.21.3+boringcrypto. I've filtered the benchmarks to only include the VerifyPKCS1v15 benchmark since that was the easiest to copy to Go 1.19, however, anything that calls rsa.go's encrypt() is affected.

% benchstat go1.19.13.linux-amd64.txt go1.20.10.linux-amd64.txt go1.21.3.linux-amd64.txt go1.21.3.linux-amd64-boringcrypto.txt
goos: linux
goarch: amd64
pkg: crypto/rsa
cpu: Intel(R) Xeon(R) Platinum 8124M CPU @ 3.00GHz
                       │ go1.19.13.linux-amd64.txt │         go1.20.10.linux-amd64.txt         │         go1.21.3.linux-amd64.txt         │ go1.21.3.linux-amd64-boringcrypto.txt │
                       │          sec/op           │     sec/op      vs base                   │    sec/op      vs base                   │    sec/op     vs base                 │
VerifyPKCS1v15/2048-4                  8.053µ ± 8%   216.550µ ±  7%  +2589.05% (p=0.002 n=6)     121.072µ ± 1%  +1403.43% (p=0.002 n=6)     5.664µ ± 14%  -29.67% (p=0.002 n=6)

I've been following these performance regressions (see #59442) and assumed they were fixed in Go 1.21. Go 1.21 mostly fixed the performance of RSA Private Key operations.

Our solution to retain performance, avoid massively scaling and remain on a recent version of Go is to compile with GOEXPERIMENT=boringcrypto which does not seem like a reasonable long term solution.

The encrypt function contains a comment regarding a possible optimization using a sync.Once.

func encrypt(pub *PublicKey, plaintext []byte) ([]byte, error) {
	boring.Unreachable()

	// Most of the CPU time for encryption and verification is spent in this
	// NewModulusFromBig call, because PublicKey doesn't have a Precomputed
	// field. If performance becomes an issue, consider placing a private
	// sync.Once on PublicKey to compute this.
	N, err := bigmod.NewModulusFromBig(pub.N)
	if err != nil {
		return nil, err
	}
	m, err := bigmod.NewNat().SetBytes(plaintext, N)
	if err != nil {
		return nil, err
	}
	e := uint(pub.E)

	return bigmod.NewNat().ExpShort(m, e, N).Bytes(N), nil
}

I have a modification to my local Go 1.21 tree that contains this fix and caches bigmod.NewModulusFromBig(pub.N). It brings performance closer to Go 1.19 (~67% worse on my M1 MacBook Pro). I do not think a patch containing this fix would be accepted. Adding a sync.Once to rsa.PublicKey introduces a few issues:

• rsa.PublicKey is no longer asn1.Marshalable. This expectation is documented in a comment within TestMarshalPKCS1PublicKey

  // It's never been documented that asn1.Marshal/Unmarshal on rsa.PublicKey works,
  // but it does, and we know of code that depends on it.
  // Lock that in, even though we'd prefer that people use MarshalPKCS1PublicKey and ParsePKCS1PublicKey.
  

• It's a weird use of sync.Once which I don't commonly see in the stdlib.

I think a proper change would require exposing some kind of Precompute() functionality on rsa.PublicKey but I think that would still break the asn1.Marshal expectation.

What did you expect to see?

Similar performance to Go 1.19.

What did you see instead?

VerifyPKCS1v15 operations are ~25x slower in Go 1.20 and ~14x slower in Go 1.21.

[bcmills]

See also #57752.

[tareksha]

Confirming the issue here too. In our system we have a component that executes rsa operations at high rates and the critical part that calls rsa.VerifyPKCS1v15 is approximately twice slower when upgrading from 1.19 to 1.21. We had to revert back to 1.19.
Previously we had to revert from go 1.20 due to the same reason.

[dmitshur]

CC @golang/security.

[gopherbot]

Change https://go.dev/cl/552895 mentions this issue: crypto/rsa: use E = 65537 in benchmarks

[gopherbot]

Change https://go.dev/cl/552935 mentions this issue: crypto/rsa,crypto/internal/bigmod: improve verify/encrypt performance

[FiloSottile]

Turns out we were benchmarking the wrong thing: all the benchmark keys had E = 3, which hid the algorithmic slowdown on the exponent size. See https://go.dev/cl/552895. Apologies, I am really not happy this happened, and that it took me so long to catch it.

I have a CL out that makes public key operations faster than they were in Go 1.19, closing the loop on all the performance regressions.

I'd appreciate if folks could test this with their workloads.

gotip download 552935
gotip build

(This will get you something not too dissimilar from Go 1.22rc1, with the CL patched on top. I wouldn't run the whole fleet on it, but it should be stable enough for a lab.)

[mateusz834]

So it turns out that the go1.19 -> go.1.20 (real-world) Verify operations were only slower by x4, not by x20 as noted in the release notes, right?

https://go.dev/doc/go1.20#cryptorsapkgcryptorsa
https://go.dev/cl/452095

Encryption operations are approximately 20x slower than before

[tareksha]

hi @FiloSottile is this fix being downported to 1.21?

[FiloSottile]

@golang/release, @rsc suggested getting this freeze exception'd rather than backported.

[dmitshur]

We've discussed and agreed to approve this freeze exception for Go 1.22. If this change turns out not to go as anticipated, please update the issue and follow up accordingly. Thanks.

[FiloSottile]

Submitted to master.