On May 27th, 2020 with the release of OpenSSH 8.3, openssh officially deprecated the rsa-sha1 keys. Their justification is really straightforward: for under US $50, that key can now be broken.

As this has begun to trickle in to supported distributions, people are finding that ssh, sftp, and scp are now complaining:

load pubkey "<key_path>": invalid format

While literally true, it is a pretty poorly written error message. What it actually means is that the key is a deprecated format, and what it does not tell you is that in the future the format will become completely unsupported.

The solution here is to replace your rsa-sha1 keys with either ecdsa or ed25519 keys, distribute those keys, and then remove the old ones.

The problem on AWS is that when you generate a key pair, it is still rsa-sha1 format, and while you can upload rsa-sha2 keys, ecdsa or ed25519 keys are not acceptable. There are questions about this going back to 2017 on the AWS forums, asking about other key formats.

We will circle back around to what likely needs to be done: generating a new ssh key and rotating out your old keys. The good news here is by default ssh-keygen now (and has for some time) defaulted to generating new rsa keys using the sha2 hashes. Creating a new key is as simple as this:

$ ssh-keygen -f ~/.ssh/id_rsa_new

This will create your new cryptographically stronger key. You can then add that to your openssh authorization agent:

$ ssh-add ~/.ssh/id_rsa_new

And then on an as-needed basis, copy it to other hosts you need to access with ssh-based tools:

$ ssh-copy-id -i ~/.ssh/id_rsa_new username@example.com

This will place the key in your authorized_keys file. You can then remove the old key from the authorized_keys file the next time you log in, and once you have updated all your keys, you can then remove the key from the openssh agent with ssh-add -d.

The good news here is that if you want to use the ecdsa or ed25519 keys, almost every service aside from AWS accepts them, and even then if you manage the ssh keys on your server separately from using AWS key pairs, you should be ok.

On the AWS side of things you can use the console to add a new key pair (ec2, select 'Key Pairs' on the left nav) or with the cli using aws ec2 import-key-pair. You will still need to distribute this key to already running instances, however.

If you have been struggling with the ssh error/warning for the last few days, this should help you rectify the issue.