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

crypto/rsa: RSA keys newly rejected in Go 1.24 #70643

Closed
rsc opened this issue Dec 2, 2024 · 12 comments
Closed

crypto/rsa: RSA keys newly rejected in Go 1.24 #70643

rsc opened this issue Dec 2, 2024 · 12 comments
Labels
NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. release-blocker
Milestone
Go1.24

Comments

@rsc
Copy link
Contributor

rsc commented Dec 2, 2024

This program works in Go 1.23 but fails in Go 1.24 with "invalid CRT coefficient".

The specific key is taken from a larger test that is now failing, because the key is rejected.

openssl rsa -in dummy.key -check -noout has no complaints about the key.

/cc @rolandshoemaker @FiloSottile

package main

import (
	"crypto/x509"
	"encoding/pem"
	"fmt"
)

var keyPEM = `-----BEGIN RSA PRIVATE KEY-----
MIIBOgIBAAJBAKj34GkxFhD90vcNLYLInFEX6Ppy1tPf9Cnzj4p4WGeKLs1Pt8Qu
KUpRKfFLfRYC9AIKjbJTWit+CqvjWYzvQwECAwEAAQJAIJLixBy2qpFoS4DSmoEm
o3qGy0t6z09AIJtH+5OeRV1be+N4cDYJKffGzDa88vQENZiRm0GRq6a+HPGQMd2k
TQIhAKMSvzIBnni7ot/OSie2TmJLY4SwTQAevXysE2RbFDYdAiEBCUEaRQnMnbp7
9mxDXDf6AU0cN/RPBjb9qSHDcWZHGzUCIG2Es59z8ugGrDY+pxLQnwfotadxd+Uy
v/Ow5T0q5gIJAiEAyS4RaI9YG8EWx/2w0T67ZUVAw8eOMB6BIUg0Xcu+3okCIBOs
/5OiPgoTdSy7bcF9IGpSE8ZgGKzgYQVZeN97YE00
-----END RSA PRIVATE KEY-----
`

func main() {
	p, _ := pem.Decode([]byte(keyPEM))
	k, err := x509.ParsePKCS1PrivateKey(p.Bytes)
	if err != nil {
		panic(err)
	}

	fmt.Printf("%+v\n", *k)
}
@rsc rsc added NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. release-blocker labels Dec 2, 2024
@rsc rsc added this to the Go1.24 milestone Dec 2, 2024
@gabyhelp
Copy link

gabyhelp commented Dec 2, 2024

Related Issues

(Emoji vote if this was helpful or unhelpful; more detailed feedback welcome in this discussion.)

@rsc
Copy link
Contributor Author

rsc commented Dec 2, 2024

I am seeing a similar failure in golang.org/x/crypto/openpgp/clearsign when running locally, but oddly I am not seeing it on the dashboard.

% go test
--- FAIL: TestMultiSign (2.72s)
    clearsign_test.go:155: cannot create key: crypto/rsa: invalid CRT coefficient
    clearsign_test.go:155: cannot create key: crypto/rsa: invalid CRT coefficient
    clearsign_test.go:155: cannot create key: crypto/rsa: invalid CRT coefficient
    clearsign_test.go:155: cannot create key: crypto/rsa: invalid CRT coefficient
    clearsign_test.go:155: cannot create key: crypto/rsa: invalid CRT coefficient
    clearsign_test.go:155: cannot create key: crypto/rsa: invalid CRT coefficient
    clearsign_test.go:155: cannot create key: crypto/rsa: invalid CRT coefficient
    clearsign_test.go:155: cannot create key: crypto/rsa: invalid CRT coefficient
    clearsign_test.go:155: cannot create key: crypto/rsa: invalid CRT coefficient
    clearsign_test.go:155: cannot create key: crypto/rsa: invalid CRT coefficient
    clearsign_test.go:155: cannot create key: crypto/rsa: invalid CRT coefficient
FAIL
exit status 1
FAIL	golang.org/x/crypto/openpgp/clearsign	2.919s
%

@FiloSottile
Copy link
Contributor

Ah, I see it, p < q, and

go/src/crypto/internal/fips140/rsa/rsa.go

Lines 251 to 255 in e5489a3

