When attempting to authenticate using an ECDSA key (specifically NIST P-521 curve) between OpenSSH 5.9 client and OpenSSH 6.1 server, we encounter the error:

auth.info sshd[13874]: userauth_pubkey: unsupported public key algorithm: ecdsa-sha2-nistp521 [preauth]

To determine which public key algorithms your OpenSSH server supports:

ssh -Q key
ssh -Q key-sig

For a remote server check:

ssh -vvv user@server 2>&1 | grep "kex_parse_kexinit"

The issue stems from algorithm negotiation between different OpenSSH versions:

• OpenSSH 5.x: Initial ECDSA support (limited curves)
• OpenSSH 6.0+: Full ECDSA support (including NIST P-521)

Option 1: Regenerate key with supported curve (NIST P-256)

ssh-keygen -t ecdsa -b 256 -f ~/.ssh/id_ecdsa256

Option 2: Explicitly specify key type in client config

Host myserver
    HostName 192.168.1.1
    IdentityFile ~/.ssh/id_ecdsa
    PubkeyAcceptedKeyTypes=ecdsa-sha2-nistp256

To enable broader ECDSA support on the server:

# In /etc/ssh/sshd_config
PubkeyAcceptedKeyTypes ssh-rsa,ecdsa-sha2-nistp256,ecdsa-sha2-nistp384,ecdsa-sha2-nistp521

Then restart sshd:

sudo systemctl restart sshd

After making changes, verify the connection with:

ssh -v -i ~/.ssh/id_ecdsa user@myserver

Look for these successful authentication messages:

debug1: Offering ECDSA public key: ~/.ssh/id_ecdsa
debug1: Server accepts key: pkalg ecdsa-sha2-nistp521

---

When setting up ECDSA key authentication between OpenSSH clients and servers, you might encounter the error:

userauth_pubkey: unsupported public key algorithm: ecdsa-sha2-nistp521 [preauth]

The root cause typically stems from version mismatches between client and server implementations. In this case:

• Client: OpenSSH 5.9 (Debian-based)
• Server: OpenSSH 6.1

While ECDSA support was introduced in OpenSSH 5.7, some implementations may have limited algorithm support.

To verify what key types your server supports:

ssh -Q key
ssh -Q key-sig

For more detailed information about the server's capabilities:

ssh -vvv user@server

Add the following to your /etc/ssh/sshd_config:

PubkeyAcceptedKeyTypes ssh-rsa,ecdsa-sha2-nistp256,ecdsa-sha2-nistp384,ecdsa-sha2-nistp521

Then restart the SSH service:

sudo service ssh restart
# Or for systemd:
sudo systemctl restart sshd

If you can't modify server configuration, try forcing a different key type:

ssh -o PubkeyAcceptedKeyTypes=ssh-rsa user@server

Or generate a new RSA key pair:

ssh-keygen -t rsa -b 4096

Check supported KEX algorithms:

ssh -Q kex

For compatibility with older servers, you might need:

ssh -o KexAlgorithms=diffie-hellman-group-exchange-sha256

For comprehensive debugging:

ssh -vvv -i ~/.ssh/id_ecdsa user@server

Check server logs in real-time:

sudo tail -f /var/log/auth.log | grep sshd

When working with ECDSA keys:

• NIST P-521 (secp521r1) is considered strong but less widely supported
• NIST P-384 offers better compatibility while maintaining good security
• Always verify your OpenSSH version supports your chosen algorithms

Example of generating a more compatible ECDSA key:

ssh-keygen -t ecdsa -b 384 -f ~/.ssh/id_ecdsa_384 -C "ECDSA NIST P-384 key"