We were also hit by this problem in our test suite where we're testing against an SshServer configured with a SimpleGeneratorHostKeyProvider using the default DSA algorithm. As a work-around, we've now just switched to the RSA algorithm: SshServer sshd = ...; sshd.setKeyPairProvider(new SimpleGeneratorHostKeyProvider("target/hostkey.ser", "RSA)); ... sshd.start();