// Check that qInv * q ≡ 1 mod p.
one := q.Nat().Mul(priv.qInv, p)
if one.IsOne() != 1 {
return errors.New("crypto/rsa: invalid CRT coefficient")
}

assumes p > q which is generally true but I believe not required.

@rsc
Copy link
Contributor Author

rsc commented Dec 2, 2024

Is there something in the code that makes p > q generally true? The openpgp test is generating its own keys which then fail to validate. It is doing so with a terrible random number generator, and if I make the generator less terrible, the error goes away, but a bad RNG should not trigger invalid keys.

@gopherbot
Copy link
Contributor

Change https://go.dev/cl/632955 mentions this issue: crypto/rsa: fix keys with p < q

@rsc
Copy link
Contributor Author

rsc commented Dec 2, 2024

Looking at the openpgp/clearsign failure, it looks like something bad happened before the "keep the CRT values" change. Note the failure beginning at "move key generation":

% go test .  # fa38b41be9 crypto/internal/fips140/rsa: check that e and N are odd
ok  	golang.org/x/crypto/openpgp/clearsign	4.912s
% go test .  # 7d7192e54f crypto/rsa: move precomputation to crypto/internal/fips140/rsa
ok  	golang.org/x/crypto/openpgp/clearsign	4.686s
% go test .  # acd54c9985 crypto/rsa: move key generation to crypto/internal/fips140/rsa
--- FAIL: TestMultiSign (7.29s)
    clearsign_test.go:155: cannot create key: crypto/rsa: decryption error
    clearsign_test.go:155: cannot create key: crypto/rsa: decryption error
    clearsign_test.go:155: cannot create key: crypto/rsa: decryption error
    clearsign_test.go:155: cannot create key: crypto/rsa: decryption error
    clearsign_test.go:155: cannot create key: crypto/rsa: decryption error
    clearsign_test.go:155: cannot create key: crypto/rsa: decryption error
    clearsign_test.go:155: cannot create key: crypto/rsa: decryption error
    clearsign_test.go:155: cannot create key: crypto/rsa: decryption error
    clearsign_test.go:155: cannot create key: crypto/rsa: decryption error
FAIL
FAIL	golang.org/x/crypto/openpgp/clearsign	7.513s
FAIL
% go test .  # c5c4f3dd5f crypto/x509: keep RSA CRT values in ParsePKCS1PrivateKey
--- FAIL: TestMultiSign (3.56s)
    clearsign_test.go:155: cannot create key: crypto/rsa: invalid CRT coefficient
    clearsign_test.go:155: cannot create key: crypto/rsa: invalid CRT coefficient
    clearsign_test.go:155: cannot create key: crypto/rsa: invalid CRT coefficient
    clearsign_test.go:155: cannot create key: crypto/rsa: invalid CRT coefficient
    clearsign_test.go:155: cannot create key: crypto/rsa: invalid CRT coefficient
    clearsign_test.go:155: cannot create key: crypto/rsa: invalid CRT coefficient
    clearsign_test.go:155: cannot create key: crypto/rsa: invalid CRT coefficient
    clearsign_test.go:155: cannot create key: crypto/rsa: invalid CRT coefficient
    clearsign_test.go:155: cannot create key: crypto/rsa: invalid CRT coefficient
    clearsign_test.go:155: cannot create key: crypto/rsa: invalid CRT coefficient
    clearsign_test.go:155: cannot create key: crypto/rsa: invalid CRT coefficient
    clearsign_test.go:155: cannot create key: crypto/rsa: invalid CRT coefficient
    clearsign_test.go:155: cannot create key: crypto/rsa: invalid CRT coefficient
FAIL
FAIL	golang.org/x/crypto/openpgp/clearsign	3.906s
FAIL
% go test .  # dd7ab5ec5d crypto/internal/fips140/rsa: do trial divisions in key generation
--- FAIL: TestMultiSign (2.71s)
    clearsign_test.go:155: cannot create key: crypto/rsa: invalid CRT coefficient
    clearsign_test.go:155: cannot create key: crypto/rsa: invalid CRT coefficient
    clearsign_test.go:155: cannot create key: crypto/rsa: invalid CRT coefficient
    clearsign_test.go:155: cannot create key: crypto/rsa: invalid CRT coefficient
    clearsign_test.go:155: cannot create key: crypto/rsa: invalid CRT coefficient
    clearsign_test.go:155: cannot create key: crypto/rsa: invalid CRT coefficient
    clearsign_test.go:155: cannot create key: crypto/rsa: invalid CRT coefficient
    clearsign_test.go:155: cannot create key: crypto/rsa: invalid CRT coefficient
    clearsign_test.go:155: cannot create key: crypto/rsa: invalid CRT coefficient
    clearsign_test.go:155: cannot create key: crypto/rsa: invalid CRT coefficient
    clearsign_test.go:155: cannot create key: crypto/rsa: invalid CRT coefficient
    clearsign_test.go:155: cannot create key: crypto/rsa: invalid CRT coefficient
    clearsign_test.go:155: cannot create key: crypto/rsa: invalid CRT coefficient
