Ubuntu 22.04 SSH the RSA key isn't working since upgrading from 20.04

Up until last week I was running Ubuntu 20.04 happily, and then over the weekend decided to back everything up and install 22.04. I've had a couple of teething issues which I've solver, however I'm having real issues with SSH. I have two first generation WD MyCloud drives which handle all my backups and files both on and away from home. I can still connect to the shares with no problems, however I need to SSH onto both drives in order to run maintenance, backup between cloud drives, etc.

Initially I couldn't gain SSH access at all after upgrading, however the one-fix at this website worked. I can now connect via SSH and entering a password.

However with Ubuntu 20.04 I had set up a passphrase so that various autyomated scripts that I use using rsync could copy between cloud drives and also between Ubuntu and the cloud drive shares. This was working until I upgraded, now the scripts continually ask me for my password and I can't figure out how to stop it.

What I was originally doing was running

ssh-keygen -b 4096

to generate a passphrase and then

ssh-copy-id root@server

to copy the passphrase across

If I then entered

ssh root@server

it simply connected without asking to my password.

I know this is going to be due to my cloud drives only supporting the now insecure SSH, but I cannot upgrade it to a more secure one (unless someone knows how - I would prefer to do this to be honest). My maintenance scripts can make up to 20 connections over a period of hours, and to have to sit and constantly enter the password is becoming a pain.

Can anyone help me get my remote rsync commands working again so they don't keep asking me for my password

The terminal outputs as I run through these are

colin@colin-desktop:~/.ssh$ ssh-keygen -b 4096

Generating public/private rsa key pair.
Enter file in which to save the key (/home/colin/.ssh/id_rsa): 
Enter passphrase (empty for no passphrase): 
Enter same passphrase again: 
Your identification has been saved in /home/colin/.ssh/id_rsa
Your public key has been saved in /home/colin/.ssh/id_rsa.pub
The key fingerprint is:
SHA256:xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx colin@colin-desktop
The key's randomart image is:
+---[RSA 4096]----+
...
+----[SHA256]-----+

colin@colin-desktop:~/.ssh$ ssh-copy-id root@xxx.xxx.xxx.xxx

/usr/bin/ssh-copy-id: INFO: attempting to log in with the new key(s), to filter out any that are already installed
/usr/bin/ssh-copy-id: INFO: 1 key(s) remain to be installed -- if you are prompted now it is to install the new keys
root@xxx.xxx.xxx.xxx's password: 

Number of key(s) added: 1

Now try logging into the machine, with:   "ssh 'root@xxx.xxx.xxx.xxx'"
and check to make sure that only the key(s) you wanted were added.

colin@colin-desktop:~/.ssh$ ssh root@xxx.xxx.xxx.xxx

root@xxx.xxx.xxx.xxx's password: 

Linux NASServer 3.2.26 #1 SMP Thu Jul 9 11:14:15 PDT 2015 wd-2.4-rel armv7l

