SSH No Matching Host Key Type Found

Question

I have two servers,

• S1: My machine, Windows 8, OpenSSH 8.8p1, OpenSSL 1.1.11 2021-08-24,
• S2: A Remote Server, Linux, Open SSH 5.3p1, OpenSSL 1.0.1e-fips 2013-02-11.

The message I have trying to investigate how to solve is

Unable to negotiate with xxx.xxx.xxx.xxx port xxxxx: no matching host key found, Their offer ssh-rsa,ssh-dss

• Both S1 and S2 ssh users keys are RSA-2048 (~372 chars),
• Both S1 and S2 etc/config files have all their options commented by default,
• Both S1 and S2 ssh users have their config and authorized_keys files identical, including both public keys and aliases,
• S2 is a Remote, Embedded Linux, not under my control, and which I cannot update. SSH cannot be updated, and is restricted to specific IPs.

Question is, should I change all keys to, i.e. ECDSA-256 for this to be solved? Is there another configuration not mentioned here I am missing?

When I add the option HostkeyAlgorithms +ssh-rsa, suggested almost everywhere, SSH ask for password instead of checking the keys.

Answer 1

(expanding slightly)

You've actually fixed the problem in your title; with HostkeyAlgorithms +ssh-rsa it prompts for password, which means it accepted the hostkey. (You could even have told 8.8 to accept ssh-dss -- it's still implemented, although the OpenSSH developers recommend pretty strongly against it.)

The actual problem in your body is now user authentication, because OpenSSH 8.8 by default only uses for an RSA key the newer, stronger rsa-sha2-* algorithms, and 5.3 was about 8 years before those were defined. Add PubkeyAcceptedAlgorithms +ssh-rsa to get 8.8 to use the old, weak algorithm 5.3 can handle.

And if possible make snide remarks to whoever is responsible for that ancient system you're connecting to :-)

Answer 2

I have used this one, worked me best in my latest Mac OS X ( 13. 0 )

just do this :

nano ~/.ssh/config

and put this text:

Host *
HostKeyAlgorithms +ssh-rsa
PubkeyAcceptedKeyTypes +ssh-rsa

and control & x then select yes to save your edit.

Answer 3

In your ~/.ssh/config file:

Host whatever_alias
    Hostname real_hostname_to_your_server
    User your_remote_user
    HostKeyAlgorithms +ssh-rsa
    PubkeyAcceptedKeyTypes +ssh-rsa