- OpenBSD CVS Sync

   - djm@cvs.openbsd.org 2010/02/26 20:29:54
     [PROTOCOL PROTOCOL.agent PROTOCOL.certkeys addrmatch.c auth-options.c]
     [auth-options.h auth.h auth2-pubkey.c authfd.c dns.c dns.h hostfile.c]
     [hostfile.h kex.h kexdhs.c kexgexs.c key.c key.h match.h monitor.c]
     [myproposal.h servconf.c servconf.h ssh-add.c ssh-agent.c ssh-dss.c]
     [ssh-keygen.1 ssh-keygen.c ssh-rsa.c ssh.1 ssh.c ssh2.h sshconnect.c]
     [sshconnect2.c sshd.8 sshd.c sshd_config.5]
     Add support for certificate key types for users and hosts.

     OpenSSH certificate key types are not X.509 certificates, but a much
     simpler format that encodes a public key, identity information and
     some validity constraints and signs it with a CA key. CA keys are
     regular SSH keys. This certificate style avoids the attack surface
     of X.509 certificates and is very easy to deploy.

     Certified host keys allow automatic acceptance of new host keys
     when a CA certificate is marked as sh/known_hosts.
     see VERIFYING HOST KEYS in ssh(1) for details.

     Certified user keys allow authentication of users when the signing
     CA key is marked as trusted in authorized_keys. See "AUTHORIZED_KEYS
     FILE FORMAT" in sshd(8) for details.

     Certificates are minted using ssh-keygen(1), documentation is in
     the "CERTIFICATES" section of that manpage.

     Documentation on the format of certificates is in the file
     PROTOCOL.certkeys

     feedback and ok markus@

1 files changed, 561 insertions, 34 deletions

