Understanding ssh-rsa not in PubkeyAcceptedAlgorithms

Question

I am having problem in connecting to an Amazon EC2 Linux instance from an old Mac OS machine running El Capitan. Unfortunately without any possibility to upgrade the OS.

Because all the other modern devices I have can connect to the instance without any problems using the same key, I suppose the problem is related to the way the ssh client interact with the server, in particular due to old ssh client version.

The private key has been generated by the EC2 console.

So I went for a little debugging on the server side and found this message:

userauth_pubkey: key type ssh-rsa not in PubkeyAcceptedAlgorithms [preauth]

Then I have analyzed the authorized_keys file on server side and found this:

cat ~/.ssh/authorized_keys
ssh-rsa <long string> mykey-rsa

For start, I was wondering why if the key is marked as ssh-rsa the server is instead refusing such option.

So I ssh to the machine with -vvv option to get this fragment from the output:

debug2: kex_parse_kexinit: [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: kex_parse_kexinit: [email protected],[email protected],[email protected],[email protected],[email protected],[email protected],[email protected],[email protected],ecdsa-sha2-nistp256,ecdsa-sha2-nistp384,ecdsa-sha2-nistp521,ssh-ed25519,ssh-rsa,ssh-dss
debug2: kex_parse_kexinit: [email protected],aes128-ctr,aes192-ctr,aes256-ctr,[email protected],[email protected],arcfour256,arcfour128,aes128-cbc,3des-cbc,blowfish-cbc,cast128-cbc,aes192-cbc,aes256-cbc,arcfour,[email protected]
debug2: kex_parse_kexinit: [email protected],aes128-ctr,aes192-ctr,aes256-ctr,[email protected],[email protected],arcfour256,arcfour128,aes128-cbc,3des-cbc,blowfish-cbc,cast128-cbc,aes192-cbc,aes256-cbc,arcfour,[email protected]
debug2: kex_parse_kexinit: [email protected],[email protected],[email protected],[email protected],[email protected],[email protected],[email protected],hmac-sha2-256,hmac-sha2-512,hmac-sha1,[email protected],[email protected],[email protected],[email protected],hmac-md5,hmac-ripemd160,[email protected],hmac-sha1-96,hmac-md5-96
debug2: kex_parse_kexinit: [email protected],[email protected],[email protected],[email protected],[email protected],[email protected],[email protected],hmac-sha2-256,hmac-sha2-512,hmac-sha1,[email protected],[email protected],[email protected],[email protected],hmac-md5,hmac-ripemd160,[email protected],hmac-sha1-96,hmac-md5-96
debug2: kex_parse_kexinit: none,[email protected],zlib
debug2: kex_parse_kexinit: none,[email protected],zlib
    ....
debug2: kex_parse_kexinit: first_kex_follows 0 
debug2: kex_parse_kexinit: reserved 0 
debug2: kex_parse_kexinit: curve25519-sha256,[email protected],ecdh-sha2-nistp256,ecdh-sha2-nistp384,ecdh-sha2-nistp521,diffie-hellman-group-exchange-sha256,diffie-hellman-group14-sha256,diffie-hellman-group16-sha512,diffie-hellman-group18-sha512
debug2: kex_parse_kexinit: ecdsa-sha2-nistp256,ssh-ed25519
debug2: kex_parse_kexinit: [email protected],[email protected],aes256-ctr,[email protected],aes128-ctr
debug2: kex_parse_kexinit: [email protected],[email protected],aes256-ctr,[email protected],aes128-ctr
debug2: kex_parse_kexinit: [email protected],[email protected],[email protected],[email protected],hmac-sha2-256,hmac-sha1,[email protected],hmac-sha2-512
debug2: kex_parse_kexinit: [email protected],[email protected],[email protected],[email protected],hmac-sha2-256,hmac-sha1,[email protected],hmac-sha2-512
debug2: kex_parse_kexinit: none,[email protected]
debug2: kex_parse_kexinit: none,[email protected]

If I am not wrong the entries in the first part are the options from client side, while the others are from server side. Infact I can see that the ssh-rsa is only available on client side. So I tought that choosing one common algoritm would have solved the issue:

ssh -l ec2-user myserver -i .ssh/ec2-key.pem  -vvvvvv [email protected]

but again I am seeing the same error on server side:

userauth_pubkey: key type ssh-rsa not in PubkeyAcceptedAlgorithms [preauth]

what am I missing ?

I know that I could solve the problem by authorizing ssh-rsa on server side, but I am more interested in understanding what's going on.

[UPDATE]

Following the suggested approaches (which I have marked as accepted), I went for option 2, as it is not easy and probably dangerous to upgrade an old MacOS at such code level.

EC2 Key Pair console gives two options RSA and ED25519, I choosed a key with 'ED25519' and replaced the related public key on the authorized keys file and I can now connect to the instance.

Answer 1

The name ssh-rsa has two different meanings here.

There's the key type ssh-rsa which you can see in the first column of your authorized_keysfile. RSA keys are perfectly fine and widely supported.

However, there's also the signature algorithm ssh-rsa which stands for RSA signatures using the SHA-1 hash algorithm. Since SHA-1 is insecure, OpenSSH disables the ssh-rsa signature algorithm since version 8.8. SSH clients and servers are now expected to use rsa-sha2-256 (RSA signatures with SHA-256) or rsa-sha2-512 (RSA signatures with SHA-512).

To fix the problem, there are three options:

• Update the SSH client, so that the newer signature algorithms can be used. This is by far the best solution. If you cannot get a current OpenSSH version through your OS, then install OpenSSH independently.
• Create a new SSH key with the ECDSA type (e. g. ecdsa-sha2-nistp256) or EdDSA rather than RSA. Then you can circumvent the signature algorithm problem.
• If, for some strange reason, you cannot do either, then the last resort is to enable the ssh-rsa signature algorithm on the server by adding it to PubkeyAcceptedAlgorithms. Note that this is a security risk.