Veeam unable to connect to a client machine. Unable to negotiate with a client.

When Veeam connects to a Linux machine, its use Diffie-Helman key exchange capabilities for successful secure connections and to reduce the possibility that a password will not be intercepted when authenticating to the storage.

If the client and server are unable to agree on a mutual set of parameters then the connection will fail. OpenSSH (7.0 and greater) will produce an error message like this:

sshd[11344]: fatal: Unable to negotiate with XXX.XXX.XXX.XXX port 36929: no matching key exchange method found. Their offer: diffie-hellman-group1-sha1 [preauth]

In this case, the client and server were unable to agree on the key exchange algorithm. OpenSSH supports this method, but does not enable it by default because is weak and within theoretical range of the so-called Logjam attack. OpenSSH only disables algorithms that we actively recommend against using because they are known to be weak. In some cases, this might not be immediately possible so you may need to temporarily re-enable the weak algorithms to retain access.
Query SSH for the supported ciphers, key exchange algorithms and keyed-hash message authentication codes using the following command: “sshd -T | grep kexa

server:~ # sshd -T | grep kexa
kexalgorithms curve25519-sha256@libssh.org,ecdh-sha2-nistp256,ecdh-sha2-nistp384,ecdh-sha2-nistp521,diffie-hellman-group-exchange-sha256,diffie-hellman-group14-sha1
slerver:~ #

And if there is no “diffie-hellman-group1-sha1” just add these:

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

to your /etc/ssh/sshd_config file, and restart SSH.

server:~ # sshd -T | grep kexa
kexalgorithms curve25519-sha256@libssh.org,ecdh-sha2-nistp256,ecdh-sha2-nistp384,ecdh-sha2-nistp521,diffie-hellman-group-exchange-sha256,diffie-hellman-group14-sha1,diffie-hellman-group1-sha1
slerver:~ #

As you can see the only new added algorithm is called “diffie-hellman-group1-sha1”.