diff --git a/key.c b/key.c
index 5aea416b..387190b5 100644
--- a/key.c
+++ b/key.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: key.c,v 1.82 2010/01/13 01:10:56 dtucker Exp $ */
+/* $OpenBSD: key.c,v 1.83 2010/02/26 20:29:54 djm Exp $ */
 /*
  * read_bignum():
  * Copyright (c) 1995 Tatu Ylonen <ylo@cs.hut.fi>, Espoo, Finland
@@ -52,6 +52,21 @@
 #include "uuencode.h"
 #include "buffer.h"
 #include "log.h"
+#include "ssh2.h"
+
+static struct KeyCert *
+cert_new(void)
+{
+	struct KeyCert *cert;
+
+	cert = xcalloc(1, sizeof(*cert));
+	buffer_init(&cert->certblob);
+	buffer_init(&cert->constraints);
+	cert->key_id = NULL;
+	cert->principals = NULL;
+	cert->signature_key = NULL;
+	return cert;
+}
 
 Key *
 key_new(int type)
@@ -63,9 +78,11 @@ key_new(int type)
 	k->type = type;
 	k->dsa = NULL;
 	k->rsa = NULL;
+	k->cert = NULL;
 	switch (k->type) {
 	case KEY_RSA1:
 	case KEY_RSA:
+	case KEY_RSA_CERT:
 		if ((rsa = RSA_new()) == NULL)
 			fatal("key_new: RSA_new failed");
 		if ((rsa->n = BN_new()) == NULL)
@@ -75,6 +92,7 @@ key_new(int type)
 		k->rsa = rsa;
 		break;
 	case KEY_DSA:
+	case KEY_DSA_CERT:
 		if ((dsa = DSA_new()) == NULL)
 			fatal("key_new: DSA_new failed");
 		if ((dsa->p = BN_new()) == NULL)
@@ -93,16 +111,20 @@ key_new(int type)
 		fatal("key_new: bad key type %d", k->type);
 		break;
 	}
+
+	if (key_is_cert(k))
+		k->cert = cert_new();
+
 	return k;
 }
 
-Key *
-key_new_private(int type)
+void
+key_add_private(Key *k)
 {
-	Key *k = key_new(type);
 	switch (k->type) {
 	case KEY_RSA1:
 	case KEY_RSA:
+	case KEY_RSA_CERT:
 		if ((k->rsa->d = BN_new()) == NULL)
 			fatal("key_new_private: BN_new failed");
 		if ((k->rsa->iqmp = BN_new()) == NULL)
@@ -117,6 +139,7 @@ key_new_private(int type)
 			fatal("key_new_private: BN_new failed");
 		break;
 	case KEY_DSA:
+	case KEY_DSA_CERT:
 		if ((k->dsa->priv_key = BN_new()) == NULL)
 			fatal("key_new_private: BN_new failed");
 		break;
@@ -125,9 +148,34 @@ key_new_private(int type)
 	default:
 		break;
 	}
+}
+
+Key *
+key_new_private(int type)
+{
+	Key *k = key_new(type);
+
+	key_add_private(k);
 	return k;
 }
 
+static void
+cert_free(struct KeyCert *cert)
+{
+	u_int i;
+
+	buffer_free(&cert->certblob);
+	buffer_free(&cert->constraints);
+	if (cert->key_id != NULL)
+		xfree(cert->key_id);
+	for (i = 0; i < cert->nprincipals; i++)
+		xfree(cert->principals[i]);
+	if (cert->principals != NULL)
+		xfree(cert->principals);
+	if (cert->signature_key != NULL)
+		key_free(cert->signature_key);
+}
+
 void
 key_free(Key *k)
 {
@@ -136,11 +184,13 @@ key_free(Key *k)
 	switch (k->type) {
 	case KEY_RSA1:
 	case KEY_RSA:
+	case KEY_RSA_CERT:
 		if (k->rsa != NULL)
 			RSA_free(k->rsa);
 		k->rsa = NULL;
 		break;
 	case KEY_DSA:
+	case KEY_DSA_CERT:
 		if (k->dsa != NULL)
 			DSA_free(k->dsa);
 		k->dsa = NULL;
@@ -151,20 +201,49 @@ key_free(Key *k)
 		fatal("key_free: bad key type %d", k->type);
 		break;
 	}
+	if (key_is_cert(k)) {
+		if (k->cert != NULL)
+			cert_free(k->cert);
+		k->cert = NULL;
+	}
+
 	xfree(k);
 }
 
+static int
+cert_compare(struct KeyCert *a, struct KeyCert *b)
+{
+	if (a == NULL && b == NULL)
+		return 1;
+	if (a == NULL || b == NULL)
+		return 0;
+	if (buffer_len(&a->certblob) != buffer_len(&b->certblob))
+		return 0;
+	if (memcmp(buffer_ptr(&a->certblob), buffer_ptr(&b->certblob),
+	    buffer_len(&a->certblob)) != 0)
+		return 0;
+	return 1;
+}
+
+/*
+ * Compare public portions of key only, allowing comparisons between
+ * certificates and plain keys too.
+ */
 int