The programs included with the Debian GNU/Linux system are free software;
the exact distribution terms for each program are described in the
individual files in /usr/share/doc/*/copyright.

Debian GNU/Linux comes with ABSOLUTELY NO WARRANTY, to the extent
permitted by applicable law.

NASServer:~# cd ~/.ssh

NASSERVER:~/.ssh# ls -al

total 12
drwx------ 2 root root 4096 May 17 23:32 .
drwx------ 7 root root 4096 Apr 28 19:02 ..
-rw------- 1 root root  742 May 17 23:32 authorized_keys

NASServer:~/.ssh# exit

logout
Connection to xxx.xxx.xxx.xxx closed.

colin@colin-desktop:~$ rsync --verbose --archive -e 'ssh -p 22' ~/Files/ root@xxx.xxx.xxx.xxx:/shares/Files/

root@xxx.xxx.xxx.xxx's password: 

How this originally came about was that I needed to be able to rsync to and from a remote location without the need for a human intervention regarding security. The instructions I was given were to use ssh-keygen to generate public/private keys and then ssh-copy-id to copy the public key to the remote host. I've just reinstalled 20.04 on another machine and used this successfully and the rsync is working without the need for a password. However if I clear the keys on the server out, reinstall 22.04 and do the same, it still prompts me for the password. I've updated my question to show the output of the commands as they are being run on Ubuntu 22.04 with the server name obscured for obvious reasons.

The Terminal output of rsync -vvv follows

colin@colin-desktop:~$ ssh -vvv root@xxx.xxx.xxx.xxx
OpenSSH_8.9p1 Ubuntu-3, OpenSSL 3.0.2 15 Mar 2022
debug1: Reading configuration data /home/colin/.ssh/config
debug3: kex names ok: [diffie-hellman-group1-sha1,diffie-hellman-group14-sha1,diffie-hellman-group14-sha256,diffie-hellman-group16-sha512,diffie-hellman-group18-sha512,diffie-hellman-group-exchange-sha1,diffie-hellman-group-exchange-sha256,ecdh-sha2-nistp256,ecdh-sha2-nistp384,ecdh-sha2-nistp521,curve25519-sha256,curve25519-sha256@libssh.org,sntrup761x25519-sha512@openssh.com]
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 xxx.xxx.xxx.xxx is address
debug3: expanded UserKnownHostsFile '~/.ssh/known_hosts' -> '/home/colin/.ssh/known_hosts'
debug3: expanded UserKnownHostsFile '~/.ssh/known_hosts2' -> '/home/colin/.ssh/known_hosts2'
debug3: ssh_connect_direct: entering
debug1: Connecting to xxx.xxx.xxx.xxx [xxx.xxx.xxx.xxx] port 22.
debug3: set_sock_tos: set socket 3 IP_TOS 0x10
debug1: Connection established.
debug1: identity file /home/colin/.ssh/id_rsa type 0
debug1: identity file /home/colin/.ssh/id_rsa-cert type -1
debug1: identity file /home/colin/.ssh/id_ecdsa type -1
debug1: identity file /home/colin/.ssh/id_ecdsa-cert type -1
debug1: identity file /home/colin/.ssh/id_ecdsa_sk type -1
debug1: identity file /home/colin/.ssh/id_ecdsa_sk-cert type -1
debug1: identity file /home/colin/.ssh/id_ed25519 type -1
debug1: identity file /home/colin/.ssh/id_ed25519-cert type -1
debug1: identity file /home/colin/.ssh/id_ed25519_sk type -1
debug1: identity file /home/colin/.ssh/id_ed25519_sk-cert type -1
debug1: identity file /home/colin/.ssh/id_xmss type -1
debug1: identity file /home/colin/.ssh/id_xmss-cert type -1
debug1: identity file /home/colin/.ssh/id_dsa type -1
debug1: identity file /home/colin/.ssh/id_dsa-cert type -1
debug1: Local version string SSH-2.0-OpenSSH_8.9p1 Ubuntu-3
debug1: Remote protocol version 2.0, remote software version OpenSSH_6.0p1 Debian-4
debug1: compat_banner: match: OpenSSH_6.0p1 Debian-4 pat OpenSSH* compat 0x04000000
debug2: fd 3 setting O_NONBLOCK
debug1: Authenticating to xxx.xxx.xxx.xxx:22 as 'root'
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: diffie-hellman-group1-sha1,diffie-hellman-group14-sha1,diffie-hellman-group14-sha256,diffie-hellman-group16-sha512,diffie-hellman-group18-sha512,diffie-hellman-group-exchange-sha1,diffie-hellman-group-exchange-sha256,ecdh-sha2-nistp256,ecdh-sha2-nistp384,ecdh-sha2-nistp521,curve25519-sha256,curve25519-sha256@libssh.org,sntrup761x25519-sha512@openssh.com,ext-info-c
debug2: host key algorithms: ssh-ed25519,ssh-ed25519-cert-v01@openssh.com,sk-ssh-ed25519@openssh.com,sk-ssh-ed25519-cert-v01@openssh.com,ssh-rsa,ssh-dss,ecdsa-sha2-nistp256,ecdsa-sha2-nistp384,ecdsa-sha2-nistp521,sk-ecdsa-sha2-nistp256@openssh.com,ssh-rsa-cert-v01@openssh.com,ssh-dss-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-ecdsa-sha2-nistp256-cert-v01@openssh.com
debug2: ciphers ctos: 3des-cbc,aes128-cbc,aes192-cbc,aes256-cbc,aes128-ctr,aes192-ctr,aes256-ctr,aes128-gcm@openssh.com,aes256-gcm@openssh.com,chacha20-poly1305@openssh.com
debug2: ciphers stoc: 3des-cbc,aes128-cbc,aes192-cbc,aes256-cbc,aes128-ctr,aes192-ctr,aes256-ctr,aes128-gcm@openssh.com,aes256-gcm@openssh.com,chacha20-poly1305@openssh.com
debug2: MACs ctos: hmac-sha1,hmac-sha1-96,hmac-sha2-256,hmac-sha2-512,hmac-md5,hmac-md5-96,umac-64@openssh.com,umac-128@openssh.com,hmac-sha1-etm@openssh.com,hmac-sha1-96-etm@openssh.com,hmac-sha2-256-etm@openssh.com,hmac-sha2-512-etm@openssh.com,hmac-md5-etm@openssh.com,hmac-md5-96-etm@openssh.com,umac-64-etm@openssh.com,umac-128-etm@openssh.com
debug2: MACs stoc: hmac-sha1,hmac-sha1-96,hmac-sha2-256,hmac-sha2-512,hmac-md5,hmac-md5-96,umac-64@openssh.com,umac-128@openssh.com,hmac-sha1-etm@openssh.com,hmac-sha1-96-etm@openssh.com,hmac-sha2-256-etm@openssh.com,hmac-sha2-512-etm@openssh.com,hmac-md5-etm@openssh.com,hmac-md5-96-etm@openssh.com,umac-64-etm@openssh.com,umac-128-etm@openssh.com
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: 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
debug2: ciphers ctos: aes128-ctr,aes192-ctr,aes256-ctr,arcfour256,arcfour128,aes128-cbc,3des-cbc,blowfish-cbc,cast128-cbc,aes192-cbc,aes256-cbc,arcfour,rijndael-cbc@lysator.liu.se
debug2: ciphers stoc: aes128-ctr,aes192-ctr,aes256-ctr,arcfour256,arcfour128,aes128-cbc,3des-cbc,blowfish-cbc,cast128-cbc,aes192-cbc,aes256-cbc,arcfour,rijndael-cbc@lysator.liu.se
debug2: MACs ctos: hmac-md5,hmac-sha1,umac-64@openssh.com,hmac-sha2-256,hmac-sha2-256-96,hmac-sha2-512,hmac-sha2-512-96,hmac-ripemd160,hmac-ripemd160@openssh.com,hmac-sha1-96,hmac-md5-96
debug2: MACs stoc: hmac-md5,hmac-sha1,umac-64@openssh.com,hmac-sha2-256,hmac-sha2-256-96,hmac-sha2-512,hmac-sha2-512-96,hmac-ripemd160,hmac-ripemd160@openssh.com,hmac-sha1-96,hmac-md5-96
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: diffie-hellman-group1-sha1
debug1: kex: host key algorithm: ssh-rsa
debug1: kex: server->client cipher: 3des-cbc MAC: hmac-sha1 compression: none
debug1: kex: client->server cipher: 3des-cbc MAC: hmac-sha1 compression: none
debug2: bits set: 515/1024
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-rsa SHA256:XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
debug3: record_hostkey: found key type RSA in file /home/colin/.ssh/known_hosts:1
debug3: load_hostkeys_file: loaded 1 keys from xxx.xxx.xxx.xxx
debug1: load_hostkeys: fopen /home/colin/.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 'xxx.xxx.xxx.xxx' is known and matches the RSA host key.
debug1: Found key in /home/colin/.ssh/known_hosts:1
debug2: bits set: 495/1024
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/colin/.ssh/id_rsa RSA SHA256:XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX agent
debug1: Will attempt key: /home/colin/.ssh/id_ecdsa 
debug1: Will attempt key: /home/colin/.ssh/id_ecdsa_sk 
debug1: Will attempt key: /home/colin/.ssh/id_ed25519 
debug1: Will attempt key: /home/colin/.ssh/id_ed25519_sk 
debug1: Will attempt key: /home/colin/.ssh/id_xmss 
debug1: Will attempt key: /home/colin/.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,password
debug3: start over, passed a different list publickey,password
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/colin/.ssh/id_rsa RSA SHA256:XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX agent
debug1: send_pubkey_test: no mutual signature algorithm
debug1: Trying private key: /home/colin/.ssh/id_ecdsa
debug3: no such identity: /home/colin/.ssh/id_ecdsa: No such file or directory
debug1: Trying private key: /home/colin/.ssh/id_ecdsa_sk
debug3: no such identity: /home/colin/.ssh/id_ecdsa_sk: No such file or directory
debug1: Trying private key: /home/colin/.ssh/id_ed25519
debug3: no such identity: /home/colin/.ssh/id_ed25519: No such file or directory
debug1: Trying private key: /home/colin/.ssh/id_ed25519_sk
debug3: no such identity: /home/colin/.ssh/id_ed25519_sk: No such file or directory
debug1: Trying private key: /home/colin/.ssh/id_xmss
debug3: no such identity: /home/colin/.ssh/id_xmss: No such file or directory
debug1: Trying private key: /home/colin/.ssh/id_dsa
debug3: no such identity: /home/colin/.ssh/id_dsa: No such file or directory
debug2: we did not send a packet, disable method
debug3: authmethod_lookup password
debug3: remaining preferred: ,password
debug3: authmethod_is_enabled password
debug1: Next authentication method: password
root@xxx.xxx.xxx.xxx's password: 

• ssh
• encryption
• rsync

Share

Cause

The RSA SHA-1 hash algorithm is being quickly deprecated across operating systems and SSH clients because of various security vulnerabilities, with many of these technologies now outright denying the use of this algorithm.

It seems this has happened for the ssh client in Ubuntu 22.04. The RSA public-private key pair is considered not safe any more.

Solution

Use a more modern and secure type of key such as ed25519. Generate a new key pair in your Ubuntu 22.04 computer with this command:

ssh-keygen -t ed25519 -C "colin@colin-desktop"

Note: the string after -C is a comment it is customary to put your email address here. Since you may only be using this key within your home, putting the email address may not make sense. I would put something like "colin@colin-desktop" so that you know which user and computer the key belongs to within your household.

Alternately you may create a new RSA key with SHA2 hashing like so:

ssh-keygen -t rsa-sha2-512 -b 4096

Either way you will need to use the ssh-copy-id command again:

ssh-copy-id root@xxx.xxx.xxx.xxx

This command will recognize there is a new public key and copy the new key to the /root/.ssh/authorized_keys file.

It should work now.

A Remote Server Workaround

If you can't change anything on the local computer, or don't want to use a new key, and want to re-enable RSA on the local computer, edit the file /etc/ssh/sshd_config on the remote computer and add this line:

HostKeyAlgorithms +ssh-rsa
PubkeyAcceptedKeyTypes +ssh-rsa

This will allow the use of unsafe RSA key you already have.

Remember to restart the sshd service by:

sudo systemctl restart sshd

Otherwise you will have to restart your computer to make the change take effect.

References

• SSH-RSA key rejected with message "no mutual signature algorithm"
• OpenSSH 8.3 released (and ssh-rsa deprecation notice)
• HostKeyAlgorithm

Hope this helps