Now that I've upgraded to Fedora 21 on my main machines and actually have it available, I've decided to start shifting my OpenSSH usage towards considering ed25519 my primary and preferred public key authentication system (out of all of the ones that OpenSSH offers). Moving towards Ed25519 for my own keypairs was and is simple; I generated some new keypairs (one for each master machine), loaded them into ssh-agent first, and started adding them to authorized_keys on machines that have a modern enough version of OpenSSH. I expect to be using RSA keys for a long time given that eg CentOS 7 is not Ed25519 enabled, but at least this transition is basically automatic from now onwards.

(Well, I can add my Ed25519 keys to authorized_keys pretty much anywhere but they won't do me any good except on modern machines.)

But I also want to use Ed25519 host keys where machines have them available, and this turns out to be more tricky than I was expecting (at least on the version of OpenSSH on Fedora 21, which is OpenSSH 6.6.1p1). If you read the ssh_config manpage you'll soon run across a description of the HostKeyAlgorithms option, which to quote the manual 'specifies the protocol version 2 host key algorithms that the client wants to use in order of preference'. This sounds like just the thing; I could specify it explicitly in .ssh/config with the Ed25519 options first and everything would work right.

Well, sadly, no. The manual also claims:

If hostkeys are known for the destination host then [the HostKeyAlgorithms] default is modified to prefer their algorithms.

In other words: if you say that you prefer Ed25519 keys, the host has both an Ed25519 key and an RSA key available, and you already have the host's RSA key in .ssh/known_hosts, ssh should authenticate the host with the existing RSA key.

This appears to be what they call 'inoperative' if you specify an explicit HostKeyAlgorithms setting, even if this setting just shuffles the priority order. If you put the Ed25519 options first and you know an RSA key for a host that also offers Ed25519, ssh complains about a host key mismatch between the Ed25519 key being offered and the RSA key you know and does various things in reaction (including turning off X forwarding, which is fatal in my environment at work).

As far as I can tell, the only way to get this to really work is to not set HostKeyAlgorithms. Instead, you have to manually gather Ed25519 keys for anything that has them (perhaps using 'ssh-keyscan -t ed25519'), add them to your known_hosts, and purge any other host key entries for those hosts. This works right in that anything with a known Ed25519 key will be verified against the key, but it won't remember Ed25519 keys for new hosts; instead you'll probably wind up with ECDSA keys for them. You'll want to periodically look for signs that new hosts support Ed25519 and upgrade your known host keys for them.

(Future versions of OpenSSH will apparently support recording multiple host keys for a remote host at once as part of host key rotation. That won't be on all of our Linux machines any time soon, much less other things in the corner.)

I'd say that hopefully this issue is or will be fixed in future versions of OpenSSH, but I'm honestly a little worried that people will say it's actually working as intended (and at most fix the manual page). Even if they do fix it I don't expect to see the fix appearing in Fedora any time soon, given the usual release process and delays.

(It's possible that setting HostKeyAlgorithms in /etc/ssh/ssh_config will work and that only .ssh/config is special here, but I haven't tested this, it's not always feasible, and I'm not holding my breath.)