Fix SSH sign_and_send_pubkey: no mutual signature supported Error

Problem Statement

When attempting to connect to an SSH server using a terminal client (particularly common on macOS after system updates), you may encounter the error:

sign_and_send_pubkey: no mutual signature supported
user@host: Permission denied (publickey).

This occurs despite:

• Using a valid private key file (-i flag)
• Having correct file permissions (400 for the key file)
• Successful connections via GUI tools (like IntelliJ Remote Hosts)

The core issue is an algorithm compatibility mismatch between your SSH client and the server. The server may be rejecting older signature algorithms due to newer security standards.

Why This Happens

Modern SSH clients (OpenSSH 8.8+) disable the ssh-rsa (SHA-1) signature algorithm by default due to security vulnerabilities. If your server:

1. Uses an older OpenSSH version
2. Only supports ssh-rsa keys
3. Or lacks modern algorithms like rsa-sha2-256/512

...your client will refuse to establish a connection using potentially insecure methods.

---

Recommended Solutions

:material-check-bold: Preferred Long-term Solution: Generate a Modern Key

1. Create a new Ed25519 key (current security standard):

   ssh-keygen -t ed25519 -a 100

2. Add the key to your agent:

   ssh-add ~/.ssh/id_ed25519

3. Copy the public key to your server:

   ssh-copy-id -i ~/.ssh/id_ed25519.pub user@host

:material-alert: Temporary Compatibility Workaround

If key regeneration isn't immediately possible, enforce modern RSA SHA-2 algorithms:

1. Per-connection fix: Add key type parameters to your SSH command

   ssh -o PubkeyAcceptedKeyTypes=rsa-sha2-256,rsa-sha2-512 \
       -i {key.pem} user@host

2. Host-specific config (Add to ~/.ssh/config):

   Host your-server-hostname
       PubkeyAcceptedKeyTypes rsa-sha2-256,rsa-sha2-512
       HostKeyAlgorithms rsa-sha2-256,rsa-sha2-512

:material-alert: Last Resort: Enable Legacy Algorithms (Not Recommended)

Host legacy-server
    PubkeyAcceptedKeyTypes +ssh-rsa
    HostKeyAlgorithms +ssh-rsa

Security Warning

This re-enables the vulnerable SHA-1 algorithm. Use only for temporary access to non-critical systems and replace keys immediately.

---

Key Principles Explained

Algorithm Compatibility

The error indicates your client/server negotiation failed to find a mutually supported signature algorithm for key authentication. Modern clients disable ssh-rsa (SHA-1) due to vulnerability to collision attacks.

Best Practice Key Recommendations

Key Type	Command	Security Level	Notes
Ed25519	ssh-keygen -t ed25519	High	Preferred modern standard
RSA 4096-bit	ssh-keygen -t rsa -b 4096	High	Good if RSA required
RSA 3072-bit	ssh-keygen -t rsa -b 3072	Medium-High	Minimum acceptable RSA in 2023

---

Verify and Maintain

1. Check your server's OpenSSH version:

   ssh user@host "sshd -V"

2. Upgrade server if possible:

   # Ubuntu/Debian
   sudo apt update && sudo apt upgrade openssh-server
   
   # RHEL/CentOS
   sudo yum update openssh-server

Persistent Workarounds Are Risky

Configuration changes like PubkeyAcceptedKeyTypes +ssh-rsa are temporary fixes that weaken security. Always prioritize updating server SSH software or regenerating keys with modern standards.

Following these solutions resolves the mutual signature error while maintaining secure SSH connections. The long-term fix (Ed25519 key regeneration) provides optimal security against emerging threats.