[solved] Ssh: Unable to negotiate with ... port 22: no matching host key type found

General
#1

[Edited to include more detail based on content in discussion]

After upgrading to 4.4.0.58 (Vanha Rauma) when trying to ssh from phone to a host I get

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

After a while searching around I got my access working again with:

[nemo@Sailfish ~]$  ssh  -o HostKeyAlgorithms\ ssh-rsa user@host

Since

[nemo@Sailfish ~]$ ssh -Q key

lists ssh-rsa as one of the supported key types I wonder why this does not
work without the HostKeyAlgorithms option.

Note: ssh connection from phone to some other host works fine, it is just this one host for me (and before upgrading to 4.4.0.58 connections worked fine).

#2

Have you change something inside .ssh/config?

#3 
[nemo@Sailfish ~]$ cat .ssh/config 
ServerAliveInterval 150
[nemo@Sailfish ~]$

In /etc/ssh/ssh_config all lines are outcommented (or empty)

#4

Mmh, you’re using SSH from your phone to connect to another computer? Where is the SSH connexion started?

#5

Yes, “on the road” I occasionally ssh to a unix host to read email and IRC, i.e.

[nemo@Sailfish ~]$ ssh user@internet-host

(it could have been helpful if I had the [nemo@Sailfish ~]$ in first message but I am not that smart ;/)

ssh to phone works fine – using it right now for copy-pasting the “nemo@Sailfish” part

#6

No worries. Everybody do mistake :wink:

(it could have been helpful if I had the [nemo@Sailfish ~]$ in first message but I am not that smart ;/)

Isn’t actually internet-host the problem? Do you have the same problem when you connect to another host from your phone?

#7

Now that you asked – I would have guessed that ssh connection to some other machine could work (I am sure it has been tested :D)

So… I ssh’d from phone back to the machine where I connected phone (as it is easier and I can collect some more data) – and it worked… perhaps the relevant
information in ssh -vvv ... connection is:

 debug1: kex: host key algorithm: ssh-ed25519

while the host where connection fails I get

 debug1: kex: host key algorithm: (no match)

The internet-host has a bit “older” sshd installation than the one in this machine I am writing, and before upgrading to 4.4.0.58 ssh connection from phone to there worked just fine. I can understand that some less-secure algorithms can be disabled by default – but if this was the case then it would be nicer to inform the user some clearer way (in this case it is confusing, as Their offer: matches the key types mentioned what ssh -Q key (executed in phone) lists (which made me wonder is there bug in ssh client code not negotiating with matching key types or is it intentional not to negotiate by default in cases of ssh-rsa and ssh-dss key).

I just added shell script to the $HOME/ in phone to restore my accessibility.

#8

The behaviour you are seeing is simply a result of the openSSH update 8.0 → 8.8.
See https://www.openssh.com/txt/release-8.8

Potentially-incompatible changes

This release disables RSA signatures using the SHA-1 hash algorithm
by default. This change has been made as the SHA-1 hash algorithm is
cryptographically broken, and it is possible to create chosen-prefix
hash collisions for <USD$50K [1]

For most users, this change should be invisible and there is
no need to replace ssh-rsa keys. OpenSSH has supported RFC8332
RSA/SHA-256/512 signatures since release 7.2 and existing ssh-rsa keys
will automatically use the stronger algorithm where possible.

Incompatibility is more likely when connecting to older SSH
implementations that have not been upgraded or have not closely tracked
improvements in the SSH protocol. For these cases, it may be necessary
to selectively re-enable RSA/SHA1 to allow connection and/or user
authentication via the HostkeyAlgorithms and PubkeyAcceptedAlgorithms
options. For example, the following stanza in ~/.ssh/config will enable
RSA/SHA1 for host and user authentication for a single destination host:

Host old-host
    HostkeyAlgorithms +ssh-rsa

PubkeyAcceptedAlgorithms +ssh-rsa

We recommend enabling RSA/SHA1 only as a stopgap measure until legacy
implementations can be upgraded or reconfigured with another key type
(such as ECDSA or Ed25519).

[1] “SHA-1 is a Shambles: First Chosen-Prefix Collision on SHA-1 and
Application to the PGP Web of Trust” Leurent, G and Peyrin, T
(2020) https://eprint.iacr.org/2020/014.pdf

4 Likes
#9

Thank you for this information. I’ll accept the situation and will (happily) use my workaround script (instead of editing .ssh/config) for the time being.

Openssh could have been more informative about the changed defaut behavior but perhaps less people to find a workaround is more secure…

#10

Better upgrade your server instead of implementing workarounds.

#11

That is not a bad idea either…