ssh: respect signer's algorithm preference in pickSignatureAlgorithm

Previously, pickSignatureAlgorithm constructed the list of candidate
algorithms by iterating over the static list returned by
algorithmsForKeyFormat. This caused the Signer's preference order
to be ignored in favor of the library's default internal order.

This change inverts the filtering logic to iterate over the signer's
supported algorithms first. This ensures that if a MultiAlgorithmSigner
explicitly prefers a specific algorithm (e.g., rsa-sha2-512 over
rsa-sha2-256), that preference is preserved and respected during the
handshake negotiation.

Fixes golang/go#78248

Change-Id: I48a0aac720be7f973963342b82047ce32fc96699
Reviewed-on: https://go-review.googlesource.com/c/crypto/+/746020
Reviewed-by: Lonny Wong <lonnywang.cn@gmail.com>
Reviewed-by: Dmitri Shuralyov <dmitshur@google.com>
Auto-Submit: Nicola Murino <nicola.murino@gmail.com>
LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
Reviewed-by: Filippo Valsorda <filippo@golang.org>
Reviewed-by: Carlos Amedee <carlos@golang.org>

2 files changed, 53 insertions, 3 deletions

diff --git a/ssh/client_auth.go b/ssh/client_auth.go
index 3127e49..4f2f75c 100644
--- a/ssh/client_auth.go
+++ b/ssh/client_auth.go
@@ -274,10 +274,14 @@ func pickSignatureAlgorithm(signer Signer, extensions map[string][]byte) (MultiA
 	}
 
 	// Filter algorithms based on those supported by MultiAlgorithmSigner.
+	// Iterate over the signer's algorithms first to preserve its preference order.
+	supportedKeyAlgos := algorithmsForKeyFormat(keyFormat)
 	var keyAlgos []string
-	for _, algo := range algorithmsForKeyFormat(keyFormat) {
-		if slices.Contains(as.Algorithms(), underlyingAlgo(algo)) {
-			keyAlgos = append(keyAlgos, algo)
+	for _, signerAlgo := range as.Algorithms() {
+		if idx := slices.IndexFunc(supportedKeyAlgos, func(algo string) bool {
+			return underlyingAlgo(algo) == signerAlgo
+		}); idx >= 0 {
+			keyAlgos = append(keyAlgos, supportedKeyAlgos[idx])
 		}
 	}
 
diff --git a/ssh/client_auth_test.go b/ssh/client_auth_test.go
index a183c21..199d207 100644
--- a/ssh/client_auth_test.go
+++ b/ssh/client_auth_test.go
@@ -1159,6 +1159,52 @@ func TestPickSignatureAlgorithm(t *testing.T) {
 	}
 }
 
+func TestPickSignatureAlgorithmRespectsSignerPreference(t *testing.T) {
+	algoSigner, ok := testSigners["rsa"].(AlgorithmSigner)
+	if !ok {
+		t.Fatalf("rsa test signer does not implement the AlgorithmSigner interface")
+	}
+
+	serverExtensions := map[string][]byte{
+		"server-sig-algs": []byte(KeyAlgoRSASHA256 + "," + KeyAlgoRSASHA512),
+	}
+
+	tests := []struct {
+		name         string
+		signerPrefs  []string
+		expectedAlgo string
+	}{
+		{
+			name:         "Signer prefers SHA512 then SHA256",
+			signerPrefs:  []string{KeyAlgoRSASHA512, KeyAlgoRSASHA256},
+			expectedAlgo: KeyAlgoRSASHA512,
+		},
+		{
+			name:         "Signer prefers SHA256 then SHA512",
+			signerPrefs:  []string{KeyAlgoRSASHA256, KeyAlgoRSASHA512},
+			expectedAlgo: KeyAlgoRSASHA256,
+		},
+	}
+
+	for _, tc := range tests {
+		t.Run(tc.name, func(t *testing.T) {
+			orderedSigner, err := NewSignerWithAlgorithms(algoSigner, tc.signerPrefs)
+			if err != nil {
+				t.Fatalf("failed to create ordered signer: %v", err)
+			}
+
+			_, selectedAlgo, err := pickSignatureAlgorithm(orderedSigner, serverExtensions)
+			if err != nil {
+				t.Fatalf("unexpected error: %v", err)
+			}
+
+			if selectedAlgo != tc.expectedAlgo {
+				t.Errorf("Algorithm mismatch; got %q want %q", selectedAlgo, tc.expectedAlgo)
+			}
+		})
+	}
+}
+
 // configurablePublicKeyCallback is a public key callback that allows to
 // configure the signature algorithm and format. This way we can emulate the
 // behavior of buggy clients.