ssh handshake is rejected with 'no mutual signature algorithm' error

It sometimes happens that although you have already set up your private/public key, you still cannot get connected to the remote server with ssh.

In practice, there is an uncountable number of reasons: firewall, server configuration that restricts external access, ... The recommended method to find the reason is to use the -v (or -vvv) flag in the ssh command to find the reason from the log.

In my case, when I tried to access my server, my client was rejected with the following error.

debug1: Offering public key: /home/myuser/.ssh/id_rsa RSA SHA256:<hidden>
debug1: send_pubkey_test: no mutual signature algorithm
Permission denied (publickey)

It looks like the remote server does not accept the signature algorithm used by my local private key generator. When I look further in from the ssh log.

debug1: Host '[54.209.41.81]:64538' is known and matches the ED25519 host key.

My local key was generated using RSA, this gives me a hint that the server prefers the ED25519 algorithm. With this hint, I could ssh to the server by the following 2 types.

Method 1: Generate a new key using the preferred algorithm.

ssh-keygen -t ed25519

Method 2: offer the RSA algorithm to the server.

In ssh command:

ssh -o 'PubkeyAcceptedKeyTypes +ssh-rsa' example.server.com

Additional information

To check algorithm and key size, use command ssh-keygen -l -f <path-to-private-key>.

RSA vs ED25519 or ECDSA.

RSA is based on the (prime) integer factorization problem, while ECDSA relies on the Elliptic Curve Discrete Logarithm Problem, and ED25519 uses the Edwards-curve Digital Signature Algorithm (EdDSA).

While all these algorithms are still secure and reliable for now, ED25519 and ECDSA belong to the elliptic-curve cryptography class, they can provide the same level of security with a shorter private key. Thus, they (EdDSA/ECDSA) are considered better in several situations.

Another way to remember their modernness is to look at the time of the invention, RSA (1977) - ECDSA (1992) - EdDSA (2011).

From Recommendation for Key Management by NIST (National Institute of Standards and Technology): link, pdf (page 67-68)

For example, the DSA algorithm with a 224-bit key provides the same security level as the RSA algorithm with a 2048-bit key.