Initial support for host certificates.

Now we offer the OpenSSH certificate key types in our KEXINIT host key
algorithm list, so that if the server has a certificate, they can send
it to us.

There's a new storage.h abstraction for representing a list of trusted
host CAs, and which ones are trusted to certify hosts for what
domains. This is stored outside the normal saved session data, because
the whole point of host certificates is to avoid per-host faffing.

Configuring this set of trusted CAs is done via a new GUI dialog box,
separate from the main PuTTY config box (because it modifies a single
set of settings across all saved sessions), which you can launch by
clicking a button in the 'Host keys' pane. The GUI is pretty crude for
the moment, and very much at a 'just about usable' stage right now. It
will want some polishing.

If we have no CA configured that matches the hostname, we don't offer
to receive certified host keys in the first place. So for existing
users who haven't set any of this up yet, nothing will immediately
change.

Currently, if we do offer to receive certified host keys and the
server presents one signed by a CA we don't trust, PuTTY will bomb out
unconditionally with an error, instead of offering a confirmation box.
That's an unfinished part which I plan to fix before this goes into a
release.

3 files changed, 199 insertions, 37 deletions

diff --git a/ssh/kex2-client.c b/ssh/kex2-client.c
index ff78840a..c01bd0fe 100644
--- a/ssh/kex2-client.c
+++ b/ssh/kex2-client.c
@@ -718,7 +718,8 @@ void ssh2kex_coroutine(struct ssh2_transport_state *s, bool *aborted)
         }
     }
 
