asyncssh: Certificate auth broken on connecting to OpenSSH servers older than v8.8

This change is now available in AsyncSSH 2.13.2.

Great - thanks for the confirmation! This change will be included in the next release.

Ok - I’ve got an initial prototype of the change mentioned above:

diff --git a/asyncssh/connection.py b/asyncssh/connection.py
index 9d21827..198d39b 100644
--- a/asyncssh/connection.py
+++ b/asyncssh/connection.py
@@ -3074,6 +3074,7 @@ class SSHClientConnection(SSHConnection):

         self._client_keys: List[SSHKeyPair] = \
             list(options.client_keys) if options.client_keys else []
+        self._saved_rsa_key: Optional[_ClientHostKey] = None

         if options.preferred_auth != ():
             self._preferred_auth = [method.encode('ascii') for method in
@@ -3314,16 +3315,27 @@ class SSHClientConnection(SSHConnection):
         if not self._host_based_auth:
             return None, '', ''

+        key: Optional[_ClientHostKey]
+
         while True:
-            try:
-                key: Optional[_ClientHostKey] = self._client_host_keys.pop(0)
-            except IndexError:
-                key = None
-                break
+            if self._saved_rsa_key:
+                key = self._saved_rsa_key
+                key.algorithm = key.sig_algorithm + b'-cert-v01@openssh.com'
+                self._saved_rsa_key = None
+            else:
+                try:
+                    key = self._client_host_keys.pop(0)
+                except IndexError:
+                    key = None
+                    break

             assert key is not None

             if self._choose_signature_alg(key):
+                if key.algorithm == b'ssh-rsa-cert-v01@openssh.com' and \
+                        key.sig_algorithm != b'ssh-rsa':
+                    self._saved_rsa_key = key
+
                 break

         client_host = self._options.client_host
@@ -3382,10 +3394,19 @@ class SSHClientConnection(SSHConnection):

                 self._client_keys = list(load_keypairs(result))

-            keypair = self._client_keys.pop(0)
+            if self._saved_rsa_key:
+                key = self._saved_rsa_key
+                key.algorithm = key.sig_algorithm + b'-cert-v01@openssh.com'
+                self._saved_rsa_key = None
+            else:
+                key = self._client_keys.pop(0)
+
+            if self._choose_signature_alg(key):
+                if key.algorithm == b'ssh-rsa-cert-v01@openssh.com' and \
+                        key.sig_algorithm != b'ssh-rsa':
+                    self._saved_rsa_key = key

-            if self._choose_signature_alg(keypair):
-                return keypair
+                return key

     async def password_auth_requested(self) -> Optional[str]:
         """Return a password to authenticate with"""
diff --git a/asyncssh/public_key.py b/asyncssh/public_key.py
index a590c2b..1ce5f8d 100644
--- a/asyncssh/public_key.py
+++ b/asyncssh/public_key.py
@@ -2201,11 +2201,6 @@ class SSHKeyPair:

             cert = cast('SSHX509CertificateChain', self._cert)
             self.public_data = cert.adjust_public_data(sig_algorithm)
-        else:
-            if sig_algorithm.endswith(b'@openssh.com'):
-                sig_algorithm = sig_algorithm[:-12]
-
-            self.algorithm = sig_algorithm + b'-cert-v01@openssh.com'

     def sign(self, data: bytes) -> bytes:
         """Sign a block of data with this private key"""

This backs out change #517, in favor of the new approach where the calling code will attempt to authenticate with RSA keys first with just the signature algorithm change, and then if that is rejected it will try again with the certificate algorithm changed, so that it can work on OpenSSH 7.8+ where ssh-rsa-cert-v01@openssh.com is not allowed as a certificate algorithm.

The code here should cover both public key authentication and host-based authentication. It should only be active when RSA keys signed by a certificate are used, and only when attempting to use a SHA-2 signature algorithm with that key.

Thinking about this overnight, I’m guessing the situation is something like the following depending on OpenSSH server version:

OpenSSH 7.4 and earlier: No server-sig-algs advertised, so only ssh-rsa-cert-v01@openssh.com will be used, with a signature algorithm of ssh-rsa (SHA-1).

OpenSSH 7.5 to 7.7: Server-sig-algs advertised with RSA SHA-2 signature algs, but there’s no support for the cert versions of these algorithms as a valid public key type, so the change in #517 breaks things on those servers when attempting to use RSA SHA-2 signatures.

OpenSSH 7.8 ro 8.7: Server-sig-algs advertised and there’s support for the cert versions of these as public key types, so things work with either SHA-1 or SHA-2 RSA signatures.

OpenSSH 8.8 and later: Same as the last case, except that ssh-rsa and its corresponding cert version are disabled by default, so an RSA SHA-2 signature algorithm MUST be chosen. This should happen automatically, as long as you don’t limit signature algs in AsyncSSH to only SHA-1.

To fix the 7.5-7.7 issue, you should be able to set signature_algs=['ssh-rsa'] when making an outbound connection. This will force RSA SHA-1 to be used, but doing that will make sure the public key algorithm in the auth request is ssh-rsa-cert-v01@openssh.com, which should be accepted by the server. This isn’t as good as what happened before #517 on these versions, where ssh-rsa-cert-v01@openssh.com was used as the public key type while still allowing SHA-2 signatures, but at least authentication should work again without having to back out #517. Unfortunately, you need to do this selectively, as limiting the signature to just ssh-rsa won’t work by default against OpenSSH 8.8 and later.

To provide full control here, I’d probably need to look at implementing the equivalent of the PubkeyAcceptedAlgorithms config option from OpenSSH, and then use that to filter the allowed public key types independent of the existing filtering based on allowed signature algs. This would be a somewhat messy change, though, as it might mean attempting to authenticate with the same key multiple times with different public key types in the auth requests, and the current code is not really set up to do that. If setting signature_algs to just ssh-rsa works for you, I think that might be the best option for now.

What do you see for “type” if you run “ssh-keygen -L -f <cert_file>”?

It shows ssh-rsa-cert-v01@openssh.com:

Ok, good. That’s what I’d expect to see, and this doesn’t seem related to the issue.

Curiously, v9.1 also has a ssh-rsa entry in server-sig-algs (which probably explains why reversing keypair.sig_algorithms in that experiment regressed on connections to OpenSSH >= 8.8, as it matched ssh-rsa entry first).

Yeah - the reason to keep ssh-rsa at the end is to make sure it only gets picked as a last resort, when none of the better options are supported. It does seem a bit wrong for OpenSSH to still be listing ssh-rsa if the support for that is actually turned off now by default (like they’re doing for the host key algorithms), but any client which supports the RSA SHA-2 algorithms will always choose those over SHA-1, so in practice continuing to list ssh-rsa in the server-sig-algs probably doesn’t matter much.

It’s good to see that ssh-rsa is at least removed from the host key algorithms. With the recent change I made in AsyncSSH to look at those to decide which signature algorithm to use when acting as a server and signing the host key, it should help fix at least one of the two directions here. However, this won’t help with user auth.

Note that commenting out the original fix from #517, the client uses ssh-rsa-cert-v01@openssh.com for both 7.5 and 9.1 (matching the type on the certificate file).

I’m beginning to think that I got the fix in #517 wrong, but I’m not quite sure how to change it to still fix the original problem reported there while not triggering this new error about the algorithm not being recognized. I think I’m going to see if I can reproduce the original issue again, and take a closer look at how OpenSSH fills in the various algorithm names in a case of an RSA cert being used for user auth. In theory, there is a separate signature algorithm field, so it shouldn’t be necessary to change the public key alg name to explicitly use the new sig algorithm names. Going with ‘ssh-rsa-cert-v01@openssh.com’ should always be ok regardless of the signature algorithm used. I think maybe the new algorithms really only need to show up in the list of allowed algorithms (via server-sig-algs in the case of user auth), but there the names never include the “-cert@openssh.com”, so that shouldn’t impact the cert algorithm name put in the user auth message.

Thanks for the extra info. I think the recent change I made only really made a difference when choosing the signature algorithm to use for SSH host keys, not users, so that’s probably why it didn’t make a difference here.

When it comes to choosing signature algorithms for user auth, you correctly identified the code here, and from that you can see that it is looking for whether or not the server sent a list of supported signature algorithms in the “server-sig-algs” SSH extension. If that’s not sent, AsyncSSH should always fall back to using the older SHA-1 signature algorithm (‘ssh-rsa’). However, if that extension is sent (meaning the server supports the newer SHA-2 algorithms), it will tend to prefer one of those. You can also use the client connection option “signature_algs” to restrict which algorithms are allowed, passing in the subset of algorithms you want it to try. So, if you wanted to restrict the algorithm to the older ssh-rsa on a server that claimed to support the newer algorithms but really didn’t, you could pass in signature_algs=['ssh-rsa'].

As you discovered, passing this in won’t work on newer versions of OpenSSH, though, at least not without a server-side config change, as support for the older SHA-1 based signature algorithms is now disabled by default on OpenSSH.

The message you are getting on the server of “unsupported public key algorithm” makes me wonder if perhaps you are creating the certificate with an algorithm name of “rsa-sha2-256-cert-v01@openssh.com” instead of “ssh-rsa-cert-v01@openssh.com”. What do you see for “type” if you run “ssh-keygen -L -f <cert_file>”? I’m not sure older versions of OpenSSH will properly handle anything but the latter, and you shouldn’t need to change that in order to be able to use the newer RSA SHA-2 algorithms.

Could you capture a level 2 debug trace showing the SSH handshake with one of the older SSH servers? In particular, I’m curious if the server is advertising support for SHA-2 signatures or not via server-sig-algs. If it is advertising that, I’m curious why selecting a SHA-2 algorithm would be a problem. I think there might be two different problems here, though – on newer servers with ssh-rsa disabled by default, it will break if you force it to use that, while on older servers it might be getting confused by the public key algorithm name for an RSA cert being anything but “ssh-rsa-cert-v01@openssh.com”.