Unable to SSH onto some systems after client upgrade: no matching key found and/or permission denied

Ben Tasker

2022-09-02 10:17

After installing system updates, you may find that you're suddenly unable to SSH into systems that you could once reach without issue.

After updating to Ubuntu Jammy Jellyfish (22.04), I found I was no longer able to SSH onto my router

ssh 192.168.4.254
Unable to negotiate with 192.168.4.254 port 22: no matching host key type found. Their offer: ssh-rsa

I also found that I was no longer able to authenticate with a different box

ssh root@mikasa
root@mikasa: Permission denied (publickey).

Both of these issues occured because OpenSSH had been updated to a version >= 8.2:

ii  openssh-client                                1:8.9p1-3                                   amd64        secure shell (SSH) client, for secure access to remote machines

SHA-1 signatures were deprecated in OpenSSH 8.2.

This post discusses how to verify and resolve this.

Getting More Information

Verify that the permission denied error is caused by the upgrade rather than a problem with the key (permissions etc).

Pass -v when calling ssh

ssh -v root@mikasa

At the bottom of the output, you should see the following

debug1: send_pubkey_test: no mutual signature algorithm
debug1: No more authentication methods to try.
root@mikasa: Permission denied (publickey).

The line with no mutual signature algorithm tells us what we need to know, and confirms that this is related to the SHA-1 deprecation. In essence, it's telling us the same thing as no matching host key type found, just about a different stage of the authentication flow.

Testing Access

Although we're pretty sure we know the cause, we can verify it by re-enabling SHA-1 in the client

ssh -oHostkeyAlgorithms="+ssh-rsa" -oPubkeyAcceptedAlgorithms="+ssh-rsa" 192.168.4.254
ssh -oHostkeyAlgorithms="+ssh-rsa" -oPubkeyAcceptedAlgorithms="+ssh-rsa" mikasa

If access is granted then the issues are because the server is trying to use ssh-rsa signatures.

The Fix

The correct fix is to upgrade OpenSSH on the systems that you're trying to SSH to: ssh-rsa wasn't disabled just for the fun of it:

It is now possible[1] to perform chosen-prefix attacks against the
SHA-1 hash algorithm for less than USD$50K. For this reason, we will
be disabling the "ssh-rsa" public key signature algorithm that depends
on SHA-1 by default in a near-future release.

This algorithm is unfortunately still used widely despite the
existence of better alternatives, being the only remaining public key
signature algorithm specified by the original SSH RFCs.

The better alternatives include:

 * The RFC8332 RSA SHA-2 signature algorithms rsa-sha2-256/512. These
   algorithms have the advantage of using the same key type as
   "ssh-rsa" but use the safe SHA-2 hash algorithms. These have been
   supported since OpenSSH 7.2 and are already used by default if the
   client and server support them.

 * The ssh-ed25519 signature algorithm. It has been supported in
   OpenSSH since release 6.5.

 * The RFC5656 ECDSA algorithms: ecdsa-sha2-nistp256/384/521. These
   have been supported by OpenSSH since release 5.7.

To check whether a server is using the weak ssh-rsa public key
algorithm for host authentication, try to connect to it after
removing the ssh-rsa algorithm from ssh(1)'s allowed list:

    ssh -oHostKeyAlgorithms=-ssh-rsa user@host

If the host key verification fails and no other supported host key
types are available, the server software on that host should be
upgraded.

A future release of OpenSSH will enable UpdateHostKeys by default
to allow the client to automatically migrate to better algorithms.
Users may consider enabling this option manually.

[1] "SHA-1 is a Shambles: First Chosen-Prefix Collision on SHA-1 and
    Application to the PGP Web of Trust" Leurent, G and Peyrin, T
    (2020) https://eprint.iacr.org/2020/014.pdf

However, if you do not currently have the ability to upgrade those systems, you can work around this by enabling ssh-rsa for these hosts in your SSH config file

nano ~/.ssh/config

For each affected host, add a block like the following

Host 192.168.4.254
    HostkeyAlgorithms +ssh-rsa
    PubkeyAcceptedAlgorithms +ssh-rsa

But, you absolutely should view this only as a short-term fix and plan to get the target systems upgraded as soon as possible.

Conclusion

You'll likely run into this issue if you've still got systems running older SSH daemons. The issue won't appear when SSHing to newer installs because the client and server will be able to negotiate use of rsa-sha2-256 (or better).

It is possible to work around this in the client as a short-term solution, but you should plan to upgrade affected systems as soon as possible.