-key_equal(const Key *a, const Key *b)
+key_equal_public(const Key *a, const Key *b)
 {
-	if (a == NULL || b == NULL || a->type != b->type)
+	if (a == NULL || b == NULL ||
+	    key_type_plain(a->type) != key_type_plain(b->type))
 		return 0;
+
 	switch (a->type) {
 	case KEY_RSA1:
+	case KEY_RSA_CERT:
 	case KEY_RSA:
 		return a->rsa != NULL && b->rsa != NULL &&
 		    BN_cmp(a->rsa->e, b->rsa->e) == 0 &&
 		    BN_cmp(a->rsa->n, b->rsa->n) == 0;
+	case KEY_DSA_CERT:
 	case KEY_DSA:
 		return a->dsa != NULL && b->dsa != NULL &&
 		    BN_cmp(a->dsa->p, b->dsa->p) == 0 &&
@@ -177,16 +256,27 @@ key_equal(const Key *a, const Key *b)
 	/* NOTREACHED */
 }
 
+int
+key_equal(const Key *a, const Key *b)
+{
+	if (a == NULL || b == NULL || a->type != b->type)
+		return 0;
+	if (key_is_cert(a)) {
+		if (!cert_compare(a->cert, b->cert))
+			return 0;
+	}
+	return key_equal_public(a, b);
+}
+
 u_char*
-key_fingerprint_raw(const Key *k, enum fp_type dgst_type,
-    u_int *dgst_raw_length)
+key_fingerprint_raw(Key *k, enum fp_type dgst_type, u_int *dgst_raw_length)
 {
 	const EVP_MD *md = NULL;
 	EVP_MD_CTX ctx;
 	u_char *blob = NULL;
 	u_char *retval = NULL;
 	u_int len = 0;
-	int nlen, elen;
+	int nlen, elen, otype;
 
 	*dgst_raw_length = 0;
 
@@ -214,6 +304,14 @@ key_fingerprint_raw(const Key *k, enum fp_type dgst_type,
 	case KEY_RSA:
 		key_to_blob(k, &blob, &len);
 		break;
+	case KEY_DSA_CERT:
+	case KEY_RSA_CERT:
+		/* We want a fingerprint of the _key_ not of the cert */
+		otype = k->type;
+		k->type = key_type_plain(k->type);
+		key_to_blob(k, &blob, &len);
+		k->type = otype;
+		break;
 	case KEY_UNSPEC:
 		return retval;
 	default:
@@ -408,7 +506,7 @@ key_fingerprint_randomart(u_char *dgst_raw, u_int dgst_raw_len, const Key *k)
 }
 
 char *
-key_fingerprint(const Key *k, enum fp_type dgst_type, enum fp_rep dgst_rep)
+key_fingerprint(Key *k, enum fp_type dgst_type, enum fp_rep dgst_rep)
 {
 	char *retval = NULL;
 	u_char *dgst_raw;
@@ -533,6 +631,8 @@ key_read(Key *ret, char **cpp)
 	case KEY_UNSPEC:
 	case KEY_RSA:
 	case KEY_DSA:
+	case KEY_DSA_CERT:
+	case KEY_RSA_CERT:
 		space = strchr(cp, ' ');
 		if (space == NULL) {
 			debug3("key_read: missing whitespace");
@@ -577,25 +677,36 @@ key_read(Key *ret, char **cpp)
 			return -1;
 		}
 /*XXXX*/
-		if (ret->type == KEY_RSA) {
+		if (key_is_cert(ret)) {
+			if (!key_is_cert(k)) {
+				error("key_read: loaded key is not a cert");
+				key_free(k);
+				return -1;
+			}
+			if (ret->cert != NULL)
+				cert_free(ret->cert);
+			ret->cert = k->cert;
+			k->cert = NULL;
+		}
+		if (key_type_plain(ret->type) == KEY_RSA) {
 			if (ret->rsa != NULL)
 				RSA_free(ret->rsa);
 			ret->rsa = k->rsa;
 			k->rsa = NULL;
-			success = 1;
 #ifdef DEBUG_PK
 			RSA_print_fp(stderr, ret->rsa, 8);
 #endif
-		} else {
+		}
+		if (key_type_plain(ret->type) == KEY_DSA) {
 			if (ret->dsa != NULL)
 				DSA_free(ret->dsa);
 			ret->dsa = k->dsa;
 			k->dsa = NULL;
-			success = 1;
 #ifdef DEBUG_PK
 			DSA_print_fp(stderr, ret->dsa, 8);
 #endif
 		}
+		success = 1;
 /*XXXX*/
 		key_free(k);
 		if (success != 1)
@@ -622,28 +733,53 @@ key_write(const Key *key, FILE *f)
 	u_char *blob;
 	char *uu;
 
-	if (key->type == KEY_RSA1 && key->rsa != NULL) {
+	if (key_is_cert(key)) {
+		if (key->cert == NULL) {
+			error("%s: no cert data", __func__);
+			return 0;
+		}
+		if (buffer_len(&key->cert->certblob) == 0) {
+			error("%s: no signed certificate blob", __func__);
+			return 0;
+		}
+	}
+
+	switch (key->type) {
+	case KEY_RSA1:
+		if (key->rsa == NULL)
+			return 0;
 		/* size of modulus 'n' */
 		bits = BN_num_bits(key->rsa->n);
 		fprintf(f, "%u", bits);
 		if (write_bignum(f, key->rsa->e) &&
-		    write_bignum(f, key->rsa->n)) {
-			success = 1;
-		} else {
-			error("key_write: failed for RSA key");
-		}
-	} else if ((key->type == KEY_DSA && key->dsa != NULL) ||
-	    (key->type == KEY_RSA && key->rsa != NULL)) {
-		key_to_blob(key, &blob, &len);
-		uu = xmalloc(2*len);
-		n = uuencode(blob, len, uu, 2*len);
-		if (n > 0) {
-			fprintf(f, "%s %s", key_ssh_name(key), uu);
-			success = 1;
-		}
-		xfree(blob);
-		xfree(uu);
+		    write_bignum(f, key->rsa->n))
+			return 1;
+		error("key_write: failed for RSA key");
+		return 0;
+	case KEY_DSA:
+	case KEY_DSA_CERT:
+		if (key->dsa == NULL)
+			return 0;
+		break;
+	case KEY_RSA:
+	case KEY_RSA_CERT:
+		if (key->rsa == NULL)
+			return 0;
+		break;
+	default:
+		return 0;
 	}
+
+	key_to_blob(key, &blob, &len);
+	uu = xmalloc(2*len);
+	n = uuencode(blob, len, uu, 2*len);
+	if (n > 0) {
+		fprintf(f, "%s %s", key_ssh_name(key), uu);
+		success = 1;
+	}
+	xfree(blob);
+	xfree(uu);
+
 	return success;
 }
 
@@ -657,6 +793,10 @@ key_type(const Key *k)
 		return "RSA";
 	case KEY_DSA:
 		return "DSA";
+	case KEY_RSA_CERT:
+		return "RSA-CERT";
+	case KEY_DSA_CERT:
+		return "DSA-CERT";
 	}
 	return "unknown";
 }
@@ -669,6 +809,10 @@ key_ssh_name(const Key *k)
 		return "ssh-rsa";
 	case KEY_DSA:
 		return "ssh-dss";
+	case KEY_RSA_CERT:
+		return "ssh-rsa-cert-v00@openssh.com";
+	case KEY_DSA_CERT:
+		return "ssh-dss-cert-v00@openssh.com";
 	}
 	return "ssh-unknown";
 }
