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.

Solution

(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 :-)

Comments

[dave_thompson_085]

With HostKeyAlgorithms +ssh-rsa it asks for password -- so it accepted the hostkey and your problem is user authentication. OpenSSH 8.8 by default only uses for an RSA key the newer RSA-SHA2 algorithms, which 5.5 doesn't implement. Also add PubkeyAcceptedAlgorithms +ssh-rsa.

[Brethlosze]

It worked. Thanks. Please move that for marking an answer, unless suggest to delete the question.