SSH from RHEL 9 to RHEL 6 systems does not work (two solutions!)

August 8, 2023
If you try to ssh between an old server and a new server, you may receive the error "no hostkey alg" or "no matching host key type found. Their offer: ssh-rsa,ssh-dss". If upgrading the old server is not an option, don't despair. You could reduce the level of security on the new server, but this is not desirable for obvious reasons. If the ECDSA algorithm is supported on the old server, you may be able to solve the problem by creating an ECDSA host key. First, inspect /etc/ssh/ and verify that ssh_host_ecdsa_key does not already exist. If it does not, create it:
sudo ssh-keygen -q -N "" -t ecdsa -b 521 -f /etc/ssh/ssh_host_ecdsa_key
You can omit "-b 521" if you prefer to use the default key size. Note that 521 is not a mistake and should not be 512. So that newer servers can SSH to the older server, edit /etc/ssh/sshd_config and add the following:
HostKey /etc/ssh/ssh_host_ecdsa_key
So that the older server can SSH to newer servers, edit /etc/ssh/ssh_config and add the following (modifying the existing HostKeyAlgorithms line if it already exists):
HostKeyAlgorithms ecdsa-sha2-nistp256-cert-v01@openssh.com,ecdsa-sha2-nistp384-cert-v01@openssh.com,ecdsa-sha2-nistp521-cert-v01@openssh.com,ssh-rsa-cert-v01@openssh.com,ssh-dss-cert-v01@openssh.com,ssh-rsa-cert-v00@openssh.com,ssh-dss-cert-v00@openssh.com,ecdsa-sha2-nistp256,ecdsa-sha2-nistp384,ecdsa-sha2-nistp521,ssh-rsa,ssh-dss
Restart the SSH service using "sudo service sshd restart" (adjust appropriately for your flavour of Linux). If you have previously used update-crypto-policies or HostKeyAlgorithms as a workaround, and you remove that workaround, when you attempt to use ssh again you will receive a warning about a changed host key. In that case, edit ~/.ssh/known_hosts and remove the old key. If you do not have root access to the old server to generate a new host key, Richard WM Jones wrote an article detailing the steps required to set security policy per remote host on an RHEL 9 server.