@@ -679,8 +823,10 @@ key_size(const Key *k)
 	switch (k->type) {
 	case KEY_RSA1:
 	case KEY_RSA:
+	case KEY_RSA_CERT:
 		return BN_num_bits(k->rsa->n);
 	case KEY_DSA:
+	case KEY_DSA_CERT:
 		return BN_num_bits(k->dsa->p);
 	}
 	return 0;
@@ -723,6 +869,9 @@ key_generate(int type, u_int bits)
 	case KEY_RSA1:
 		k->rsa = rsa_generate_private_key(bits);
 		break;
+	case KEY_RSA_CERT:
+	case KEY_DSA_CERT:
+		fatal("key_generate: cert keys cannot be generated directly");
 	default:
 		fatal("key_generate: unknown type %d", type);
 	}
@@ -730,12 +879,55 @@ key_generate(int type, u_int bits)
 	return k;
 }
 
+void
+key_cert_copy(const Key *from_key, struct Key *to_key)
+{
+	u_int i;
+	const struct KeyCert *from;
+	struct KeyCert *to;
+
+	if (to_key->cert != NULL) {
+		cert_free(to_key->cert);
+		to_key->cert = NULL;
+	}
+
+	if ((from = from_key->cert) == NULL)
+		return;
+
+	to = to_key->cert = cert_new();
+
+	buffer_append(&to->certblob, buffer_ptr(&from->certblob),
+	    buffer_len(&from->certblob));
+
+	buffer_append(&to->constraints, buffer_ptr(&from->constraints),
+	    buffer_len(&from->constraints));
+
+	to->type = from->type;
+	to->key_id = from->key_id == NULL ? NULL : xstrdup(from->key_id);
+	to->valid_after = from->valid_after;
+	to->valid_before = from->valid_before;
+	to->signature_key = from->signature_key == NULL ?
+	    NULL : key_from_private(from->signature_key);
+
+	to->nprincipals = from->nprincipals;
+	if (to->nprincipals > CERT_MAX_PRINCIPALS)
+		fatal("%s: nprincipals (%u) > CERT_MAX_PRINCIPALS (%u)",
+		    __func__, to->nprincipals, CERT_MAX_PRINCIPALS);
+	if (to->nprincipals > 0) {
+		to->principals = xcalloc(from->nprincipals,
+		    sizeof(*to->principals));
+		for (i = 0; i < to->nprincipals; i++)
+			to->principals[i] = xstrdup(from->principals[i]);
+	}
+}
+
 Key *
 key_from_private(const Key *k)
 {
 	Key *n = NULL;
 	switch (k->type) {
 	case KEY_DSA:
+	case KEY_DSA_CERT:
 		n = key_new(k->type);
 		if ((BN_copy(n->dsa->p, k->dsa->p) == NULL) ||
 		    (BN_copy(n->dsa->q, k->dsa->q) == NULL) ||
@@ -745,6 +937,7 @@ key_from_private(const Key *k)
 		break;
 	case KEY_RSA:
 	case KEY_RSA1:
+	case KEY_RSA_CERT:
 		n = key_new(k->type);
 		if ((BN_copy(n->rsa->n, k->rsa->n) == NULL) ||
 		    (BN_copy(n->rsa->e, k->rsa->e) == NULL))
@@ -754,6 +947,8 @@ key_from_private(const Key *k)
 		fatal("key_from_private: unknown type %d", k->type);
 		break;
 	}
+	if (key_is_cert(k))
+		key_cert_copy(k, n);
 	return n;
 }
 
@@ -770,6 +965,10 @@ key_type_from_name(char *name)
 		return KEY_RSA;
 	} else if (strcmp(name, "ssh-dss") == 0) {
 		return KEY_DSA;
+	} else if (strcmp(name, "ssh-rsa-cert-v00@openssh.com") == 0) {
+		return KEY_RSA_CERT;
+	} else if (strcmp(name, "ssh-dss-cert-v00@openssh.com") == 0) {
+		return KEY_DSA_CERT;
 	}
 	debug2("key_type_from_name: unknown key type '%s'", name);
 	return KEY_UNSPEC;
