Using ssh-rsa public key on Ubuntu 22.04 – no mutual signature algorithm

The RSA key for public key authentication was deprecated in 2020 due to security problems and although it is really not recommended to use this type of keys anymore here is how you can configure your server to accept it if you really need to. But this post is about the client side.

The OpenSSH client starting from version 8.4 also deprecated ssh-rsa keys so it refuses to use it with the following message (when using the -v switch for verbose output):

$ ssh -v -i /path/to/id_rsa user@server
[...]
debug1: Authentications that can continue: publickey
debug1: Next authentication method: publickey
debug1: Offering public key: /path/to/id_rsa RSA SHA256:1a2b3c4d[...] explicit
debug1: send_pubkey_test: no mutual signature algorithm
debug1: No more authentication methods to try.  
Permission denied (publickey).  

Although the no mutual signature algorithm seems to be a server issue at first, it might be as well a problem on the client side – the client refuses to use the key despite not stating it clearly.

You can extend the accepted key algorithms using the option -o "PubkeyAcceptedAlgorithms +ssh-rsa" and this should solve the problem:

$ ssh -v -o "PubkeyAcceptedAlgorithms +ssh-rsa" -i /path/to/id_rsa user@server
[...]
debug1: Authentications that can continue: publickey
debug1: Next authentication method: publickey
debug1: Offering public key: /path/to/id_rsa RSA SHA256:1a2b3c4d[...] explicit
debug1: Server accepts key: /path/to/id_rsa RSA SHA256:1a2b3c4d[...] explicit
Authenticated to server ([192.168.1.1]:22) using "publickey".