send_pubkey_test: no mutual signature algorithm

Question

Here is the client log output after a ssh -vvv user@machine (I think this problem is related with the deprecation of sha-1). I have already tried to create a new key/par for ed25519, but it doesn't work either. The server is for 2014 and maybe my ssh version doesn't even have support for that. I don't know. So I removed the ed25519 keys and start over.

The client -vvv output:

OpenSSH_9.4p1, OpenSSL 3.1.2 1 Aug 2023
debug1: Reading configuration data /c/Users/xxx/.ssh/config
debug1: Reading configuration data /etc/ssh/ssh_config
debug2: resolve_canonicalize: hostname xx.xxx.xx.xxx is address
debug3: expanded UserKnownHostsFile '~/.ssh/known_hosts' -> '/c/Users/xxx/.ssh/known_hosts'
debug3: expanded UserKnownHostsFile '~/.ssh/known_hosts2' -> '/c/Users/xxx/.ssh/known_hosts2'
debug3: ssh_connect_direct: entering
debug1: Connecting to xx.xxx.xx.xxx [xx.xxx.xx.xxx] port 22.
debug3: set_sock_tos: set socket 4 IP_TOS 0x48
debug1: Connection established.
debug1: identity file /c/Users/xxx/.ssh/id_rsa type 0
debug1: identity file /c/Users/xxx/.ssh/id_rsa-cert type -1
debug1: identity file /c/Users/xxx/.ssh/id_ecdsa type -1
debug1: identity file /c/Users/xxx/.ssh/id_ecdsa-cert type -1
debug1: identity file /c/Users/xxx/.ssh/id_ecdsa_sk type -1
debug1: identity file /c/Users/xxx/.ssh/id_ecdsa_sk-cert type -1
debug1: identity file /c/Users/xxx/.ssh/id_ed25519 type -1
debug1: identity file /c/Users/xxx/.ssh/id_ed25519-cert type -1
debug1: identity file /c/Users/xxx/.ssh/id_ed25519_sk type -1
debug1: identity file /c/Users/xxx/.ssh/id_ed25519_sk-cert type -1
debug1: identity file /c/Users/xxx/.ssh/id_xmss type -1
debug1: identity file /c/Users/xxx/.ssh/id_xmss-cert type -1
debug1: identity file /c/Users/xxx/.ssh/id_dsa type -1
debug1: identity file /c/Users/xxx/.ssh/id_dsa-cert type -1
debug1: Local version string SSH-2.0-OpenSSH_9.4
debug1: Remote protocol version 2.0, remote software version OpenSSH_6.6.1p1 Ubuntu-2ubuntu2.13
debug1: compat_banner: match: OpenSSH_6.6.1p1 Ubuntu-2ubuntu2.13 pat OpenSSH_6.6.1* compat 0x04000002
debug2: fd 4 setting O_NONBLOCK
debug1: Authenticating to xx.xxx.xx.xxx:22 as 'xxx'
debug3: record_hostkey: found key type ECDSA in file /c/Users/xxx/.ssh/known_hosts:4
debug3: load_hostkeys_file: loaded 1 keys from xx.xxx.xx.xxx
debug1: load_hostkeys: fopen /c/Users/xxx/.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
debug3: order_hostkeyalgs: prefer hostkeyalgs: [email protected],ecdsa-sha2-nistp256
debug3: send packet: type 20
debug1: SSH2_MSG_KEXINIT sent
debug3: receive packet: type 20
debug1: SSH2_MSG_KEXINIT received
debug2: local client KEXINIT proposal
debug2: KEX algorithms: [email protected],curve25519-sha256,[email protected],ecdh-sha2-nistp256,ecdh-sha2-nistp384,ecdh-sha2-nistp521,diffie-hellman-group-exchange-sha256,diffie-hellman-group16-sha512,diffie-hellman-group18-sha512,diffie-hellman-group14-sha256,ext-info-c
debug2: host key algorithms: [email protected],ecdsa-sha2-nistp256,[email protected],[email protected],[email protected],[email protected],[email protected],[email protected],[email protected],ssh-ed25519,ecdsa-sha2-nistp384,ecdsa-sha2-nistp521,[email protected],[email protected],rsa-sha2-512,rsa-sha2-256
debug2: ciphers ctos: [email protected],aes128-ctr,aes192-ctr,aes256-ctr,[email protected],[email protected]
debug2: ciphers stoc: [email protected],aes128-ctr,aes192-ctr,aes256-ctr,[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],zlib
debug2: compression stoc: none,[email protected],zlib
debug2: languages ctos:
debug2: languages stoc:
debug2: first_kex_follows 0
debug2: reserved 0
debug2: peer server KEXINIT proposal
debug2: KEX algorithms: [email protected],ecdh-sha2-nistp256,ecdh-sha2-nistp384,ecdh-sha2-nistp521,diffie-hellman-group-exchange-sha256,diffie-hellman-group-exchange-sha1,diffie-hellman-group14-sha1,diffie-hellman-group1-sha1
debug2: host key algorithms: ssh-rsa,ssh-dss,ecdsa-sha2-nistp256,ssh-ed25519
debug2: ciphers ctos: aes128-ctr,aes192-ctr,aes256-ctr,arcfour256,arcfour128,[email protected],[email protected],[email protected],aes128-cbc,3des-cbc,blowfish-cbc,cast128-cbc,aes192-cbc,aes256-cbc,arcfour,[email protected]
debug2: ciphers stoc: aes128-ctr,aes192-ctr,aes256-ctr,arcfour256,arcfour128,[email protected],[email protected],[email protected],aes128-cbc,3des-cbc,blowfish-cbc,cast128-cbc,aes192-cbc,aes256-cbc,arcfour,[email protected]
debug2: MACs ctos: [email protected],[email protected],[email protected],[email protected],[email protected],[email protected],[email protected],[email protected],[email protected],hmac-md5,hmac-sha1,[email protected],[email protected],hmac-sha2-256,hmac-sha2-512,hmac-ripemd160,[email protected],hmac-sha1-96,hmac-md5-96
debug2: MACs stoc: [email protected],[email protected],[email protected],[email protected],[email protected],[email protected],[email protected],[email protected],[email protected],hmac-md5,hmac-sha1,[email protected],[email protected],hmac-sha2-256,hmac-sha2-512,hmac-ripemd160,[email protected],hmac-sha1-96,hmac-md5-96
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: ecdsa-sha2-nistp256
debug1: kex: server->client cipher: [email protected] MAC: <implicit> compression: none
debug1: kex: client->server cipher: [email protected] MAC: <implicit> compression: none
debug3: send packet: type 30
debug1: expecting SSH2_MSG_KEX_ECDH_REPLY
debug3: receive packet: type 31
debug1: SSH2_MSG_KEX_ECDH_REPLY received
debug1: Server host key: ecdsa-sha2-nistp256 SHA256:NzaIy51gTI4u1f8G8Sb5GbbmcspIIv2ghIEUfYEQE48
debug3: record_hostkey: found key type ECDSA in file /c/Users/xxx/.ssh/known_hosts:4
debug3: load_hostkeys_file: loaded 1 keys from xx.xxx.xx.xxx
debug1: load_hostkeys: fopen /c/Users/xxx/.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 'xx.xxx.xx.xxx' is known and matches the ECDSA host key.
debug1: Found key in /c/Users/xxx/.ssh/known_hosts:4
debug3: send packet: type 21
debug2: ssh_set_newkeys: mode 1
debug1: rekey out after 134217728 blocks
debug1: SSH2_MSG_NEWKEYS sent
debug1: expecting SSH2_MSG_NEWKEYS
debug3: receive packet: type 21
debug1: SSH2_MSG_NEWKEYS received
debug2: ssh_set_newkeys: mode 0
debug1: rekey in after 134217728 blocks
debug1: Will attempt key: /c/Users/xxx/.ssh/id_rsa RSA SHA256:3EyV4rvMJKw61loT3nB9pkdE8okBg5/DqrTnMhVOXRQ
debug1: Will attempt key: /c/Users/xxx/.ssh/id_ecdsa
debug1: Will attempt key: /c/Users/xxx/.ssh/id_ecdsa_sk
debug1: Will attempt key: /c/Users/xxx/.ssh/id_ed25519
debug1: Will attempt key: /c/Users/xxx/.ssh/id_ed25519_sk
debug1: Will attempt key: /c/Users/xxx/.ssh/id_xmss
debug1: Will attempt key: /c/Users/xxx/.ssh/id_dsa
debug2: pubkey_prepare: done
debug3: send packet: type 5
debug3: receive packet: type 6
debug2: service_accept: ssh-userauth
debug1: SSH2_MSG_SERVICE_ACCEPT received
debug3: send packet: type 50
debug3: receive packet: type 51
debug1: Authentications that can continue: publickey
debug3: start over, passed a different list publickey
debug3: preferred publickey,keyboard-interactive,password
debug3: authmethod_lookup publickey
debug3: remaining preferred: keyboard-interactive,password
debug3: authmethod_is_enabled publickey
debug1: Next authentication method: publickey
debug1: Offering public key: /c/Users/xxx/.ssh/id_rsa RSA SHA256:3EyV4rvMJKw61loT3nB9pkdE8okBg5/DqrTnMhVOXRQ
debug1: send_pubkey_test: no mutual signature algorithm
debug1: Trying private key: /c/Users/xxx/.ssh/id_ecdsa
debug3: no such identity: /c/Users/xxx/.ssh/id_ecdsa: No such file or directory
debug1: Trying private key: /c/Users/xxx/.ssh/id_ecdsa_sk
debug3: no such identity: /c/Users/xxx/.ssh/id_ecdsa_sk: No such file or directory
debug1: Trying private key: /c/Users/xxx/.ssh/id_ed25519
debug3: no such identity: /c/Users/xxx/.ssh/id_ed25519: No such file or directory
debug1: Trying private key: /c/Users/xxx/.ssh/id_ed25519_sk
debug3: no such identity: /c/Users/xxx/.ssh/id_ed25519_sk: No such file or directory
debug1: Trying private key: /c/Users/xxx/.ssh/id_xmss
debug3: no such identity: /c/Users/xxx/.ssh/id_xmss: No such file or directory
debug1: Trying private key: /c/Users/xxx/.ssh/id_dsa
debug3: no such identity: /c/Users/xxx/.ssh/id_dsa: No such file or directory
debug2: we did not send a packet, disable method
debug1: No more authentication methods to try.
[email protected]: Permission denied (publickey).