-    s->keystr = (s->hkey ? ssh_key_cache_str(s->hkey) : NULL);
+    s->keystr = (s->hkey && !ssh_key_alg(s->hkey)->is_certificate ?
+                 ssh_key_cache_str(s->hkey) : NULL);
 #ifndef NO_GSSAPI
     if (s->gss_kex_used) {
         /*
@@ -851,19 +852,83 @@ void ssh2kex_coroutine(struct ssh2_transport_state *s, bool *aborted)
                 }
             }
 
+            ssh2_userkey uk = { .key = s->hkey, .comment = NULL };
+            char **fingerprints = ssh2_all_fingerprints(s->hkey);
+
+            FingerprintType fptype_default =
+                ssh2_pick_default_fingerprint(fingerprints);
+            ppl_logevent("Host key fingerprint is:");
+            ppl_logevent("%s", fingerprints[fptype_default]);
+
             /*
-             * Authenticate remote host: verify host key. (We've already
-             * checked the signature of the exchange hash.)
+             * Authenticate remote host: verify host key, either by
+             * certification or by the local host key cache.
+             *
+             * (We've already checked the signature of the exchange
+             * hash.)
              */
-            {
-                ssh2_userkey uk = { .key = s->hkey, .comment = NULL };
-                char *keydisp = ssh2_pubkey_openssh_str(&uk);
-                char **fingerprints = ssh2_all_fingerprints(s->hkey);
+            if (ssh_key_alg(s->hkey)->is_certificate) {
+                ssh2_free_all_fingerprints(fingerprints);
 
-                FingerprintType fptype_default =
-                    ssh2_pick_default_fingerprint(fingerprints);
-                ppl_logevent("Host key fingerprint is:");
-                ppl_logevent("%s", fingerprints[fptype_default]);
+                char *base_fp = ssh2_fingerprint(ssh_key_base_key(s->hkey),
+                                                 fptype_default);
+                ppl_logevent("Host key is a certificate, whose base key has "
+                             "fingerprint:");
+                ppl_logevent("%s", base_fp);
+                sfree(base_fp);
+
+                strbuf *id_string = strbuf_new();
+                StripCtrlChars *id_string_scc = stripctrl_new(
+                    BinarySink_UPCAST(id_string), false, L'\0');
+                ssh_key_cert_id_string(
+                    s->hkey, BinarySink_UPCAST(id_string_scc));
+                stripctrl_free(id_string_scc);
+                ppl_logevent("Certificate ID string is \"%s\"", id_string->s);
+                strbuf_free(id_string);
+
+                strbuf *ca_pub = strbuf_new();
+                ssh_key_ca_public_blob(s->hkey, BinarySink_UPCAST(ca_pub));
+                host_ca hca_search = { .ca_public_key = ca_pub };
+                host_ca *hca_found = find234(s->host_cas, &hca_search, NULL);
+
+                char *ca_fp = ssh2_fingerprint_blob(ptrlen_from_strbuf(ca_pub),
+                                                    fptype_default);
+                ppl_logevent("Fingerprint of certification authority:");
+                ppl_logevent("%s", ca_fp);
+                sfree(ca_fp);
+
+                strbuf_free(ca_pub);
+
+                strbuf *error = strbuf_new();
+                bool cert_ok = false;
+
+                if (!hca_found) {
+                    put_fmt(error, "Certification authority is not trusted");
+                } else {
+                    ppl_logevent("Certification authority matches '%s'",
+                                 hca_found->name);
+                    cert_ok = ssh_key_check_cert(
+                        s->hkey,
+                        true, /* host certificate */
+                        ptrlen_from_asciz(s->savedhost),
+                        time(NULL),
+                        BinarySink_UPCAST(error));
+                }
+                if (cert_ok) {
+                    strbuf_free(error);
+                    ppl_logevent("Accepted certificate");
+                } else {
+                    ppl_logevent("Rejected host key certificate: %s",
+                                 error->s);
+                    ssh_sw_abort(s->ppl.ssh,
+                                 "Rejected host key certificate: %s",
+                                 error->s);
+                    *aborted = true;
+                    strbuf_free(error);
+                    return;
+                }
+            } else {
+                char *keydisp = ssh2_pubkey_openssh_str(&uk);
 
                 s->spr = verify_ssh_host_key(
                     ppl_get_iseat(&s->ppl), s->conf, s->savedhost, s->savedport,
@@ -872,15 +937,15 @@ void ssh2kex_coroutine(struct ssh2_transport_state *s, bool *aborted)
 
                 ssh2_free_all_fingerprints(fingerprints);
                 sfree(keydisp);
-            }
 #ifdef FUZZING
-            s->spr = SPR_OK;
+                s->spr = SPR_OK;
 #endif
-            crMaybeWaitUntilV(s->spr.kind != SPRK_INCOMPLETE);
-            if (spr_is_abort(s->spr)) {
-                *aborted = true;
-                ssh_spr_close(s->ppl.ssh, s->spr, "host key verification");
-                return;
+                crMaybeWaitUntilV(s->spr.kind != SPRK_INCOMPLETE);
+                if (spr_is_abort(s->spr)) {
+                    *aborted = true;
+                    ssh_spr_close(s->ppl.ssh, s->spr, "host key verification");
+                    return;
+                }
             }
 
             /*
diff --git a/ssh/transport2.c b/ssh/transport2.c
index d1231069..ebb76be1 100644
--- a/ssh/transport2.c
+++ b/ssh/transport2.c
@@ -113,6 +113,7 @@ static const char *const kexlist_descr[NKEXLIST] = {
 };
 
 static int weak_algorithm_compare(void *av, void *bv);
+static int ca_blob_compare(void *av, void *bv);
 
 PacketProtocolLayer *ssh2_transport_new(
     Conf *conf, const char *host, int port, const char *fullhostname,
@@ -134,6 +135,7 @@ PacketProtocolLayer *ssh2_transport_new(
     s->server_greeting = dupstr(server_greeting);
     s->stats = stats;
     s->hostkeyblob = strbuf_new();
+    s->host_cas = newtree234(ca_blob_compare);
 
     pq_in_init(&s->pq_in_higher);
     pq_out_init(&s->pq_out_higher);
@@ -212,6 +214,12 @@ static void ssh2_transport_free(PacketProtocolLayer *ppl)
     sfree(s->keystr);
     sfree(s->hostkey_str);
     strbuf_free(s->hostkeyblob);
+    {
+        host_ca *hca;
+        while ( (hca = delpos234(s->host_cas, 0)) )
+            host_ca_free(hca);
+        freetree234(s->host_cas);
+    }
     if (s->hkey && !s->hostkeys) {
         ssh_key_free(s->hkey);
         s->hkey = NULL;
@@ -493,7 +501,7 @@ static void ssh2_write_kexinit_lists(
     struct kexinit_algorithm_list kexlists[NKEXLIST],
     Conf *conf, const SshServerConfig *ssc, int remote_bugs,
     const char *hk_host, int hk_port, const ssh_keyalg *hk_prev,
-    ssh_transient_hostkey_cache *thc,
+    ssh_transient_hostkey_cache *thc, tree234 *host_cas,
     ssh_key *const *our_hostkeys, int our_nhostkeys,
     bool first_time, bool can_gssapi_keyex, bool transient_hostkey_mode)
 {
@@ -672,33 +680,98 @@ static void ssh2_write_kexinit_lists(
          * they surely _do_ want to be alerted that a server
          * they're actually connecting to is using it.
          */
+
+        bool accept_certs = false;
+        {
+            host_ca_enum *handle = enum_host_ca_start();
+            if (handle) {
+                strbuf *name = strbuf_new();
+                while (strbuf_clear(name), enum_host_ca_next(handle, name)) {
+                    host_ca *hca = host_ca_load(name->s);
+                    if (!hca)
+                        continue;
+
+                    bool match = false;
+                    for (size_t i = 0, e = hca->n_hostname_wildcards;
+                         i < e; i++) {
+                        if (wc_match(hca->hostname_wildcards[i], hk_host)) {
+                            match = true;
+                            break;
+                        }
+                    }
+
+                    if (match && hca->ca_public_key) {
+                        accept_certs = true;
+                        add234(host_cas, hca);
+                    } else {
+                        host_ca_free(hca);
+                    }
+                }
+                enum_host_ca_finish(handle);
+                strbuf_free(name);
+            }
+        }
+
+        if (accept_certs) {
+            /* Add all the certificate algorithms first, in preference order */
+            warn = false;
+            for (i = 0; i < n_preferred_hk; i++) {
+                if (preferred_hk[i] == HK_WARN)
+                    warn = true;
+                for (j = 0; j < lenof(ssh2_hostkey_algs); j++) {
+                    const struct ssh_signkey_with_user_pref_id *a =
+                        &ssh2_hostkey_algs[j];
+                    if (!a->alg->is_certificate)
+                        continue;
+                    if (a->id != preferred_hk[i])
+                        continue;
+                    alg = ssh2_kexinit_addalg(&kexlists[KEXLIST_HOSTKEY],
+                                              a->alg->ssh_id);
+                    alg->u.hk.hostkey = a->alg;
+                    alg->u.hk.warn = warn;
+                }
+            }
+        }
+
+        /* Next, add uncertified algorithms we already know a key for
+         * (unless configured not to do that) */
         warn = false;
         for (i = 0; i < n_preferred_hk; i++) {
             if (preferred_hk[i] == HK_WARN)
                 warn = true;
             for (j = 0; j < lenof(ssh2_hostkey_algs); j++) {
-                if (ssh2_hostkey_algs[j].id != preferred_hk[i])
+                const struct ssh_signkey_with_user_pref_id *a =
+                    &ssh2_hostkey_algs[j];
+                if (a->alg->is_certificate || !a->alg->cache_id)
+                    continue;
+                if (a->id != preferred_hk[i])
                     continue;
                 if (conf_get_bool(conf, CONF_ssh_prefer_known_hostkeys) &&
                     have_ssh_host_key(hk_host, hk_port,
-                                      ssh2_hostkey_algs[j].alg->cache_id)) {
+                                      a->alg->cache_id)) {
                     alg = ssh2_kexinit_addalg(&kexlists[KEXLIST_HOSTKEY],
-                                              ssh2_hostkey_algs[j].alg->ssh_id);
-                    alg->u.hk.hostkey = ssh2_hostkey_algs[j].alg;
+                                              a->alg->ssh_id);
+                    alg->u.hk.hostkey = a->alg;
                     alg->u.hk.warn = warn;
                 }
             }
         }
+
+        /* And finally, everything else */
         warn = false;
         for (i = 0; i < n_preferred_hk; i++) {
             if (preferred_hk[i] == HK_WARN)
                 warn = true;
             for (j = 0; j < lenof(ssh2_hostkey_algs); j++) {
-                if (ssh2_hostkey_algs[j].id != preferred_hk[i])
+                const struct ssh_signkey_with_user_pref_id *a =
+                    &ssh2_hostkey_algs[j];
+                if (a->alg->is_certificate)
+                    continue;
+                if (a->id != preferred_hk[i])
                     continue;
                 alg = ssh2_kexinit_addalg(&kexlists[KEXLIST_HOSTKEY],
-                                          ssh2_hostkey_algs[j].alg->ssh_id);
-                alg->u.hk.hostkey = ssh2_hostkey_algs[j].alg;
+                                          a->alg->ssh_id);
+                alg->u.hk.hostkey = a->alg;
                 alg->u.hk.warn = warn;
             }
         }