FAIL
FAIL	golang.org/x/crypto/openpgp/clearsign	2.928s
FAIL
%

@FiloSottile
Copy link
Contributor

FiloSottile commented Dec 2, 2024 •
edited by gabyhelp
Loading

Yeah I think there's two different issues. The key in the initial issue has ⌈log₂(p)⌉ < ⌈log₂(q)⌉ which can't happen with our keygen (because for even sized moduli we produce primes of nlen/2 with the top two bits set, while for odd moduli we make p longer, while this key... has a 512 bit modulus with a 256 bit p and a 257 bit q, which I honestly wonder how you'd non-intentionally generate such a key). That tickled the bug CL 632955 is fixing.

The openpgp/clearsign failure is different I think, and I am looking into it now.

@rsc
Copy link
Contributor Author

rsc commented Dec 2, 2024

This diff in openpgp, improving the entropy returned by the random reader, "fixes" the errors, but we should understand why we are mishandling the current reader.

diff --git a/openpgp/clearsign/clearsign_test.go b/openpgp/clearsign/clearsign_test.go
index 051b8f1..6b524eb 100644
--- a/openpgp/clearsign/clearsign_test.go
+++ b/openpgp/clearsign/clearsign_test.go
@@ -6,6 +6,7 @@ package clearsign
 
 import (
 	"bytes"
+	"crypto/sha256"
 	"fmt"
 	"io"
 	"testing"
@@ -123,15 +124,18 @@ func TestSigning(t *testing.T) {
 	}
 }
 
-// We use this to make test keys, so that they aren't all the same.
-type quickRand byte
+// We use this to make test keys, so that they are deterministic but not all the same.
+type quickRand struct{ buf [32]byte }
 
 func (qr *quickRand) Read(p []byte) (int, error) {
-	for i := range p {
-		p[i] = byte(*qr)
+	n := 0
+	for len(p) > 0 {
+		qr.buf = sha256.Sum256(qr.buf[:])
+		m := copy(p, qr.buf[:])
+		n += m
+		p = p[m:]
 	}
-	*qr++
-	return len(p), nil
+	return n, nil
 }
 
 func TestMultiSign(t *testing.T) {
@@ -139,8 +143,7 @@ func TestMultiSign(t *testing.T) {
 		t.Skip("skipping long test in -short mode")
 	}
 
-	zero := quickRand(0)
-	config := packet.Config{Rand: &zero}
+	config := packet.Config{Rand: &quickRand{}}
 
 	for nKeys := 0; nKeys < 4; nKeys++ {
 	nextTest:

@FiloSottile
Copy link
Contributor

Hah, found it. The rng is so bad that it causes p = q, and then we compute q⁻¹ = q^(p-2) mod p which for p = q is 0.

I remember thinking "huh, why is this here" and deciding to remove it because a random source that bad kind of ought to explode. (Looking at the history, it actually looks like it's always been there, so it's not clear if it was because Adam stepped into the same problem.)

go/src/crypto/rsa/rsa.go

Lines 402 to 409 in c390a1c

// Make sure that primes is pairwise unequal.
for i, prime := range primes {
for j := 0; j < i; j++ {
if prime.Cmp(primes[j]) == 0 {
continue NextSetOfPrimes
}
}
}

We could fix the openpgp/clearsign test by retrying when p = q because this RNG is bad but not so bad that the primes keep coming out equal every time (which I think used to infinite loop), but I kinda prefer erroring out with a clear error rather than hide the brokenness of the random source.

@rolandshoemaker
Copy link
Member

+1 for the error case.

@rsc
Copy link
Contributor Author

rsc commented Dec 2, 2024

Returning an error in this case is great. We've had to improve these bad RNGs in the past as well.

@gopherbot
Copy link
Contributor

Change https://go.dev/cl/632896 mentions this issue: crypto/rsa: return error if keygen random source is broken

gopherbot pushed a commit that referenced this issue Dec 3, 2024
@FiloSottile @gopherbot
crypto/rsa: fix keys with p < q
106c804 
Updates #70643

Change-Id: I4aee8373dbddf774564902b3957c6eba11d15fc9
Reviewed-on: https://go-review.googlesource.com/c/go/+/632955
Reviewed-by: Roland Shoemaker <roland@golang.org>
Auto-Submit: Filippo Valsorda <filippo@golang.org>
Reviewed-by: Russ Cox <rsc@golang.org>
LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
@FiloSottile FiloSottile mentioned this issue Dec 20, 2024
Open
@mauri870 mauri870 mentioned this issue Dec 27, 2024
Closed
KoviRobi added a commit to KoviRobi/tooltracker that referenced this issue Jan 28, 2025
@KoviRobi
test: go: Generate new RSA key

Unverified

This commit is not signed, but one or more authors requires that any commit attributed to them is signed.
Learn about vigilant mode
e092530 
The old one complains about invalid modulus with new Go.
Related to golang/go#70643 maybe?
KoviRobi added a commit to KoviRobi/tooltracker that referenced this issue Jan 29, 2025
@KoviRobi
test: go: Generate new RSA key

Verified

This commit was signed with the committer’s verified signature.
KoviRobi Kovacsics Robert
SSH Key Fingerprint: Ex1IOaWv3A5fihOny0rngltSlVtxMq5aj3mqi6vAM+o
Verified
Learn about vigilant mode
9f324d3 
The old one complains about invalid modulus with new Go.
Related to golang/go#70643 maybe?
KoviRobi added a commit to KoviRobi/tooltracker that referenced this issue Jan 29, 2025
@KoviRobi
test: go: Generate new RSA key

Verified

This commit was signed with the committer’s verified signature.
KoviRobi Kovacsics Robert
SSH Key Fingerprint: Ex1IOaWv3A5fihOny0rngltSlVtxMq5aj3mqi6vAM+o
Verified
Learn about vigilant mode
0f1111f 
The old one complains about invalid modulus with new Go.
Related to golang/go#70643 maybe?
@romshark romshark mentioned this issue Feb 14, 2025
Merged
romshark added a commit to scionproto/scion that referenced this issue Feb 18, 2025
@romshark
chore: upgrade go to v1.24.0 (#4702)

Verified

This commit was created on GitHub.com and signed with GitHub’s verified signature.
GPG key ID: B5690EEEBB952194
Verified
Learn about vigilant mode
Loading
Loading status checks…
ecb4eaa 
Since the release of [Go v1.24.0](https://tip.golang.org/doc/go1.24), Go
1.22 is no longer supported.

~~We might go for 1.24 for the various performance improvements and the
significant changes to the crypto packages but that's up to collective
consensus.~~

We can't upgrade to `v1.23.x` because of significant performance
regression and instead we need to upgrade all the way to Go `v1.24.0`.

- `private/trust`: Change RSA key generation in `TestSignerGenGenerate`
to use 1024-bit keys instead of 512-bit because the latter is no longer
accepted, see golang/go#70643
- **test:** slightly lower router benchmark expectations as there seems
to be a general performance regression since the Go upgrade to v1.24
(not as much as v1.23.6 though).
- **ci:** remove linter `exportloopref` due to deprecation, see
[golangci-lint/CHANGELOG](https://github.com/golangci/golangci-lint/blob/312fdf7a8d0516ced651630c6196da9d6053c2d7/CHANGELOG.md?plain=1#L251)
- **ci:** disable Go linker's new automatic build id setting which
causes rpmbuild to fail due to all binaries having the same build id.
- **ci:** temporarily remove `nogo` due to incompatibility with Go 1.24
until further investigation.
- **ci:** upgrade golangci-lint to v1.64.5
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. release-blocker
Projects
None yet
Milestone
Go1.24
Development

No branches or pull requests
5 participants
@rsc @FiloSottile @rolandshoemaker @gopherbot @gabyhelp