If you get the following error message when connecting to a server (in my case, it was a GitLab instance running on Docker using something at least inspired by the official Docker image), you may be using an older SSH client, such as the one in RHEL/CentOS 6.
no hostkey alg
Some cursory web searching didn’t give me a satisfactory solution, so here goes: It seems likely that you’re using an older ssh client (for example, the one in CentOS 6.x). This client unfortunately doesn’t support the -Q option to list supported host keys, but we can figure out that information by doing the following:
ssh -vvvv 127.0.0.1
On a more modern system, you might get something like this:
debug2: host key algorithms: ecdsa-sha2-nistp256-cert-v01@openssh.com,ecdsa-sha2-nistp384-cert-v01@openssh.com,ecdsa-sha2-nistp521-cert-v01@openssh.com,ecdsa-sha2-nistp256,ecdsa-sha2-nistp384,ecdsa-sha2-nistp521,ssh-ed25519-cert-v01@openssh.com,ssh-rsa-cert-v01@openssh.com,ssh-ed25519,rsa-sha2-512,rsa-sha2-256,ssh-rsa
(Which is the same as ssh -Q key, but harder to read.)
On older systems, you won’t get the helpful “host key algorithms:” label, but you’ll still get the information. So perhaps look out for a line that contains “ssh-rsa”.
Then, try the same ssh -vvvv 12.34.56.78 (replace 12.34.56.78 with the target server’s name or address), and look at the equivalent line. (Or if you have access, log into the server and try ssh -Q key.)
In my case, the client only had ssh-rsa and ssh-dsa, and the target server only listed ecdsa-sha2-nistp256. In my case, this could be solved by entirely on the client side. All we have to do is add an option to the command line and create a key if it doesn’t exist yet:
ssh-keygen -t ecdsa -f /etc/ssh/ssh_host_ecdsa_key
ssh -o HostKeyAlgorithms=ecdsa-sha2-nistp256,ssh-rsa 12.34.56.78
To avoid adding this option every time, you can add the following into your ~/.ssh/config:
Host 12.34.56.78
HostKeyAlgorithms ecdsa-sha2-nistp256,ssh-rsa
(Or if you want this on all hosts: Host *)
Hope this helps.