How does OpenSSH decide which host key to use?

Solution 1:

The order is selected by the client using the HostKeyAlgorithms config option. The default on my system (according to the manpage) is:

1. [email protected]
2. [email protected]
3. [email protected]
4. [email protected]
5. [email protected]
6. [email protected]
7. [email protected]
8. [email protected]
9. ecdsa-sha2-nistp256
10. ecdsa-sha2-nistp384
11. ecdsa-sha2-nistp521
12. ssh-ed25519
13. ssh-rsa
14. ssh-dss

To override this, do something like:

ssh -oHostKeyAlgorithms=ssh-ed25519 [email protected]

Solution 2:

And more importantly, why has OpenSSH decided give the ECDSA algorithm first priority?

ECDSA was introduced into openssh with version 5.7, you may find the Release notes here. In particular, it is stated:

Implement Elliptic Curve Cryptography modes for key exchange (ECDH) and host/user keys (ECDSA) as specified by RFC5656. ECDH and ECDSA offer better performance than plain DH and DSA at the same equivalent symmetric key length, as well as much shorter keys.

.......

Certificate host and user keys using the new ECDSA key types are supported - an ECDSA key may be certified, and an ECDSA key may act as a CA to sign certificates.

ECDH in a 256 bit curve field is the preferred key agreement algorithm when both the client and server support it. ECDSA host keys are preferred when learning a host's keys for the first time, or can be learned using ssh-keyscan(1).

Also, RFC 5656 states:

Many estimates consider that 2^80-2^90 operations are beyond feasible, so that would suggest using elliptic curves of at least 160-180 bits. The REQUIRED curves in this document are 256-, 384-, and 521-bit curves; implementations SHOULD NOT use curves smaller than 160 bits