Unable to SSH from Debian 12 to Debian 8 Using ssh-rsa Key: “send_pubkey_test: no mutual signature algorithm”

[isscbta]

Question:

I’m trying to SSH from a Debian 12 machine to a Debian 8 server using my ssh-rsa private key located on the Debian 12 computer. However, I can’t log in using the SSH key; instead, SSH prompts me for a password.

When I run the SSH command with the -vvv option for verbose output, I notice the following lines at the end:

Code: Select all

debug2: KEX algorithms: [email protected],ecdh-sha2-nistp256,ecdh-sha2-nistp384,ecdh-sha2-nistp521,diffie-hellman-group-exchange-sha256,diffie-hellman-group14-sha1
debug2: host key algorithms: ssh-rsa,ssh-dss,ecdsa-sha2-nistp256,ssh-ed25519
debug2: ciphers ctos: aes128-ctr,aes192-ctr,aes256-ctr,[email protected],[email protected],[email protected]
debug2: ciphers stoc: aes128-ctr,aes192-ctr,aes256-ctr,[email protected],[email protected],[email protected]
debug2: MACs ctos: [email protected],[email protected],[email protected],[email protected],[email protected],[email protected],[email protected],hmac-sha2-256,hmac-sha2-512,hmac-sha1
debug2: MACs stoc: [email protected],[email protected],[email protected],[email protected],[email protected],[email protected],[email protected],hmac-sha2-256,hmac-sha2-512,hmac-sha1
debug2: compression ctos: none,[email protected]
debug2: compression stoc: none,[email protected]
debug2: languages ctos: 
debug2: languages stoc: 
debug2: first_kex_follows 0 
debug2: reserved 0 
debug1: kex: algorithm: [email protected]
debug1: kex: host key algorithm: ssh-ed25519
debug1: kex: server->client cipher: [email protected] MAC: <implicit> compression: none
debug1: kex: client->server cipher: [email protected] MAC: <implicit> compression: none
debug1: expecting SSH2_MSG_KEX_ECDH_REPLY
debug1: SSH2_MSG_KEX_ECDH_REPLY received
debug1: Server host key: ssh-ed25519 SHA256:AvwMPWNshVKJeF+eSijp4+5xrO25tjylSPa12ERusvc
debug1: load_hostkeys: fopen /root/.ssh/known_hosts2: No such file or directory
debug1: load_hostkeys: fopen /etc/ssh/ssh_known_hosts: No such file or directory
debug1: load_hostkeys: fopen /etc/ssh/ssh_known_hosts2: No such file or directory
debug1: Host 'matrix.na.rs' is known and matches the ED25519 host key.
debug1: Found key in /root/.ssh/known_hosts:9
debug2: ssh_set_newkeys: mode 1
debug1: rekey out after 134217728 blocks
debug1: SSH2_MSG_NEWKEYS sent
debug1: expecting SSH2_MSG_NEWKEYS
debug1: SSH2_MSG_NEWKEYS received
debug2: ssh_set_newkeys: mode 0
debug1: rekey in after 134217728 blocks
debug1: Will attempt key: /root/.ssh/id_rsa RSA SHA256:TdPH7qoRFHoJvHzyHqSCWEwBe5gv6TuqnOHUcD6B4Nc
debug1: Will attempt key: /root/.ssh/id_ecdsa 
debug1: Will attempt key: /root/.ssh/id_ecdsa_sk 
debug1: Will attempt key: /root/.ssh/id_ed25519 
debug1: Will attempt key: /root/.ssh/id_ed25519_sk 
debug1: Will attempt key: /root/.ssh/id_xmss 
debug1: Will attempt key: /root/.ssh/id_dsa 
debug2: pubkey_prepare: done
debug2: service_accept: ssh-userauth
debug1: SSH2_MSG_SERVICE_ACCEPT received
debug1: Authentications that can continue: publickey,password
debug1: Next authentication method: publickey
debug1: Offering public key: /root/.ssh/id_rsa RSA SHA256:TdPH7qoRFHoJvHzyHqSCWEwBe5gv6TuqnOHUcD6B4Nc
debug1: send_pubkey_test: no mutual signature algorithm
debug1: Trying private key: /root/.ssh/id_ecdsa
debug1: Trying private key: /root/.ssh/id_ecdsa_sk
debug1: Trying private key: /root/.ssh/id_ed25519
debug1: Trying private key: /root/.ssh/id_ed25519_sk
debug1: Trying private key: /root/.ssh/id_xmss
debug1: Trying private key: /root/.ssh/id_dsa
debug2: we did not send a packet, disable method
debug1: Next authentication method: password

After this, SSH tries other keys and ultimately falls back to password authentication.

How can I resolve this issue? Why is Debian 12 unable to SSH into Debian 8 using my ssh-rsa private key?

---

Answer:


1. Allow ssh-rsa as a signing algorithm on the client:

Open or create the SSH client configuration file on your Debian 12 machine:

Code: Select all

sudo nano /etc/ssh/ssh_config

2. Add support for ssh-rsa:

Add the following lines at the end of the file or within the appropriate section for the specific server:

Code: Select all

Host <server_name_or_ip>
HostkeyAlgorithms +ssh-rsa
PubkeyAcceptedAlgorithms +ssh-rsa

Replace <server_name_or_ip> with the server’s name or its IP address. If you want this to apply to all servers, you can use an asterisk (*) instead of the hostname:

Code: Select all

Host *
HostkeyAlgorithms +ssh-rsa
PubkeyAcceptedAlgorithms +ssh-rsa

3. Save and exit the editor, then try connecting again using your SSH key.

If you still encounter issues, check:
• Whether the permissions for your private key are set correctly (e.g., chmod 600 ~/.ssh/id_rsa).
• Whether the server is using an SSH version that matches the algorithms available on your client.

This should enable you to successfully connect using an ssh-rsa key from your Debian 12 machine to the Debian 8 server.