Are you managing a couple of machines over ssh and have begun to feel frustrated about the key management? Find it tedious to distribute your public key to every machine you want to administer? Well, there is a simple solution, that does not include LDAP or some other central authentication server. A little known fact is that OpenSSH have support for both server and client certificates (not x509) since version 5.4. These can be used to set up a trusted Certificate authority on every server once and for all.

This is a very useful tool in environments where server access are harmonized (Where the same set of users should have access to all servers).

The other part is the signing of host keys. This solves the problem of having to manually check and verify the host key fingerprint every time you connect to a new server. If the server key is signed by a CA that you choose to trust you will not be asked to verify the fingerprint. If you have some configuration orchestration like Puppet you can have the puppetmaster create the host certificates on the fly.

From the release notes of OpenSSH 5.4:

* Add support for certificate authentication of users and hosts using a
   new, minimal OpenSSH certificate format (not X.509). Certificates
   contain a public key, identity information and some validity
   constraints and are signed with a standard SSH public key using
   ssh-keygen(1). CA keys may be marked as trusted in authorized_keys
   or via a TrustedUserCAKeys option in sshd_config(5) (for user
   authentication), or in known_hosts (for host authentication).

Creating CA keys
First of all I strongly recommend that you create separate CA keys for hosts and users for security reasons.

The CA keys are just regular ssh keys, you can create them like this:

$ ssh-keygen -a 256 -o -t rsa -b 4096 -f user_ca
Generating public/private rsa key pair.
Enter passphrase (empty for no passphrase): 
Enter same passphrase again: 
Your identification has been saved in user_ca.
Your public key has been saved in user_ca.pub.

$ ssh-keygen -a 256 -o -t rsa -b 4096 -f host_ca
Generating public/private rsa key pair.
Enter passphrase (empty for no passphrase): 
Enter same passphrase again: 
Your identification has been saved in host_ca.
Your public key has been saved in host_ca.pub.

Securing the private key
Since we are in the process of essentially giving one ssh key access to all of our severs we want keep the private key used for certificate signing very secure. The absolute minimum is to have the key encrypted (password protected). But other than that you should also enable KDF which you can read more about here. I also recommend that you store your keys offline and only have them mounted to a system when you use them. One way could be a encrypted partition on a USB drive, but have two of them since USB drives have a tendency to fail.

Another way to secure your keys is to have them stored on a hardware token, you can read about that here.

Singning your ssh key
First of all you need a regular ssh key which you create with ssh-keygen. Then we can sign this key and create a certificate. This is also done with ssh-keygen:

$ ssh-keygen -s /path/to/ca_key -n peter -z 1234 -V +52w1d-I key_id /path/to/user_key.pub
Signed user key user_key-cert.pub: id "peter_cert" serial 1234 for peter valid from 2016-10-09T22:23:00 to 2017-10-09T22:24:57

The file user_key-cert.pub can now be used together with your private key to access machines that accept the user_ca.pub.

To look at the newly created certificate run:

% ssh-keygen -L -f user_key-cert.pub 
wack-cert.pub:
        Type: ssh-rsa-cert-v01@openssh.com user certificate
        Public key: RSA-CERT SHA256:AtPyAu1DL5cFruTo9XnsVz7tdec7xF9SbpX8DzsQrbs
        Signing CA: RSA SHA256:8PYQAJojSknTl3BqgBkFKigmaufDhL/7d8zYUNFm7Po
        Key ID: "peter_cert"
        Serial: 1234
        Valid: from 2016-10-09T22:23:00 to 2017-10-09T22:24:57
        Principals: 
                peter
        Critical Options: (none)
        Extensions: 
                permit-X11-forwarding
                permit-agent-forwarding
                permit-port-forwarding
                permit-pty
                permit-user-rc

Singning host keys
The signing of host keys is done exactly as above, the only difference is that you add -h and the value given to -n should be the hostname.

Configure sshd
To tell sshd to accept key signed with your newly created ca you just need to upload the user_ca.pub and add one line to sshd_config. To tell the server to provide a host certificate to the client you need to add one line per key type to the configuration.

TrustedUserCAKeys /etc/ssh/user_ca.pub
HostCertificate /etc/ssh/ssh_host_rsa_key-cert.pub
HostCertificate /etc/ssh/ssh_host_ecdsa_key-cert.pub
HostCertificate /etc/ssh/ssh_host_ed25519_key-cert.pub

and restart sshd.

Configure the client to accept host certificates
To accept host certificates signed by the host_ca you need to add a line to your known_hosts file.
Its just @cert-authority * < public key >

It should look something like this:

@cert-authority * ssh-rsa AAAAB3NzaC1yc2EAAAADAQABAAACAQC3pcm4IJGw76YKZSrf7pZA6s3Hu9eRzKbyzKPgg5OkBWU9ztUz2e1bXtR0UDqQKuOUx+ZDx6wmR3rVRM/BhYt1oeAv6rhxNRW2XPiakpn3EzuEWlbp68QRY8p+k6gjy7cnvF2uyaP0R0Ov819tTMHkdS3Rn57m7pfFk+tuRKLjJnQN2g6uxT+PBJonTQr2XcS5oAzwjel1x7xLqmz0MMrE98uE0GaZHxf/hioXOHt1ihzTF+GPqZ31ZrR3GIWtFEKtvcroaiS25VIV9W39LfVh7RRZTh8oCrjcEdoeFKUKA1PpqblsJhqg1XU2/xa9CAKb6SHb7gwQ18nUaQ/Sk6qYJMgkwWUtXbwS1RIm1k5QlKk8VD4H10jyqiAUBC8SHfNxnqOwKe275AfOVc/iuh4F2NsrIuHfh8tno5LqWSP63D3gXpXXm/4j3Sop2NqNz6EIqoqj0HPIL21/SneJgWXS7xxV/ShgnLVGB0dsJf8PsCnsVt0s5thO22VvE/IVQ1KM/ac1lEafBeSZsuPiOfcIeZu9mm4DfuoyqaHmnV6yBguW6zb894IdcYXsrVnMy3Hp85gnymEZn/qfPJ+dhNbBAANgjWphz5ZaBKdrpgCESz8Ka9S6V7fXr2ikB21YiUKB7XuoPjDncOokSEHU0p5iMQjE+Le7K3nOTtokhrZjXw==

Revoking Certificates
This will be added later.