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

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 '[]: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'

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.