RSA keys are not deprecated; SHA-1 signature scheme is!
Debugging "send_pubkey_test: no mutual signature algorithm" errors and demystifying the deprecation of "ssh-rsa" signature scheme in OpenSSH 8.8
ssh-rsa signature scheme has been deprecated since OpenSSH 8.8 which was released in
2021-08-20 (release notes).
The reason is as quoted:
In the SSH protocol, the "ssh-rsa" signature scheme uses the SHA-1 hash algorithm in conjunction with the RSA public key algorithm. It is now possible to perform chosen-prefix attacks against the SHA-1 algorithm for less than USD$50K.
This change should be transparent to most system as they already leverage relatively modern versions of OpenSSH; they automatically switch to stronger
rsa-sha2-512 signature schemes when presented with an RSA key.
However, there is one case where this creates problems: Either the client itself or the server has a very old implementation of SSH that does not support
rsa-sha2-512 signatures, for example: OpenSSH <=7.2 which was released in
2016-02-29 (release notes).
In such a scenario, when trying to establish an SSH connection, the authentication will fail with the following message (if verbose logs are enabled with
This means that between the server and the client, one of them is using the modern OpenSSH >= 8.8 which does not accept
ssh-rsa signature scheme, and the other is using some old SSH implementation, which still accepts
ssh-rsa signature scheme AND additionally does not try to switch to stronger signature algorithms.
|Modern SSH||Older SSH|
||Does not accept||Accept|
|RSA signature type(s)||
To summarize the differences, here's a table comparing modern SSH implementations versus older SSH implementations when handling RSA key types.
RSA keys are not deprecated!
I see many information sources writing about how RSA keys are deprecated with the release of OpenSSH 8.8 and that you should generate ECDSA or Ed25519 keys but I'd like to clarify here that that is absolutely false.
ssh-rsasignature algorithm is deprecated
You may still use RSA keys! Provided that you have a sufficiently modern SSH server and client pair (post 2016)
Confusion between key format and signature algorithm
The definition of
Public Key Algorithm has evolved over time which has led to this confusion which lies primarily in the nuances between the definition of a key format and a signature algorithm.
Key format in the context of SSH can refer to either:
- Mathematical procedure used to generate and validate a public/private key pair
- Format used to encode a public key
In laymen terms:
The key format refers to the type of the SSH key. It is synonymous to the value provided as the
-targument when generating an SSH key with
Values that might sound familiar to you include:
ed25519and of course
Signature algorithm in the context of SSH refers to:
- The mathematical procedure used to calculate, encode and verify a signature
In laymen terms:
Typically in SSH authentication a digital signature is produced which includes the public key itself within the contents.
This is then hashed with the signature algorithm before it is sent to the server.
In the past, before the standardization of SSH,
ssh-rsa implicitly referred to both the RSA key format and the RSA/SHA-1 signature algorithm used during the authentication process.
That means changing the signature algorithm would require assigning a new key type identifier (fictitious example: ssh-rsa-sha2-512) and end-users will all have to generate new keys to comply with new standards all the time.
To avoid this, IETF RFC8332 introduced the
server-sig-algs protocol extension that allowed clients to discover public key formats and signature algorithms supported by servers during authentication. This way, the key format may still remain as
ssh-rsa, as the signature algorithm is negotiated separately.
To see this protocol extension in action, you can run
ssh -vvv [email protected]. The logs would output something like this to show the signature algorithms supported:
How I found out the hard way
Once again, following the theme of my last few blog posts, I've went through this so that hopefully you won't have to. If you're just here for the solutions, skip to the last section.
Applications showing strange symptoms
It all started a few months back when I started noticing some issues cropping up with public key authentication in some applications running in my cluster that required establishing SSH connections.
A key example of this was
argocd-image-updater which essentially keeps my self-hosted applications' container images up-to-date.
It does this in 3 steps:
- Poll the respective container registries periodically for new tags for specific images
- Update the
images..newTagspec in the application's
kustomization.yamlwith the new tag
- Commit and push the changes to the application manifest git repository for persistence (Gitea in my case)
- New changes will then be deployed onto the cluster with Argo CD
This has worked fine for nearly a year, until one day I realized that my application images are not longer kept up-to-date.
Digging into the logs, it does seem like new tags are being discovered but it is failing to commit and push the changes with an error of
Permission denied (publickey) .
At this point, there are 2 possible causes:
- The SSH private key was not picked up by
- Gitea somehow deauthorized the public key
To eliminate the potential causes one-by one, I tried the following:
- Directly mounting in the container, the RSA SSH key in
~/.ssh/id_rsaand the SSH config in
~/.ssh/configbut it made no difference.
- Establishing an SSH connection on my Macbook with the same key and it worked flawlessly.
At that point, what really puzzled me was:
v0.10.3worked but any version after that broke the SSH authentication.
As much as I wanted to downgrade, alas I needed the bug fixes in the new version for it to work correctly with
In a last ditch attempt to convince myself that it was not just some error caused by new application code in
v0.11.0, I did a
kubectl exec into the container and tried establishing an SSH connection directly with the key using the verbose
ssh -vvv and that's when I saw the fateful error message:
debug1: send_pubkey_test: no mutual signature algorithm
Checking client configuration
A quick search revealed that it is most likely due to the deprecation of
ssh-rsa signature algorithm.
Checking the client configurations with
ssh -G <hostname>:
We can see that the client (
argocd-image-updater ) does not accept the
ssh-rsa public key algorithm.
Verifying server configuration
Unfortunately, as my Gitea instance is currently configured to use the provided internal Go implementation of SSH, there are no
sshd_config files that I can refer to, to check the server's accepted public key algorithms.
But we can get a clue by adding the
ssh-rsa public key algorithm back into the list of
PubKeyAcceptedAlgorithms and trying to connect once again.
From this, we can surmise that the issue is most likely caused by the fact that
ssh-rsa signature algorithm was deprecated.
Examining image for OpenSSH client version
To gain further confidence of the hypothesised root cause, I dug even deeper into the container image to find the version of OpenSSH client used.
Tracing the Dockerfile for
argocd-image-updater we can see that
openssh-client was not locked to a specific version which means it will pick whichever is the latest version at the time of build.
Cross-checking Application/OpenSSH release dates
Looking at the release dates of
We can see that:
v0.11.0was released on 2021-10-28, after OpenSSH 8.8 was released
v0.10.3was released on 2021-09-13, before OpenSSH 8.8 was released
This illustrates that the OpenSSH client version bump was likely the cause.
Open issue with Gitea on SSH implementation
Last but not least, I checked Gitea's GitHub issues to ascertain whether the internal Go SSH implementation was causing issues for others and indeed I found an open issue since Nov 24, 2021.
This is the final nail in the coffin and fully confirms that the root cause is the newly updated
openssh-client operating with Gitea's internal implementation of an SSH server which might not have kept abreast with OpenSSH's development trajectory and timelines.
Summary of the issue
To be honest, this issue was not an easy one to describe and I've struggled quite a fair bit to put it in simple terms.
To help visualize the issue, here's a simplified diagram that shows each interaction between the modern client and old server in a conversational manner.
To enable SSH connections against best practices, you can add the following line to your
/etc/ssh_config file to allow re-enable
ssh-rsa signature algorithm globally.
This is only recommended as a temporal solution as it leaves your system increasingly vulnerable over time to attacks via the SHA-1 signature algorithm.
The long-term solution is to upgrade your OpenSSH version or, if you're not using OpenSSH, your SSH implementation to be in line with latest standards.
If that's not an option, I'm afraid the only way out is to either wait for/contribute a fix, or to switch to another SSH key format such as ECDSA or Ed25519.
What I did in the end
To avoid having to deal with further issues relating to RSA keys, I've decided to migrate all my SSH keys to Ed25519.
Potential issues with RSA keys
- Key length growth: Will gradually require more bits to stay secure as compute capacity advances (Current minimum: 2048 bits)
- Not future proof: Potentially vulnerable to breaking by quantum computers
Advantages of Ed25519 (EdDSA) keys:
- Performance: Ed25519 is the fastest performing algorithm across all metrics
- Security: EdDSA provides the highest security level as compared to other algorithms with the same key length (Source)
- Dummy proof: No need to specify number of bits when generating keys
- Shorter public keys: No wrangling with unwieldily long public key strings like in RSA 4096-bit
Benchmarking the algorithms on a Rock Pi 4A with
For context, 253 bits EdDSA is equivalent in strength to RSA ~3000 bits. As you can see, Ed25519 blows all other cryptographic algorithms out the water in terms of performance.
It's been fun diving deep into this issue and I probably spent more time than I should have on this 😆. Nonetheless, I hope this helps with your SSH issues whether or not it's related to Gitea. Cheers!