TL;DR edit your sshd_config and enable support for diffie-hellman-group-exchange-sha1 and diffie-hellman-group1-sha1 in KexAlgorithms:
KexAlgorithms [email protected],ecdh-sha2-nistp256,ecdh-sha2-nistp384,ecdh-sha2-nistp521,diffie-hellman-group-exchange-sha256,diffie-hellman-group14-sha1,diffie-hellman-group-exchange-sha1,diffie-hellman-group1-sha1
I suspect that the problem appeared after the following change in OpenSSH 6.7: “The default set of ciphers and MACs has been altered to remove unsafe algorithms.”. (see changelog). This version was released on Oct, 6, and made it on Oct, 21 to Debian testing (see Debian changelog).
OpenSSH enables only the following key exchange algorithms by default:
- [email protected]
- ecdh-sha2-nistp256
- ecdh-sha2-nistp384
- ecdh-sha2-nistp521
- diffie-hellman-group-exchange-sha256
- diffie-hellman-group14-sha1
Whereas JSch claims to support these algorithms (see under “features”) for key exchange:
- diffie-hellman-group-exchange-sha1
- diffie-hellman-group1-sha1
So indeed, they cannot agree on a common key exchange algorithm. Updating sshd_config (and restarting the SSH server) does the trick. Apparently JSch is supposed to support the “diffie-hellman-group-exchange-sha256” method since version 0.1.50 (see changelog).