connect using SSH to a remote server from client running ubuntu 22.04

Question

I am trying to connect to a remote server using SSH from client running ubuntu 22.04

Server is a cloud instance of OVH ISP, running ubuntu 23.04.

In OVH doc, it is mentioned: "You can only store RSA and ECDSA encrypted keys; ED25519 is currently not supported.". So I created, as they propose, an RSA key on my client, using:

ssh-keygen -b 4096, and copied the key to the cloud instance server.

Now, when I try to connect, using:

ssh ubuntu@135.125.94.203

I get:

The authenticity of host '135.125.94.203' can't be established. ED25519 key fingerprint is SHA256:xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx. This key is not known by any other names Are you sure you want to continue connecting (yes/no/[fingerprint])?

When I answer yes, I get: ubuntu@135.125.94.203: Permission denied (publickey).

I read different messages about that, but in the first place I don't understand why ED25519 is mentioned, since I created an RSA key.

I tried to add: PubkeyAcceptedKeyTypes +ssh-rsa at the end of /etc/ssh/sshd_config and restart ssh, but it didn't help.

Below is the log of ssh -vvv ubuntu@135.125.94.203

OpenSSH_8.9p1 Ubuntu-3ubuntu0.1, OpenSSL 3.0.2 15 Mar 2022
debug1: Reading configuration data /etc/ssh/ssh_config
debug1: /etc/ssh/ssh_config line 19: include /etc/ssh/ssh_config.d/*.conf matched no files
debug1: /etc/ssh/ssh_config line 21: Applying options for *
debug2: resolve_canonicalize: hostname 135.125.94.203 is address
debug3: expanded UserKnownHostsFile '~/.ssh/known_hosts' -> '/home/mp/.ssh/known_hosts'
debug3: expanded UserKnownHostsFile '~/.ssh/known_hosts2' -> '/home/mp/.ssh/known_hosts2'
debug3: ssh_connect_direct: entering
debug1: Connecting to 135.125.94.203 [135.125.94.203] port 22.
debug3: set_sock_tos: set socket 3 IP_TOS 0x10
debug1: Connection established.
debug1: identity file /home/mp/.ssh/id_rsa type 0
debug1: identity file /home/mp/.ssh/id_rsa-cert type -1
debug1: identity file /home/mp/.ssh/id_ecdsa type -1
debug1: identity file /home/mp/.ssh/id_ecdsa-cert type -1
debug1: identity file /home/mp/.ssh/id_ecdsa_sk type -1
debug1: identity file /home/mp/.ssh/id_ecdsa_sk-cert type -1
debug1: identity file /home/mp/.ssh/id_ed25519 type -1
debug1: identity file /home/mp/.ssh/id_ed25519-cert type -1
debug1: identity file /home/mp/.ssh/id_ed25519_sk type -1
debug1: identity file /home/mp/.ssh/id_ed25519_sk-cert type -1
debug1: identity file /home/mp/.ssh/id_xmss type -1
debug1: identity file /home/mp/.ssh/id_xmss-cert type -1
debug1: identity file /home/mp/.ssh/id_dsa type -1
debug1: identity file /home/mp/.ssh/id_dsa-cert type -1
debug1: Local version string SSH-2.0-OpenSSH_8.9p1 Ubuntu-3ubuntu0.1
debug1: Remote protocol version 2.0, remote software version OpenSSH_9.0p1 Ubuntu-1ubuntu8
debug1: compat_banner: match: OpenSSH_9.0p1 Ubuntu-1ubuntu8 pat OpenSSH* compat 0x04000000
debug2: fd 3 setting O_NONBLOCK
debug1: Authenticating to 135.125.94.203:22 as 'ubuntu'
debug3: record_hostkey: found key type ED25519 in file /home/mp/.ssh/known_hosts:1
debug3: load_hostkeys_file: loaded 1 keys from 135.125.94.203
debug1: load_hostkeys: fopen /home/mp/.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: have matching best-preference key type ssh-ed25519-cert-v01@openssh.com, using HostkeyAlgorithms verbatim
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: curve25519-sha256,curve25519-sha256@libssh.org,ecdh-sha2-nistp256,ecdh-sha2-nistp384,ecdh-sha2-nistp521,sntrup761x25519-sha512@openssh.com,diffie-hellman-group-exchange-sha256,diffie-hellman-group16-sha512,diffie-hellman-group18-sha512,diffie-hellman-group14-sha256,ext-info-c
debug2: host key algorithms: ssh-ed25519-cert-v01@openssh.com,ecdsa-sha2-nistp256-cert-v01@openssh.com,ecdsa-sha2-nistp384-cert-v01@openssh.com,ecdsa-sha2-nistp521-cert-v01@openssh.com,sk-ssh-ed25519-cert-v01@openssh.com,sk-ecdsa-sha2-nistp256-cert-v01@openssh.com,rsa-sha2-512-cert-v01@openssh.com,rsa-sha2-256-cert-v01@openssh.com,ssh-ed25519,ecdsa-sha2-nistp256,ecdsa-sha2-nistp384,ecdsa-sha2-nistp521,sk-ssh-ed25519@openssh.com,sk-ecdsa-sha2-nistp256@openssh.com,rsa-sha2-512,rsa-sha2-256
debug2: ciphers ctos: chacha20-poly1305@openssh.com,aes128-ctr,aes192-ctr,aes256-ctr,aes128-gcm@openssh.com,aes256-gcm@openssh.com
debug2: ciphers stoc: chacha20-poly1305@openssh.com,aes128-ctr,aes192-ctr,aes256-ctr,aes128-gcm@openssh.com,aes256-gcm@openssh.com
debug2: MACs ctos: umac-64-etm@openssh.com,umac-128-etm@openssh.com,hmac-sha2-256-etm@openssh.com,hmac-sha2-512-etm@openssh.com,hmac-sha1-etm@openssh.com,umac-64@openssh.com,umac-128@openssh.com,hmac-sha2-256,hmac-sha2-512,hmac-sha1
debug2: MACs stoc: umac-64-etm@openssh.com,umac-128-etm@openssh.com,hmac-sha2-256-etm@openssh.com,hmac-sha2-512-etm@openssh.com,hmac-sha1-etm@openssh.com,umac-64@openssh.com,umac-128@openssh.com,hmac-sha2-256,hmac-sha2-512,hmac-sha1
debug2: compression ctos: none,zlib@openssh.com,zlib
debug2: compression stoc: none,zlib@openssh.com,zlib
debug2: languages ctos: 
debug2: languages stoc: 
debug2: first_kex_follows 0 
debug2: reserved 0 
debug2: peer server KEXINIT proposal
debug2: KEX algorithms: sntrup761x25519-sha512@openssh.com,curve25519-sha256,curve25519-sha256@libssh.org,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
debug2: host key algorithms: rsa-sha2-512,rsa-sha2-256,ecdsa-sha2-nistp256,ssh-ed25519
debug2: ciphers ctos: chacha20-poly1305@openssh.com,aes128-ctr,aes192-ctr,aes256-ctr,aes128-gcm@openssh.com,aes256-gcm@openssh.com
debug2: ciphers stoc: chacha20-poly1305@openssh.com,aes128-ctr,aes192-ctr,aes256-ctr,aes128-gcm@openssh.com,aes256-gcm@openssh.com
debug2: MACs ctos: umac-64-etm@openssh.com,umac-128-etm@openssh.com,hmac-sha2-256-etm@openssh.com,hmac-sha2-512-etm@openssh.com,hmac-sha1-etm@openssh.com,umac-64@openssh.com,umac-128@openssh.com,hmac-sha2-256,hmac-sha2-512,hmac-sha1
debug2: MACs stoc: umac-64-etm@openssh.com,umac-128-etm@openssh.com,hmac-sha2-256-etm@openssh.com,hmac-sha2-512-etm@openssh.com,hmac-sha1-etm@openssh.com,umac-64@openssh.com,umac-128@openssh.com,hmac-sha2-256,hmac-sha2-512,hmac-sha1
debug2: compression ctos: none,zlib@openssh.com
debug2: compression stoc: none,zlib@openssh.com
debug2: languages ctos: 
debug2: languages stoc: 
debug2: first_kex_follows 0 
debug2: reserved 0 
debug1: kex: algorithm: curve25519-sha256
debug1: kex: host key algorithm: ssh-ed25519
debug1: kex: server->client cipher: chacha20-poly1305@openssh.com MAC: <implicit> compression: none
debug1: kex: client->server cipher: chacha20-poly1305@openssh.com 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: ssh-ed25519 SHA256:78sCXM8oOJ0H7mq/mhlVw6N/iLgtGSf6ua3Fr91j0Lo
debug3: record_hostkey: found key type ED25519 in file /home/mp/.ssh/known_hosts:1
debug3: load_hostkeys_file: loaded 1 keys from 135.125.94.203
debug1: load_hostkeys: fopen /home/mp/.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 '135.125.94.203' is known and matches the ED25519 host key.
debug1: Found key in /home/mp/.ssh/known_hosts:1
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: get_agent_identities: bound agent to hostkey
debug1: get_agent_identities: agent returned 1 keys
debug1: Will attempt key: /home/mp/.ssh/id_rsa RSA SHA256:k1ZxU52fxS6qcGnXNplNGShPZdv4aqFYR30JHvSoeeo agent
debug1: Will attempt key: /home/mp/.ssh/id_ecdsa 
debug1: Will attempt key: /home/mp/.ssh/id_ecdsa_sk 
debug1: Will attempt key: /home/mp/.ssh/id_ed25519 
debug1: Will attempt key: /home/mp/.ssh/id_ed25519_sk 
debug1: Will attempt key: /home/mp/.ssh/id_xmss 
debug1: Will attempt key: /home/mp/.ssh/id_dsa 
debug2: pubkey_prepare: done
debug3: send packet: type 5
debug3: receive packet: type 7
debug1: SSH2_MSG_EXT_INFO received
debug1: kex_input_ext_info: server-sig-algs=<ssh-ed25519,sk-ssh-ed25519@openssh.com,ssh-rsa,rsa-sha2-256,rsa-sha2-512,ssh-dss,ecdsa-sha2-nistp256,ecdsa-sha2-nistp384,ecdsa-sha2-nistp521,sk-ecdsa-sha2-nistp256@openssh.com,webauthn-sk-ecdsa-sha2-nistp256@openssh.com>
debug1: kex_input_ext_info: publickey-hostbound@openssh.com=<0>
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 gssapi-with-mic,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: /home/mp/.ssh/id_rsa RSA SHA256:k1ZxU52fxS6qcGnXNplNGShPZdv4aqFYR30JHvSoeeo agent
debug3: send packet: type 50
debug2: we sent a publickey packet, wait for reply
debug3: receive packet: type 51
debug1: Authentications that can continue: publickey
debug1: Trying private key: /home/mp/.ssh/id_ecdsa
debug3: no such identity: /home/mp/.ssh/id_ecdsa: No such file or directory
debug1: Trying private key: /home/mp/.ssh/id_ecdsa_sk
debug3: no such identity: /home/mp/.ssh/id_ecdsa_sk: No such file or directory
debug1: Trying private key: /home/mp/.ssh/id_ed25519
debug3: no such identity: /home/mp/.ssh/id_ed25519: No such file or directory
debug1: Trying private key: /home/mp/.ssh/id_ed25519_sk
debug3: no such identity: /home/mp/.ssh/id_ed25519_sk: No such file or directory
debug1: Trying private key: /home/mp/.ssh/id_xmss
debug3: no such identity: /home/mp/.ssh/id_xmss: No such file or directory
debug1: Trying private key: /home/mp/.ssh/id_dsa
debug3: no such identity: /home/mp/.ssh/id_dsa: No such file or directory
debug2: we did not send a packet, disable method
debug1: No more authentication methods to try.
ubuntu@135.125.94.203: Permission denied (publickey).`

score 1 · Accepted Answer · answered May 16 '23 at 17:09

The "The authenticity of host" message is shown when you first try to connect to the server or the server's host key has changed. This is used to prevent MITM and similar attacks.

Permission denied (publickey).

This error means your public key is not authorised on the server. Your public key must be appended to ~/.ssh/authorized_keys on the server.

The verbose logs confirm that your key (/home/mp/.ssh/id_rsa) is not authorised on the server.

If you have no other way to access the server (e.g. online terminal via OVH's website) or using password auth, or booting in recovery (and authorise your key), then it is unlikely you will be able to access this server and you might have to reinstall it. If you can access it or after reinstalling, make sure to authorise your keys before making key auth the only way to access your server.

connect using SSH to a remote server from client running ubuntu 22.04

1 Answers1