[ssh] Unable to negotiate with XX.XXX.XX.XX: no matching host key type found. Their offer: ssh-dss

I am trying to create a git repository on my web host and clone it on my computer. Here's what I did:

1. I created a repository on the remote server.
2. I generated a key pair: ssh-keygen -t dsa.
3. I added my key to ssh-agent.
4. I copied to the server public key in ~/.ssh.

And then, after an attempt to run the command git clone ssh://user@host/path-to-repository, I get an error:

Unable to negotiate with XX.XXX.XX.XX: no matching host key type found. Their offer: ssh-dss
fatal: Could not read from remote repository.
Please make sure you have the correct access rights and the repository exists.

What does that mean?

How would one specify multiple algorithms? I ask because git just updated on my work laptop, (Windows 10, using the official Git for Windows build,) and I got this error when I tried to push a project branch to my Azure DevOps remote. I tried to push --set-upstream and got this:

Unable to negotiate with 20.44.80.98 port 22: no matching key exchange method found. Their offer: diffie-hellman-group1-sha1,diffie-hellman-group14-sha1
fatal: Could not read from remote repository.

Please make sure you have the correct access rights
and the repository exists.

So how would one implement the suggestions above allowing for both of those? (As a quick get-it-done, I used @golvok's solution with group14 and it worked, but I really don't know if 1 or 14 is better, etc.)

I want to collaborate a little with the solution for the server side. So, the server is saying it does not support DSA, this is because the openssh client does not activate it by default:

OpenSSH 7.0 and greater similarly disable the ssh-dss (DSA) public key algorithm. It too is weak and we recommend against its use.

So, to fix this this in the server side I should activate other Key algorithms like RSA o ECDSA. I just had this problem with a server in a lan. I suggest the following:

Update the openssh:

yum update openssh-server

Merge new configurations in the sshd_config if there is a sshd_config.rpmnew.

Verify there are hosts keys at /etc/ssh/. If not generate new ones, see man ssh-keygen.

$ ll /etc/ssh/
total 580
-rw-r--r--. 1 root root     553185 Mar  3  2017 moduli
-rw-r--r--. 1 root root       1874 Mar  3  2017 ssh_config
drwxr-xr-x. 2 root root       4096 Apr 17 17:56 ssh_config.d
-rw-------. 1 root root       3887 Mar  3  2017 sshd_config
-rw-r-----. 1 root ssh_keys    227 Aug 30 15:33 ssh_host_ecdsa_key
-rw-r--r--. 1 root root        162 Aug 30 15:33 ssh_host_ecdsa_key.pub
-rw-r-----. 1 root ssh_keys    387 Aug 30 15:33 ssh_host_ed25519_key
-rw-r--r--. 1 root root         82 Aug 30 15:33 ssh_host_ed25519_key.pub
-rw-r-----. 1 root ssh_keys   1675 Aug 30 15:33 ssh_host_rsa_key
-rw-r--r--. 1 root root        382 Aug 30 15:33 ssh_host_rsa_key.pub

Verify in the /etc/ssh/sshd_config the HostKey configuration. It should allow the configuration of RSA and ECDSA. (If all of them are commented by default it will allow too the RSA, see in man sshd_config the part of HostKey).

# HostKey for protocol version 1
#HostKey /etc/ssh/ssh_host_key
# HostKeys for protocol version 2
HostKey /etc/ssh/ssh_host_rsa_key
#HostKey /etc/ssh/ssh_host_dsa_key
HostKey /etc/ssh/ssh_host_ecdsa_key
HostKey /etc/ssh/ssh_host_ed25519_key

For the client side, create a key for ssh (not a DSA like in the question) by just doing this:

ssh-keygen

After this, because there are more options than ssh-dss(DSA) the client openssh (>=v7) should connect with RSA or better algorithm.

Here another good article.

This is my first question answered, I welcome suggestions :D .

You can also add -oHostKeyAlgorithms=+ssh-dss in your ssh line:

ssh -oHostKeyAlgorithms=+ssh-dss user@host

You either follow above approach or this one

Create the config file in the .ssh directory and add these line.

host xxx.xxx
 Hostname xxx.xxx
 IdentityFile ~/.ssh/id_rsa
 User xxx
 KexAlgorithms +diffie-hellman-group1-sha1

For me this worked: (added into .ssh\config)

Host *
HostkeyAlgorithms +ssh-dss
PubkeyAcceptedKeyTypes +ssh-dss

If you're like me, and would rather not make this security hole system or user-wide, then you can add a config option to any git repos that need this by running this command in those repos. (note only works with git version >= 2.10, released 2016-09-04)

git config core.sshCommand 'ssh -oHostKeyAlgorithms=+ssh-dss'

This only works after the repo is setup however. If you're not comfortable adding a remote manually (and just want to clone) then you can run the clone like this:

GIT_SSH_COMMAND='ssh -oHostKeyAlgorithms=+ssh-dss' git clone ssh://user@host/path-to-repository

then run the first command to make it permanent.

If you don't have the latest, and still would like to keep the hole as local as possible I recommend putting

export GIT_SSH_COMMAND='ssh -oHostKeyAlgorithms=+ssh-dss'

in a file somewhere, say git_ssh_allow_dsa_keys.sh, and sourceing it when needed.