Cryptography Featured

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

Will Ho

Jul 16, 2022 • 10 min read

Didn't know that was the OpenSSH logo? Don't worry, me neither.

The 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[1] 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-256 or rsa-sha2-512 signature schemes when presented with an RSA key.

The problem

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-256 or 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 ssh -vvv):

debug1: Authentications that can continue: publickey
debug1: Next authentication method: publickey
debug1: Offering public key: id_rsa RSA SHA256:gFUuZDPoALpi8+UZ3DYV/NMxsG3rlQbSr8puSYwdkXQ explicit
debug1: send_pubkey_test: no mutual signature algorithm

SSH verbose log message when failing signature algorithm checks

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
`ssh-rsa` (SHA-1) signature	Does not accept	Accept
RSA signature type(s)	`rsa-sha2-256`, `rsa-sha2-512`	`ssh-rsa`

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.

To reiterate:

Only the ssh-rsa signature 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

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 -t argument when generating an SSH key with ssh-keygen.
Values that might sound familiar to you include: dsa, ecdsa, ed25519 and of course rsa.

Signature Algorithm

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.

History

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.

RFC 8332 - Use of RSA Keys with SHA-256 and SHA-512 in the Secure Shell (SSH) Protocol

Use of RSA Keys with SHA-256 and SHA-512 in the Secure Shell (SSH) Protocol (RFC 8332)

Use of RSA Keys with SHA-256 and SHA-512 in the Secure Shell (SSH) Protocol

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:

debug1: kex_input_ext_info: server-sig-algs=<[email protected],[email protected],[email protected],[email protected],[email protected],[email protected],[email protected],[email protected],[email protected],[email protected],[email protected],ssh-ed25519,ecdsa-sha2-nistp521,ecdsa-sha2-nistp384,ecdsa-sha2-nistp256,rsa-sha2-512,rsa-sha2-256,ssh-rsa>

server-sig-algs SSH protocol extension as seen in verbose logs

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.[].newTag spec in the application's kustomization.yaml with 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.

Diving deeper

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 argocd-image-updater
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_rsa and the SSH config in ~/.ssh/config but 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:

Downgrading argocd-image-updater to v0.10.3 worked 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 kustomization.yaml.

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>:

$ ssh -G [email protected] | grep pubkeyacceptedalgorithms
pubkeyacceptedalgorithms [email protected],[email protected],[email protected],[email protected],[email protected],[email protected],[email protected],[email protected],ssh-ed25519,ecdsa-sha2-nistp256,ecdsa-sha2-nistp384,ecdsa-sha2-nistp521,[email protected],[email protected],rsa-sha2-512,rsa-sha2-256

Checking SSH client configuration post host mapping

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.

$ ssh -o PubKeyAcceptedAlgorithms=+ssh-rsa [email protected]
PTY allocation request failed on channel 0
Hi there! You've successfully authenticated with the key named [email protected], but Gitea does not provide shell access.
If this is unexpected, please log in with password and setup Gitea under another user.
Connection to gitea.myprivate.domain closed.

Connected successfully to SSH server with PubKeyAcceptedAlgorithms=+ssh-rsa

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.

...
FROM alpine:latest

RUN apk update && \
    apk upgrade && \
    apk add git openssh-client python3 py3-pip && \
    pip3 install --upgrade pip && \
    pip3 install awscli && \
    rm -rf /var/cache/apk/*
...

Part of argocd-image-updater Dockerfile

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 argocd-image-updater :

We can see that:

v0.11.0 was released on 2021-10-28, after OpenSSH 8.8 was released
v0.10.3 was 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.

A modern SSH client with RSA key failing authentication with an old SSH server

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.

Stopgap measure

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.

PubkeyAcceptedKeyTypes +ssh-rsa

Line in ssh_config file to re-enable ssh-rsa

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.

Long-term solution

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 openssl:

$ openssl speed rsa1024 rsa2048 rsa4096 ecdsap256 ed25519
                            sign      verify     sign/s verify/s
rsa 1024 bits               0.000746s 0.000037s  1339.6  26977.3
rsa 2048 bits               0.004988s 0.000134s   200.5   7489.6
rsa 4096 bits               0.034826s 0.000511s    28.7   1956.0
256 bits ecdsa (nistp256)   0.0001s   0.0003s   10816.4   3398.5
253 bits EdDSA (Ed25519)    0.0001s   0.0002s    9192.5   4096.0

OpenSSL cryptographic algorithm benchmarking

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.

Closing thoughts

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!