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