ssh: return clearer error when signature algorithm is used as key format

ParsePublicKey now returns a more specific error when a signature
algorithm like rsa-sha2-256 is mistakenly provided as a key format

Change-Id: Ic08286a5b2b326e99dd3e61594919203f0c36791
Reviewed-on: https://go-review.googlesource.com/c/crypto/+/695075
Reviewed-by: Filippo Valsorda <filippo@golang.org>
LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
Reviewed-by: Mark Freeman <markfreeman@google.com>
Reviewed-by: Michael Knyszek <mknyszek@google.com>
diff --git a/ssh/common.go b/ssh/common.go
index 8bfad16..36c82a7 100644
--- a/ssh/common.go
+++ b/ssh/common.go
@@ -312,6 +312,35 @@
 	}
 }
 
+// keyFormatForAlgorithm returns the key format corresponding to the given
+// signature algorithm. It returns an empty string if the signature algorithm is
+// invalid or unsupported.
+func keyFormatForAlgorithm(sigAlgo string) string {
+	switch sigAlgo {
+	case KeyAlgoRSA, KeyAlgoRSASHA256, KeyAlgoRSASHA512:
+		return KeyAlgoRSA
+	case CertAlgoRSAv01, CertAlgoRSASHA256v01, CertAlgoRSASHA512v01:
+		return CertAlgoRSAv01
+	case KeyAlgoED25519,
+		KeyAlgoSKED25519,
+		KeyAlgoSKECDSA256,
+		KeyAlgoECDSA256,
+		KeyAlgoECDSA384,
+		KeyAlgoECDSA521,
+		InsecureKeyAlgoDSA,
+		InsecureCertAlgoDSAv01,
+		CertAlgoECDSA256v01,
+		CertAlgoECDSA384v01,
+		CertAlgoECDSA521v01,
+		CertAlgoSKECDSA256v01,
+		CertAlgoED25519v01,
+		CertAlgoSKED25519v01:
+		return sigAlgo
+	default:
+		return ""
+	}
+}
+
 // isRSA returns whether algo is a supported RSA algorithm, including certificate
 // algorithms.
 func isRSA(algo string) bool {
diff --git a/ssh/common_test.go b/ssh/common_test.go
index 67cf1f4..80aa2df 100644
--- a/ssh/common_test.go
+++ b/ssh/common_test.go
@@ -5,7 +5,9 @@
 package ssh
 
 import (
+	"maps"
 	"reflect"
+	"slices"
 	"testing"
 )
 
@@ -174,3 +176,21 @@
 		})
 	}
 }
+
+func TestKeyFormatAlgorithms(t *testing.T) {
+	supportedAlgos := SupportedAlgorithms()
+	insecureAlgos := InsecureAlgorithms()
+	algoritms := append(supportedAlgos.PublicKeyAuths, insecureAlgos.PublicKeyAuths...)
+	algoritms = append(algoritms, slices.Collect(maps.Keys(certKeyAlgoNames))...)
+
+	for _, algo := range algoritms {
+		keyFormat := keyFormatForAlgorithm(algo)
+		if keyFormat == "" {
+			t.Errorf("got empty key format for algorithm %q", algo)
+		}
+		if !slices.Contains(algorithmsForKeyFormat(keyFormat), algo) {
+			t.Errorf("algorithms for key format %q, does not contain %q", keyFormat, algo)
+		}
+
+	}
+}
diff --git a/ssh/keys.go b/ssh/keys.go
index a28c0de..8327260 100644
--- a/ssh/keys.go
+++ b/ssh/keys.go
@@ -89,6 +89,11 @@
 		}
 		return cert, nil, nil
 	}
+	if keyFormat := keyFormatForAlgorithm(algo); keyFormat != "" {
+		return nil, nil, fmt.Errorf("ssh: signature algorithm %q isn't a key format; key is malformed and should be re-encoded with type %q",
+			algo, keyFormat)
+	}
+
 	return nil, nil, fmt.Errorf("ssh: unknown key algorithm: %v", algo)
 }
 
@@ -191,9 +196,10 @@
 	return "", nil, nil, "", nil, io.EOF
 }
 
-// ParseAuthorizedKey parses a public key from an authorized_keys
-// file used in OpenSSH according to the sshd(8) manual page.
+// ParseAuthorizedKey parses a public key from an authorized_keys file used in
+// OpenSSH according to the sshd(8) manual page. Invalid lines are ignored.
 func ParseAuthorizedKey(in []byte) (out PublicKey, comment string, options []string, rest []byte, err error) {
+	var lastErr error
 	for len(in) > 0 {
 		end := bytes.IndexByte(in, '\n')
 		if end != -1 {
@@ -222,6 +228,8 @@
 
 		if out, comment, err = parseAuthorizedKey(in[i:]); err == nil {
 			return out, comment, options, rest, nil
+		} else {
+			lastErr = err
 		}
 
 		// No key type recognised. Maybe there's an options field at
@@ -264,12 +272,18 @@
 		if out, comment, err = parseAuthorizedKey(in[i:]); err == nil {
 			options = candidateOptions
 			return out, comment, options, rest, nil
+		} else {
+			lastErr = err
 		}
 
 		in = rest
 		continue
 	}
 
+	if lastErr != nil {
+		return nil, "", nil, nil, fmt.Errorf("ssh: no key found; last parsing error for ignored line: %w", lastErr)
+	}
+
 	return nil, "", nil, nil, errors.New("ssh: no key found")
 }
 
diff --git a/ssh/keys_test.go b/ssh/keys_test.go
index f3eb223..661e3cb 100644
--- a/ssh/keys_test.go
+++ b/ssh/keys_test.go
@@ -59,6 +59,17 @@
 	}
 }
 
+func TestParsePublicKeyWithSigningAlgoAsKeyFormat(t *testing.T) {
+	key := []byte(`rsa-sha2-256 AAAADHJzYS1zaGEyLTI1NgAAAAMBAAEAAAEBAJ7qMyjLXEJCCJmRknuCLo0uPi5GrPY5pQYr84lhlN8Gor5KVL2LKYCW4e70r5xzj7SrHHSCft1FMlYg1KDO9xrprJh733kQqAPWETmSuH0EfRtGtcH6EarKyVxk6As076/yNiiMKVBtG0RPa1L7FviTfcYK4vnCCVrbv3RmA5CCzuG5BSMbRLxzVb4Ri3p8jhxYT8N4QGe/2yqvJLys5vQ9szpZR3tcFp3DJIVZhBRfR6LnoY23XZniAAMQaUVBX86dXQ++dNwAwZSXSt9Og+AniOCiBYqhNVa5n3DID/H7YtEtG+CbZr3r2KD3fv8AfSLRar4XOp8rsRdD31h/kr8=`)
+	_, _, _, _, err := ParseAuthorizedKey(key)
+	if err == nil {
+		t.Fatal("parsing a public key using a signature algorithm as the key format succeeded unexpectedly")
+	}
+	if !strings.Contains(err.Error(), `signature algorithm "rsa-sha2-256" isn't a key format`) {
+		t.Errorf(`got %v, expected 'signature algorithm "rsa-sha2-256" isn't a key format'`, err)
+	}
+}
+
 func TestUnsupportedCurves(t *testing.T) {
 	raw, err := ecdsa.GenerateKey(elliptic.P224(), rand.Reader)
 	if err != nil {