no matching host key type found. Their offer: ssh-rsa,ssh-dss
 

After I upgraded to openssh-8.8p1-x86_64-1 I began to get when I tried to connect to a domain. Adding to /etc/ssh_config cleared the error

I know man been a nightmare yesterday for me. Glad you posted this. Still Has Atlasian and Bitbucket screwed up.
That's on there end.

I had to fix a few machines myself. But it's probably better to take this breaking change now, before the release, than to have a new openssh release afterwards that fixes CVEs and end up also pushing this change into /patches as a surprise.

Upstream has been warning about this for quite some time. Hopefully the now-broken sites will fix their issues quickly.

I had to add this for some of my connections as well. Thanks!

Note that the method described above is not a fix but an unsafe work-around to buy you enough time to log in and really fix the problem correctly.

The correct solution is to upgrade OpenSSH on the server, using backports if necessary. Those old algorithms have been removed with plenty of advanced warning so that should have been done long ago. They have been considered unsafe for a long time.

A small contribution,

after adding ssh-rsa to my .ssh/config file, I got
Fixed by adding PubkeyAcceptedKeyTypes to my .ssh/config
At least I regain access to change to a more secure algorithm.

thank you
 

THANK YOU!

Solution that worked for me
 

At first I was getting:

Unable to negotiate with x.x.x.x port 22: no matching key exchange method found. Their offer: diffie-hellman-group-exchange-sha1,diffie-hellman-group14-sha1

So I added:

KexAlgorithms +diffie-hellman-group1-sha1,curve25519-sha256@libssh.org,ecdh-sha2-nistp256,ecdh-sha2-nistp384,ecdh-sha2-nistp521,diffie-hellman-group-exchange-sha256,diffie-hellman-group14-sha1
Ciphers +aes256-cbc

to my ~/.ssh/config

Then I was getting:

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

So I added:

HostKeyAlgorithms +ssh-rsa,ssh-dss

Problem resolved!