HOWTO authenticate ssh server through certificates

In August 2010, OpenSSH 5.6 added support for certificate authentication (release notes), unfortunately, no documentation really exists at the moment (you are on your own with sshd_config(1), ssh-keygen(1) and ssh_config(1), good luck with that).  This is a surprising because this feature is awesome for system administrators, even for a small deployment.

Certificates allow you to sign user or host keys. In other words:

• Thanks to a unique file (CA certificate) on the server, it can accept any (signed) user keys transparently
• If every servers' host keys are signed, clients only need to carry the CA to authenticate every servers of your network, which means no more "The authenticity of host foobar can't be established. Fingerprint is..." message

Here is the HOWTO for the latter case.

Geek summary: Sign SSHd host key

$ ssh-keygen -f ~/.ssh/cert_signer
$ scp foobar.example.org:/etc/ssh/ssh_host_rsa_key.pub foobar.pub
$ ssh-keygen -h                             \ # sign host key
             -s ~/.ssh/cert_signer          \ # CA key
             -I foobar                      \ # Key identifier
             -V +1w                         \ # Valid only 1 week
             -n foobar,foobar.example.org   \ # Valid hostnames
             foobar.pub                       # Host pubkey file
$ scp foobar-cert.pub foobar.example.org:/etc/ssh/ssh_host_rsa_key-cert.pub

On foobar.example.org, add "HostCertificate /etc/ssh/ssh_host_rsa_key-cert.pub" in sshd_config and reload sshd. Now, configure the ssh client to use this authority:

$ (  echo -n '@cert-authority * '; \
     cat ~/.ssh/cert_signer.pub ) > ~/.ssh/known_hosts_cert
$ ssh -oUserKnownHostsFile=~/.ssh/known_hosts_cert foobar.example.org

At this point, you can connect to every servers without any annoying messages. You don't even have to care when the server is replaced without conserving its old ssh keys.