@@ -797,6 +996,117 @@ key_names_valid2(const char *names)
 	return 1;
 }
 
+static int
+cert_parse(Buffer *b, Key *key, const u_char *blob, u_int blen)
+{
+	u_char *principals, *constraints, *sig_key, *sig;
+	u_int signed_len, plen, clen, sklen, slen;
+	Buffer tmp;
+	char *principal;
+	int ret = -1;
+
+	buffer_init(&tmp);
+
+	/* Copy the entire key blob for verification and later serialisation */
+	buffer_append(&key->cert->certblob, blob, blen);
+
+	principals = constraints = sig_key = sig = NULL;
+	if (buffer_get_int_ret(&key->cert->type, b) != 0 ||
+	    (key->cert->key_id = buffer_get_string_ret(b, NULL)) == NULL ||
+	    (principals = buffer_get_string_ret(b, &plen)) == NULL ||
+	    buffer_get_int64_ret(&key->cert->valid_after, b) != 0 ||
+	    buffer_get_int64_ret(&key->cert->valid_before, b) != 0 ||
+	    (constraints = buffer_get_string_ret(b, &clen)) == NULL ||
+	    /* skip nonce */ buffer_get_string_ptr_ret(b, NULL) == NULL ||
+	    /* skip reserved */ buffer_get_string_ptr_ret(b, NULL) == NULL ||
+	    (sig_key = buffer_get_string_ret(b, &sklen)) == NULL) {
+		error("%s: parse error", __func__);
+		goto out;
+	}
+
+	/* Signature is left in the buffer so we can calculate this length */
+	signed_len = buffer_len(&key->cert->certblob) - buffer_len(b);
+
+	if ((sig = buffer_get_string_ret(b, &slen)) == NULL) {
+		error("%s: parse error", __func__);
+		goto out;
+	}
+
+	if (key->cert->type != SSH2_CERT_TYPE_USER &&
+	    key->cert->type != SSH2_CERT_TYPE_HOST) {
+		error("Unknown certificate type %u", key->cert->type);
+		goto out;
+	}
+
+	buffer_append(&tmp, principals, plen);
+	while (buffer_len(&tmp) > 0) {
+		if (key->cert->nprincipals >= CERT_MAX_PRINCIPALS) {
+			error("Too many principals");
+			goto out;
+		}
+		if ((principal = buffer_get_string_ret(&tmp, NULL)) == NULL) {
+			error("Principals data invalid");
+			goto out;
+		}
+		key->cert->principals = xrealloc(key->cert->principals,
+		    key->cert->nprincipals + 1, sizeof(*key->cert->principals));
+		key->cert->principals[key->cert->nprincipals++] = principal;
+	}
+
+	buffer_clear(&tmp);
+
+	buffer_append(&key->cert->constraints, constraints, clen);
+	buffer_append(&tmp, constraints, clen);
+	/* validate structure */
+	while (buffer_len(&tmp) != 0) {
+		if (buffer_get_string_ptr(&tmp, NULL) == NULL ||
+		    buffer_get_string_ptr(&tmp, NULL) == NULL) {
+			error("Constraints data invalid");
+			goto out;
+		}
+	}
+	buffer_clear(&tmp);
+
+	if ((key->cert->signature_key = key_from_blob(sig_key,
+	    sklen)) == NULL) {
+		error("Signature key invalid");
+		goto out;
+	}
+	if (key->cert->signature_key->type != KEY_RSA &&
+	    key->cert->signature_key->type != KEY_DSA) {
+		error("Invalid signature key type %s (%d)",
+		    key_type(key->cert->signature_key),
+		    key->cert->signature_key->type);
+		goto out;
+	}
+
+	switch (key_verify(key->cert->signature_key, sig, slen, 
+	    buffer_ptr(&key->cert->certblob), signed_len)) {
+	case 1:
+		break; /* Good signature */
+	case 0:
+		error("Invalid signature on certificate");
+		goto out;
+	case -1:
+		error("Certificate signature verification failed");
+		goto out;
+	}
+
+	ret = 0;
+
+ out:
+	buffer_free(&tmp);
+	if (principals != NULL)
+		xfree(principals);
+	if (constraints != NULL)
+		xfree(constraints);
+	if (sig_key != NULL)
+		xfree(sig_key);
+	if (sig != NULL)
+		xfree(sig);
+	return ret;
+}
+
 Key *
 key_from_blob(const u_char *blob, u_int blen)
 {
@@ -819,10 +1129,12 @@ key_from_blob(const u_char *blob, u_int blen)
 
 	switch (type) {
 	case KEY_RSA:
+	case KEY_RSA_CERT:
 		key = key_new(type);
 		if (buffer_get_bignum2_ret(&b, key->rsa->e) == -1 ||
 		    buffer_get_bignum2_ret(&b, key->rsa->n) == -1) {
 			error("key_from_blob: can't read rsa key");
+ badkey:
 			key_free(key);
 			key = NULL;
 			goto out;
@@ -832,15 +1144,14 @@ key_from_blob(const u_char *blob, u_int blen)
 #endif
 		break;
 	case KEY_DSA:
+	case KEY_DSA_CERT:
 		key = key_new(type);
 		if (buffer_get_bignum2_ret(&b, key->dsa->p) == -1 ||
 		    buffer_get_bignum2_ret(&b, key->dsa->q) == -1 ||
 		    buffer_get_bignum2_ret(&b, key->dsa->g) == -1 ||
 		    buffer_get_bignum2_ret(&b, key->dsa->pub_key) == -1) {
 			error("key_from_blob: can't read dsa key");
-			key_free(key);
-			key = NULL;
-			goto out;
+			goto badkey;
 		}
 #ifdef DEBUG_PK
 		DSA_print_fp(stderr, key->dsa, 8);
@@ -853,6 +1164,10 @@ key_from_blob(const u_char *blob, u_int blen)
 		error("key_from_blob: cannot handle type %s", ktype);
 		goto out;
 	}
+	if (key_is_cert(key) && cert_parse(&b, key, blob, blen) == -1) {
+		error("key_from_blob: can't parse cert data");
+		goto badkey;
+	}
 	rlen = buffer_len(&b);
 	if (key != NULL && rlen != 0)
 		error("key_from_blob: remaining bytes in key blob %d", rlen);
@@ -875,6 +1190,12 @@ key_to_blob(const Key *key, u_char **blobp, u_int *lenp)
 	}
 	buffer_init(&b);
 	switch (key->type) {
+	case KEY_DSA_CERT:
+	case KEY_RSA_CERT:
+		/* Use the existing blob */
+		buffer_append(&b, buffer_ptr(&key->cert->certblob),
+		    buffer_len(&key->cert->certblob));
+		break;
 	case KEY_DSA:
 		buffer_put_cstring(&b, key_ssh_name(key));
 		buffer_put_bignum2(&b, key->dsa->p);
@@ -911,8 +1232,10 @@ key_sign(
     const u_char *data, u_int datalen)
 {
 	switch (key->type) {
+	case KEY_DSA_CERT:
 	case KEY_DSA:
 		return ssh_dss_sign(key, sigp, lenp, data, datalen);
+	case KEY_RSA_CERT:
 	case KEY_RSA:
 		return ssh_rsa_sign(key, sigp, lenp, data, datalen);
 	default:
@@ -935,8 +1258,10 @@ key_verify(
 		return -1;
 
 	switch (key->type) {
+	case KEY_DSA_CERT:
 	case KEY_DSA:
 		return ssh_dss_verify(key, signature, signaturelen, data, datalen);
+	case KEY_RSA_CERT:
 	case KEY_RSA:
 		return ssh_rsa_verify(key, signature, signaturelen, data, datalen);
 	default:
@@ -958,6 +1283,9 @@ key_demote(const Key *k)
 	pk->rsa = NULL;
 
 	switch (k->type) {
+	case KEY_RSA_CERT:
+		key_cert_copy(k, pk);
+		/* FALLTHROUGH */
 	case KEY_RSA1:
 	case KEY_RSA:
 		if ((pk->rsa = RSA_new()) == NULL)
@@ -967,6 +1295,9 @@ key_demote(const Key *k)
 		if ((pk->rsa->n = BN_dup(k->rsa->n)) == NULL)
 			fatal("key_demote: BN_dup failed");
 		break;
+	case KEY_DSA_CERT:
+		key_cert_copy(k, pk);
+		/* FALLTHROUGH */
 	case KEY_DSA:
 		if ((pk->dsa = DSA_new()) == NULL)
 			fatal("key_demote: DSA_new failed");
@@ -986,3 +1317,199 @@ key_demote(const Key *k)
 
 	return (pk);
 }
+
+int
+key_is_cert(const Key *k)
+{
+	return k != NULL &&
+	    (k->type == KEY_RSA_CERT || k->type == KEY_DSA_CERT);
+}
+
+/* Return the cert-less equivalent to a certified key type */
+int
+key_type_plain(int type)
+{
+	switch (type) {
+	case KEY_RSA_CERT:
+		return KEY_RSA;
+	case KEY_DSA_CERT:
+		return KEY_DSA;
+	default:
+		return type;
+	}
+}
+
+/* Convert a KEY_RSA or KEY_DSA to their _CERT equivalent */
+int
+key_to_certified(Key *k)
+{
+	switch (k->type) {
+	case KEY_RSA:
+		k->cert = cert_new();
+		k->type = KEY_RSA_CERT;
+		return 0;
+	case KEY_DSA:
+		k->cert = cert_new();
+		k->type = KEY_DSA_CERT;
+		return 0;
+	default:
+		error("%s: key has incorrect type %s", __func__, key_type(k));
+		return -1;
+	}
+}
+
+/* Convert a KEY_RSA_CERT or KEY_DSA_CERT to their raw key equivalent */
+int
+key_drop_cert(Key *k)
+{
+	switch (k->type) {
+	case KEY_RSA_CERT:
+		cert_free(k->cert);
+		k->type = KEY_RSA;
+		return 0;
+	case KEY_DSA_CERT:
+		cert_free(k->cert);
+		k->type = KEY_DSA;
+		return 0;
+	default:
+		error("%s: key has incorrect type %s", __func__, key_type(k));
+		return -1;
+	}
+}
+
+/* Sign a KEY_RSA_CERT or KEY_DSA_CERT, (re-)generating the signed certblob */
+int
+key_certify(Key *k, Key *ca)
+{
+	Buffer principals;
+	u_char *ca_blob, *sig_blob, nonce[32];
+	u_int i, ca_len, sig_len;
+
+	if (k->cert == NULL) {
+		error("%s: key lacks cert info", __func__);
+		return -1;
+	}
+
+	if (!key_is_cert(k)) {
+		error("%s: certificate has unknown type %d", __func__,
+		    k->cert->type);
+		return -1;
+	}
+
+	if (ca->type != KEY_RSA && ca->type != KEY_DSA) {
+		error("%s: CA key has unsupported type %s", __func__,
+		    key_type(ca));
+		return -1;
+	}
+
+	key_to_blob(ca, &ca_blob, &ca_len);
+
+	buffer_clear(&k->cert->certblob);
+	buffer_put_cstring(&k->cert->certblob, key_ssh_name(k));
+
+	switch (k->type) {
+	case KEY_DSA_CERT:
+		buffer_put_bignum2(&k->cert->certblob, k->dsa->p);
+		buffer_put_bignum2(&k->cert->certblob, k->dsa->q);
+		buffer_put_bignum2(&k->cert->certblob, k->dsa->g);
+		buffer_put_bignum2(&k->cert->certblob, k->dsa->pub_key);
+		break;
+	case KEY_RSA_CERT:
+		buffer_put_bignum2(&k->cert->certblob, k->rsa->e);
+		buffer_put_bignum2(&k->cert->certblob, k->rsa->n);
+		break;
+	default:
+		error("%s: key has incorrect type %s", __func__, key_type(k));
+		buffer_clear(&k->cert->certblob);
+		xfree(ca_blob);
+		return -1;
+	}
+
+	buffer_put_int(&k->cert->certblob, k->cert->type);
+	buffer_put_cstring(&k->cert->certblob, k->cert->key_id);
+
+	buffer_init(&principals);
+	for (i = 0; i < k->cert->nprincipals; i++)
+		buffer_put_cstring(&principals, k->cert->principals[i]);
+	buffer_put_string(&k->cert->certblob, buffer_ptr(&principals),
+	    buffer_len(&principals));
+	buffer_free(&principals);
+
+	buffer_put_int64(&k->cert->certblob, k->cert->valid_after);
+	buffer_put_int64(&k->cert->certblob, k->cert->valid_before);
+	buffer_put_string(&k->cert->certblob,
+	    buffer_ptr(&k->cert->constraints),
+	    buffer_len(&k->cert->constraints));
+
+	arc4random_buf(&nonce, sizeof(nonce));
+	buffer_put_string(&k->cert->certblob, nonce, sizeof(nonce));
+	buffer_put_string(&k->cert->certblob, NULL, 0); /* reserved */
+	buffer_put_string(&k->cert->certblob, ca_blob, ca_len);
+	xfree(ca_blob);
+
+	/* Sign the whole mess */
+	if (key_sign(ca, &sig_blob, &sig_len, buffer_ptr(&k->cert->certblob),
+	    buffer_len(&k->cert->certblob)) != 0) {
+		error("%s: signature operation failed", __func__);
+		buffer_clear(&k->cert->certblob);
+		return -1;
+	}
+	/* Append signature and we are done */
+	buffer_put_string(&k->cert->certblob, sig_blob, sig_len);
+	xfree(sig_blob);
+
+	return 0;
+}
+
+int
+key_cert_check_authority(const Key *k, int want_host, int require_principal,
+    const char *name, const char **reason)
+{
+	u_int i, principal_matches;
+	time_t now = time(NULL);
+
+	if (want_host) {
+		if (k->cert->type != SSH2_CERT_TYPE_HOST) {
+			*reason = "Certificate invalid: not a host certificate";
+			return -1;
+		}
+	} else {
+		if (k->cert->type != SSH2_CERT_TYPE_USER) {
+			*reason = "Certificate invalid: not a user certificate";
+			return -1;
+		}
+	}
+	if (now < 0) {
+		error("%s: system clock lies before epoch", __func__);
+		*reason = "Certificate invalid: not yet valid";
+		return -1;
+	}
+	if ((u_int64_t)now < k->cert->valid_after) {
+		*reason = "Certificate invalid: not yet valid";
+		return -1;
+	}
+	if ((u_int64_t)now >= k->cert->valid_before) {
+		*reason = "Certificate invalid: expired";
+		return -1;
+	}
+	if (k->cert->nprincipals == 0) {
+		if (require_principal) {
+			*reason = "Certificate lacks principal list";
+			return -1;
+		}
+	} else {
+		principal_matches = 0;
+		for (i = 0; i < k->cert->nprincipals; i++) {
+			if (strcmp(name, k->cert->principals[i]) == 0) {
+				principal_matches = 1;
+				break;
+			}
+		}
+		if (!principal_matches) {
+			*reason = "Certificate invalid: name is not a listed "
+			    "principal";
+			return -1;
+		}
+	}
+	return 0;
+}