ssh: fix RSA certificate and public key authentication with older clients

After adding support for rsa-sha2-256/512 on the server side some edge
cases started to arise with old clients:

1) public key authentication with gpg-agent < 2.2.6 fails because we
   receive ssh-rsa as signature format and rsa-sha2-256 or rsa-sha2-512
   as algorithm.
   This is a bug in gpg-agent fixed in this commit:

   https://github.com/gpg/gnupg/commit/80b775bdbb852aa4a80292c9357e5b1876110c00

2) certificate authentication fails with OpenSSH 7.2-7.7 because we
   receive ssh-rsa-cert-v01@openssh.com as algorithm and rsa-sha2-256
   or rsa-sha2-512 as signature format.

This patch is based on CL 412854 and has been tested with every version
of OpenSSH from 7.1 to 7.9 and OpenSSH 9.3.

Fixes golang/go#53391

Change-Id: Id71f596f73d84efb5c76d6d5388432cccad3e3b1
Reviewed-on: https://go-review.googlesource.com/c/crypto/+/506835
Auto-Submit: Filippo Valsorda <filippo@golang.org>
Reviewed-by: Filippo Valsorda <filippo@golang.org>
Run-TryBot: Filippo Valsorda <filippo@golang.org>
Reviewed-by: Dmitri Shuralyov <dmitshur@google.com>
TryBot-Result: Gopher Robot <gobot@golang.org>
Reviewed-by: Roland Shoemaker <roland@golang.org>

3 files changed, 148 insertions, 1 deletions

diff --git a/ssh/client_auth_test.go b/ssh/client_auth_test.go
index 35b62e3..70558a9 100644
--- a/ssh/client_auth_test.go
+++ b/ssh/client_auth_test.go
@@ -955,3 +955,124 @@ func TestAuthMethodGSSAPIWithMIC(t *testing.T) {
 		}
 	}
 }
+
+func TestCompatibleAlgoAndSignatures(t *testing.T) {
+	type testcase struct {
+		algo       string
+		sigFormat  string
+		compatible bool
+	}
+	testcases := []*testcase{
+		{
+			KeyAlgoRSA,
+			KeyAlgoRSA,
+			true,
+		},
+		{
+			KeyAlgoRSA,
+			KeyAlgoRSASHA256,
+			true,
+		},
+		{
+			KeyAlgoRSA,
+			KeyAlgoRSASHA512,
+			true,
+		},
+		{
+			KeyAlgoRSASHA256,
+			KeyAlgoRSA,
+			true,
+		},
+		{
+			KeyAlgoRSASHA512,
+			KeyAlgoRSA,
+			true,
+		},
+		{
+			KeyAlgoRSASHA512,
+			KeyAlgoRSASHA256,
+			true,
+		},
+		{
+			KeyAlgoRSASHA256,
+			KeyAlgoRSASHA512,
+			true,
+		},
+		{
+			KeyAlgoRSASHA512,
+			KeyAlgoRSASHA512,
+			true,
+		},
+		{
+			CertAlgoRSAv01,
+			KeyAlgoRSA,
+			true,
+		},
+		{
+			CertAlgoRSAv01,
+			KeyAlgoRSASHA256,
+			true,
+		},
+		{
+			CertAlgoRSAv01,
+			KeyAlgoRSASHA512,
+			true,
+		},
+		{
+			CertAlgoRSASHA256v01,
+			KeyAlgoRSASHA512,
+			true,
+		},
+		{
+			CertAlgoRSASHA512v01,
+			KeyAlgoRSASHA512,
+			true,
+		},
+		{
+			CertAlgoRSASHA512v01,
+			KeyAlgoRSASHA256,
+			true,
+		},
+		{
+			CertAlgoRSASHA256v01,
+			CertAlgoRSAv01,
+			true,
+		},
+		{
+			CertAlgoRSAv01,
+			CertAlgoRSASHA512v01,
+			true,
+		},
+		{
+			KeyAlgoECDSA256,
+			KeyAlgoRSA,
+			false,
+		},
+		{
+			KeyAlgoECDSA256,
+			KeyAlgoECDSA521,
+			false,
+		},
+		{
+			KeyAlgoECDSA256,
+			KeyAlgoECDSA256,
+			true,
+		},
+		{
+			KeyAlgoECDSA256,
+			KeyAlgoED25519,
+			false,
+		},
+		{
+			KeyAlgoED25519,
+			KeyAlgoED25519,
+			true,
+		},
+	}
+
+	for _, c := range testcases {
+		if isAlgoCompatible(c.algo, c.sigFormat) != c.compatible {
+			t.Errorf("algorithm %q, signature format %q, expected compatible to be %t", c.algo, c.sigFormat, c.compatible)
+		}
+	}
+}
diff --git a/ssh/common.go b/ssh/common.go
index 03ff0b3..5ce452b 100644
--- a/ssh/common.go
+++ b/ssh/common.go
@@ -119,6 +119,13 @@ func algorithmsForKeyFormat(keyFormat string) []string {
 	}
 }
 
+// isRSA returns whether algo is a supported RSA algorithm, including certificate
+// algorithms.
+func isRSA(algo string) bool {
+	algos := algorithmsForKeyFormat(KeyAlgoRSA)
+	return contains(algos, underlyingAlgo(algo))
+}
+
 // supportedPubKeyAuthAlgos specifies the supported client public key
 // authentication algorithms. Note that this doesn't include certificate types
 // since those use the underlying algorithm. This list is sent to the client if
diff --git a/ssh/server.go b/ssh/server.go
index 9e38702..b21322a 100644
--- a/ssh/server.go
+++ b/ssh/server.go
@@ -370,6 +370,25 @@ func gssExchangeToken(gssapiConfig *GSSAPIWithMICConfig, firstToken []byte, s *c
 	return authErr, perms, nil
 }
 
+// isAlgoCompatible checks if the signature format is compatible with the
+// selected algorithm taking into account edge cases that occur with old
+// clients.
+func isAlgoCompatible(algo, sigFormat string) bool {
+	// Compatibility for old clients.
+	//
+	// For certificate authentication with OpenSSH 7.2-7.7 signature format can
+	// be rsa-sha2-256 or rsa-sha2-512 for the algorithm
+	// ssh-rsa-cert-v01@openssh.com.
+	//
+	// With gpg-agent < 2.2.6 the algorithm can be rsa-sha2-256 or rsa-sha2-512
+	// for signature format ssh-rsa.
+	if isRSA(algo) && isRSA(sigFormat) {
+		return true
+	}
+	// Standard case: the underlying algorithm must match the signature format.
+	return underlyingAlgo(algo) == sigFormat
+}
+
 // ServerAuthError represents server authentication errors and is
 // sometimes returned by NewServerConn. It appends any authentication
 // errors that may occur, and is returned if all of the authentication
@@ -567,7 +586,7 @@ userAuthLoop:
 					authErr = fmt.Errorf("ssh: algorithm %q not accepted", sig.Format)
 					break
 				}
-				if underlyingAlgo(algo) != sig.Format {
+				if !isAlgoCompatible(algo, sig.Format) {
 					authErr = fmt.Errorf("ssh: signature %q not compatible with selected algorithm %q", sig.Format, algo)
 					break
 				}