Server config:

$ cat /etc/ssh/sshd_config
Port 22
Protocol 2
HostKey /etc/ssh/ssh_host_rsa_key
HostKey /etc/ssh/ssh_host_dsa_key
HostKey /etc/ssh/ssh_host_ecdsa_key
HostKey /etc/ssh/ssh_host_ed25519_key
UsePrivilegeSeparation yes
KeyRegenerationInterval 3600
ServerKeyBits 1024
SyslogFacility AUTH
LogLevel INFO
LoginGraceTime 120
PermitRootLogin yes
StrictModes yes
RSAAuthentication yes
PubkeyAuthentication yes
IgnoreRhosts yes
RhostsRSAAuthentication no
HostbasedAuthentication no
PermitEmptyPasswords no
ChallengeResponseAuthentication no
PasswordAuthentication no
X11Forwarding yes
X11DisplayOffset 10
PrintMotd no
PrintLastLog yes
TCPKeepAlive yes
AcceptEnv LANG LC_*
Subsystem sftp /usr/lib/openssh/sftp-server
UsePAM yes
AllowUsers root xxx

Answer 1

Not sure what the issue actually was, but I created a new ssh key/pair using ECDSA:

ssh-keygen -t ecdsa

This step is justified by the log line shown above which said record_hostkey: found key type ECDSA in file ..., which seems to imply according to some other Internet source that ECDSA is the key-type preferred by the server. So I created my own ecdsa key.

After this step, I had the new public/private pair in ~/.ssh for ecdsa: id_ecdsa and id_ecdsa.pub.

Now, I accessed my server using the remote console (offered by my server provider), set the PasswordAuthentication to yes in /etc/ssh/sshd_config so that I can (temporarily) authenticate by using a password instead of a key, and finally restarted the ssh server.

Afterwards, I copied the newly generated ecdsa public key to the authorized keys of the remote user I'm interested in by executing in my client machine:

ssh-copy-id -i ~/.ssh/id_ecdsa.pub myuser@server-ip

and typing the remote user's password.

Afterwards, I disabled password authentication my setting PasswordAuthentication to no again, and restarted the ssh server, and now I can succesfully ssh to the remote server as usual.