We don't currently handle OpenSSH certificates properly (bug 7641). Before bug 7536 this wasn't particularly noticable as we just treated every key type as a blob and simply stored that.
However certificates behave slightly different, and one difference is that they will not be enumerated by the server when getting all host keys. So we get in to this bad sequence:
1. client connects to server
2. unknown certificate host key is presented to the user
3. user approves host key and it is stored to disk
4. a list of all (normal) host keys is received from the server
5. the just stored certificate host key is removed from disk since it wasn't in the list
End result is that the users end up having to approve the key over and over again.
Bug 7461 is about handling certificates properly. This bug is about avoiding the above extreme scenario.
ssh has the argument -HostKeyAlgorithms to control which algorithms to support. We could likely use that and specify "-*-cert-*" to get rid of all certificate based algorithms.
However that likely prevents us from implementing bug 7623, so I'd rather avoid doing that.
We could change ssh and remove these certificate algorithms from the default list, which should be more robust. We could also try to piggyback on ssh's mechanism to downgrade a certificate host key to a plain host key. Will have to experiment to see which is easier.
To test things simply generate a CA signing key:
> ssh-keygen -N '' -t ed25519 -f /etc/ssh/host_ca_key
Then sign the existing host key:
> ssh-keygen -h -s /etc/ssh/host_ca_key -I test -n lab-189,lab-189.lkpg.cendio.se /etc/ssh/ssh_host_ed25519_key
Then configure sshd to use the new certificate:
> HostCertificate /etc/ssh/ssh_host_ed25519_key-cert.pub
Works better now. Tester should verify proper behaviour on systems with plain host keys and those with certificate host keys.
Tested on Fedora 32 and can confirm that the user was warned of a "possible security breach" and had to reapprove the key every login when using certificate host keys. There was also this log warning present:
> Unexpected host key received from server. Possible attack in progress.
With the fix, logging in with certificate host keys now only warns the user on the first login, and later logins are allowed without any warnings. The log looks good, and the warning on the first login is logged.
Logging in with plain host keys works as before.