crypto/rsa: RSA keys newly rejected in Go 1.24

[rsc]

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)
}

[gabyhelp]

Related Issues

• crypto/rsa: mismatched keys no longer error #61077
• crypto/x509: ParsePKCS1PrivateKey is not complaint with PKCS#1 standard #14512 (closed)
• crypto/tls: LoadX509KeyPair fails to parse some keys, yet they are accepted by OpenSSL #21807 (closed)
• crypto/x509: ParsePKCS1PublicKey expects invalid key format #29141 (closed)
• crypto/x509: unable to parse certificate with rsassa-pss algorithm #48314
• x/crypto/openpgp: Treat PubKeyAlgoRSA and PubKeyAlgoRSASignOnly as equivalent for signatures #27888 (closed)
• crypto/x509 does not read RSA-PSS private key files #50532 (closed)

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

[rsc]

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]

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]

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]

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

[rsc]

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]

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]

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]

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]

+1 for the error case.

[rsc]

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

[gopherbot]

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