@@ -1201,7 +1274,7 @@ static void ssh2_transport_process_queue(PacketProtocolLayer *ppl)
     ssh2_write_kexinit_lists(
         BinarySink_UPCAST(s->outgoing_kexinit), s->kexlists,
         s->conf, s->ssc, s->ppl.remote_bugs,
-        s->savedhost, s->savedport, s->hostkey_alg, s->thc,
+        s->savedhost, s->savedport, s->hostkey_alg, s->thc, s->host_cas,
         s->hostkeys, s->nhostkeys,
         !s->got_session_id, s->can_gssapi_keyex,
         s->gss_kex_used && !s->need_gss_transient_hostkey);
@@ -1271,6 +1344,7 @@ static void ssh2_transport_process_queue(PacketProtocolLayer *ppl)
         for (i = 0; i < nhk; i++) {
             j = hks[i];
             if (ssh2_hostkey_algs[j].alg != s->hostkey_alg &&
+                ssh2_hostkey_algs[j].alg->cache_id &&
                 !have_ssh_host_key(s->savedhost, s->savedport,
                                    ssh2_hostkey_algs[j].alg->cache_id)) {
                 s->uncert_hostkeys[s->n_uncert_hostkeys++] = j;
@@ -2154,6 +2228,18 @@ static int weak_algorithm_compare(void *av, void *bv)
     return a < b ? -1 : a > b ? +1 : 0;
 }
 
+static int ca_blob_compare(void *av, void *bv)
+{
+    host_ca *a = (host_ca *)av, *b = (host_ca *)bv;
+    strbuf *apk = a->ca_public_key, *bpk = b->ca_public_key;
+    /* Ordering by public key is arbitrary here, so do whatever is easiest */
+    if (apk->len < bpk->len)
+        return -1;
+    if (apk->len > bpk->len)
+        return +1;
+    return memcmp(apk->u, bpk->u, apk->len);
+}
+
 /*
  * Wrapper on seat_confirm_weak_crypto_primitive(), which uses the
  * tree234 s->weak_algorithms_consented_to to ensure we ask at most
diff --git a/ssh/transport2.h b/ssh/transport2.h
index dc62f71f..72cd5fba 100644
--- a/ssh/transport2.h
+++ b/ssh/transport2.h
@@ -49,16 +49,25 @@ struct kexinit_algorithm_list {
     size_t nalgs, algsize;
 };
 
-#define HOSTKEY_ALGORITHMS(X)                   \
-    X(HK_ED25519, ssh_ecdsa_ed25519)            \
-    X(HK_ED448, ssh_ecdsa_ed448)                \
-    X(HK_ECDSA, ssh_ecdsa_nistp256)             \
-    X(HK_ECDSA, ssh_ecdsa_nistp384)             \
-    X(HK_ECDSA, ssh_ecdsa_nistp521)             \
-    X(HK_DSA, ssh_dsa)                          \
-    X(HK_RSA, ssh_rsa_sha512)                   \
-    X(HK_RSA, ssh_rsa_sha256)                   \
-    X(HK_RSA, ssh_rsa)                          \
+#define HOSTKEY_ALGORITHMS(X)                                   \
+    X(HK_ED25519, ssh_ecdsa_ed25519)                            \
+    X(HK_ED448, ssh_ecdsa_ed448)                                \
+    X(HK_ECDSA, ssh_ecdsa_nistp256)                             \
+    X(HK_ECDSA, ssh_ecdsa_nistp384)                             \
+    X(HK_ECDSA, ssh_ecdsa_nistp521)                             \
+    X(HK_DSA, ssh_dsa)                                          \
+    X(HK_RSA, ssh_rsa_sha512)                                   \
+    X(HK_RSA, ssh_rsa_sha256)                                   \
+    X(HK_RSA, ssh_rsa)                                          \
+    X(HK_ED25519, opensshcert_ssh_ecdsa_ed25519)                \
+    /* OpenSSH defines no certified version of Ed448 */         \
+    X(HK_ECDSA, opensshcert_ssh_ecdsa_nistp256)                 \
+    X(HK_ECDSA, opensshcert_ssh_ecdsa_nistp384)                 \
+    X(HK_ECDSA, opensshcert_ssh_ecdsa_nistp521)                 \
+    X(HK_DSA, opensshcert_ssh_dsa)                              \
+    X(HK_RSA, opensshcert_ssh_rsa_sha512)                       \
+    X(HK_RSA, opensshcert_ssh_rsa_sha256)                       \
+    X(HK_RSA, opensshcert_ssh_rsa)                              \
     /* end of list */
 #define COUNT_HOSTKEY_ALGORITHM(type, alg) +1
 #define N_HOSTKEY_ALGORITHMS (0 HOSTKEY_ALGORITHMS(COUNT_HOSTKEY_ALGORITHM))
@@ -168,6 +177,8 @@ struct ssh2_transport_state {
 
     bool gss_kex_used;
 
+    tree234 *host_cas;
+
     int nbits, pbits;
     bool warn_kex, warn_hk, warn_cscipher, warn_sccipher;
     mp_int *p, *g, *e, *f;