- djm@cvs.openbsd.org 2010/04/16 01:47:26

     [PROTOCOL.certkeys auth-options.c auth-options.h auth-rsa.c]
     [auth2-pubkey.c authfd.c key.c key.h myproposal.h ssh-add.c]
     [ssh-agent.c ssh-dss.c ssh-keygen.1 ssh-keygen.c ssh-rsa.c]
     [sshconnect.c sshconnect2.c sshd.c]
     revised certificate format ssh-{dss,rsa}-cert-v01@openssh.com with the
     following changes:

     move the nonce field to the beginning of the certificate where it can
     better protect against chosen-prefix attacks on the signature hash

     Rename "constraints" field to "critical options"

     Add a new non-critical "extensions" field

     Add a serial number

     The older format is still support for authentication and cert generation
     (use "ssh-keygen -t v00 -s ca_key ..." to generate a v00 certificate)

     ok markus@

19 files changed, 449 insertions, 213 deletions

diff --git a/ChangeLog b/ChangeLog
index fd4ce5db..b058de0f 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -41,6 +41,27 @@
      retry lookup for private key if there's no matching key with CKA_SIGN
      attribute enabled; this fixes fixes MuscleCard support (bugzilla #1736)
      ok djm@
+   - djm@cvs.openbsd.org 2010/04/16 01:47:26
+     [PROTOCOL.certkeys auth-options.c auth-options.h auth-rsa.c]
+     [auth2-pubkey.c authfd.c key.c key.h myproposal.h ssh-add.c]
+     [ssh-agent.c ssh-dss.c ssh-keygen.1 ssh-keygen.c ssh-rsa.c]
+     [sshconnect.c sshconnect2.c sshd.c]
+     revised certificate format ssh-{dss,rsa}-cert-v01@openssh.com with the
+     following changes:
+     
+     move the nonce field to the beginning of the certificate where it can
+     better protect against chosen-prefix attacks on the signature hash
+     
+     Rename "constraints" field to "critical options"
+     
+     Add a new non-critical "extensions" field
+     
+     Add a serial number
+     
+     The older format is still support for authentication and cert generation
+     (use "ssh-keygen -t v00 -s ca_key ..." to generate a v00 certificate)
+     
+     ok markus@
 
 20100410
  - (dtucker) [configure.ac] Put the check for the existence of getaddrinfo
diff --git a/PROTOCOL.certkeys b/PROTOCOL.certkeys
index 1ed9e206..a2069f54 100644
--- a/PROTOCOL.certkeys
+++ b/PROTOCOL.certkeys
@@ -16,7 +16,7 @@ These protocol extensions build on the simple public key authentication
 system already in SSH to allow certificate-based authentication.
 The certificates used are not traditional X.509 certificates, with
 numerous options and complex encoding rules, but something rather
-more minimal: a key, some identity information and usage constraints
+more minimal: a key, some identity information and usage options
 that have been signed with some other trusted key.
 
 A sshd server may be configured to allow authentication via certified
@@ -27,7 +27,7 @@ of acceptance of certified host keys, by adding a similar ability
 to specify CA keys in ~/.ssh/known_hosts.
 
 Certified keys are represented using two new key types:
-ssh-rsa-cert-v00@openssh.com and ssh-dss-cert-v00@openssh.com that
+ssh-rsa-cert-v01@openssh.com and ssh-dss-cert-v01@openssh.com that
 include certification information along with the public key that is used
 to sign challenges. ssh-keygen performs the CA signing operation.
 
@@ -47,7 +47,7 @@ in RFC4252 section 7.
 New public key formats
 ----------------------
 
-The ssh-rsa-cert-v00@openssh.com and ssh-dss-cert-v00@openssh.com key
+The ssh-rsa-cert-v01@openssh.com and ssh-dss-cert-v01@openssh.com key
 types take a similar high-level format (note: data types and
 encoding are as per RFC4251 section 5). The serialised wire encoding of
 these certificates is also used for storing them on disk.
@@ -57,42 +57,55 @@ these certificates is also used for storing them on disk.
 
 RSA certificate
 
-    string    "ssh-rsa-cert-v00@openssh.com"
+    string    "ssh-rsa-cert-v01@openssh.com"
+    string    nonce
     mpint     e
     mpint     n
+    uint64    serial
     uint32    type
     string    key id
     string    valid principals
     uint64    valid after
     uint64    valid before
-    string    constraints
-    string    nonce
+    string    critical options
+    string    extensions
     string    reserved
     string    signature key
     string    signature
 
 DSA certificate
 
-    string    "ssh-dss-cert-v00@openssh.com"
+    string    "ssh-dss-cert-v01@openssh.com"
+    string    nonce
     mpint     p
     mpint     q
     mpint     g
     mpint     y
+    uint64    serial
     uint32    type
     string    key id
     string    valid principals
     uint64    valid after
     uint64    valid before
-    string    constraints
-    string    nonce
+    string    critical options
+    string    extensions
     string    reserved
     string    signature key
     string    signature
 
+The nonce field is a CA-provided random bitstring of arbitrary length
+(but typically 16 or 32 bytes) included to make attacks that depend on
+inducing collisions in the signature hash infeasible.
+
 e and n are the RSA exponent and public modulus respectively.
 
 p, q, g, y are the DSA parameters as described in FIPS-186-2.
 
+serial is an optional certificate serial number set by the CA to
+provide an abbreviated way to refer to certificates from that CA.
+If a CA does not with to number its certificates it must set this
+field to zero.
+
 type specifies whether this certificate is for identification of a user
 or a host using a SSH_CERT_TYPE_... value.
 
@@ -112,13 +125,15 @@ certificate. Each represents a time in seconds since 1970-01-01
 00:00:00. A certificate is considered valid if:
 	 valid after <= current time < valid before
 
-constraints is a set of zero or more key constraints encoded as below.
+criticial options is a set of zero or more key options encoded as
+below. All such options are "critical" in the sense that an implementation
+must refuse to authorise a key that has an unrecognised option.
 
-The nonce field is a CA-provided random bitstring of arbitrary length
-(but typically 16 or 32 bytes) included to make attacks that depend on
-inducing collisions in the signature hash infeasible.
+extensions is a set of zero or more optional extensions. These extensions
+are not critical, and an implementation that encounters one that it does
+not recognise may safely ignore it. No extensions are defined at present.
 
-The reserved field is current unused and is ignored in this version of
+The reserved field is currently unused and is ignored in this version of
 the protocol.
 
 signature key contains the CA key used to sign the certificate.
@@ -132,22 +147,22 @@ up to, and including the signature key. Signatures are computed and
 encoded according to the rules defined for the CA's public key algorithm
 (RFC4253 section 6.6 for ssh-rsa and ssh-dss).
 
-Constraints
------------
+Critical options
+----------------
 
-The constraints section of the certificate specifies zero or more
-constraints on the certificates validity. The format of this field
+The critical options section of the certificate specifies zero or more
+options on the certificates validity. The format of this field
 is a sequence of zero or more tuples:
 
     string       name
     string       data
 
-The name field identifies the constraint and the data field encodes
-constraint-specific information (see below). All constraints are
-"critical", if an implementation does not recognise a constraint
+The name field identifies the option and the data field encodes
+option-specific information (see below). All options are
+"critical", if an implementation does not recognise a option
 then the validating party should refuse to accept the certificate.
 
-The supported constraints and the contents and structure of their
+The supported options and the contents and structure of their
 data fields are:
 
 Name                    Format        Description
@@ -159,35 +174,35 @@ force-command           string        Specifies a command that is executed
 
 permit-X11-forwarding   empty         Flag indicating that X11 forwarding
                                       should be permitted. X11 forwarding will
-                                      be refused if this constraint is absent.
+                                      be refused if this option is absent.
 
 permit-agent-forwarding empty         Flag indicating that agent forwarding
                                       should be allowed. Agent forwarding
                                       must not be permitted unless this
-                                      constraint is present.
+                                      option is present.
 
 permit-port-forwarding  empty         Flag indicating that port-forwarding
-                                      should be allowed. If this constraint is
+                                      should be allowed. If this option is
                                       not present then no port forwarding will
                                       be allowed.
 
 permit-pty              empty         Flag indicating that PTY allocation
                                       should be permitted. In the absence of
-                                      this constraint PTY allocation will be
+                                      this option PTY allocation will be
                                       disabled.
 
 permit-user-rc          empty         Flag indicating that execution of
                                       ~/.ssh/rc should be permitted. Execution
                                       of this script will not be permitted if
-                                      this constraint is not present.
+                                      this option is not present.
 
 source-address          string        Comma-separated list of source addresses
                                       from which this certificate is accepted
                                       for authentication. Addresses are
                                       specified in CIDR format (nn.nn.nn.nn/nn
                                       or hhhh::hhhh/nn).
-                                      If this constraint is not present then
+                                      If this option is not present then
                                       certificates may be presented from any
                                       source address.
 
-$OpenBSD: PROTOCOL.certkeys,v 1.3 2010/03/03 22:50:40 djm Exp $
+$OpenBSD: PROTOCOL.certkeys,v 1.4 2010/04/16 01:47:25 djm Exp $
diff --git a/auth-options.c b/auth-options.c
index 69b314fb..60d5f749 100644
--- a/auth-options.c
+++ b/auth-options.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: auth-options.c,v 1.49 2010/03/16 15:46:52 stevesk Exp $ */
+/* $OpenBSD: auth-options.c,v 1.50 2010/04/16 01:47:26 djm Exp $ */
 /*
  * Author: Tatu Ylonen <ylo@cs.hut.fi>
  * Copyright (c) 1995 Tatu Ylonen <ylo@cs.hut.fi>, Espoo, Finland
@@ -27,10 +27,10 @@
 #include "canohost.h"
 #include "buffer.h"
 #include "channels.h"
-#include "auth-options.h"
 #include "servconf.h"
 #include "misc.h"
 #include "key.h"
+#include "auth-options.h"
 #include "hostfile.h"
 #include "auth.h"
 #ifdef GSSAPI
@@ -377,11 +377,11 @@ bad_option:
 }
 
 /*
- * Set options from certificate constraints. These supersede user key options
- * so this must be called after auth_parse_options().
+ * Set options from critical certificate options. These supersede user key
+ * options so this must be called after auth_parse_options().
  */
 int
-auth_cert_constraints(Buffer *c_orig, struct passwd *pw)
+auth_cert_options(Key *k, struct passwd *pw)
 {
 	u_char *name = NULL, *data_blob = NULL;
 	u_int nlen, dlen, clen;
@@ -400,12 +400,13 @@ auth_cert_constraints(Buffer *c_orig, struct passwd *pw)
 
 	/* Make copy to avoid altering original */
 	buffer_init(&c);
-	buffer_append(&c, buffer_ptr(c_orig), buffer_len(c_orig));
+	buffer_append(&c,
+	    buffer_ptr(&k->cert->critical), buffer_len(&k->cert->critical));
 
 	while (buffer_len(&c) > 0) {
 		if ((name = buffer_get_string_ret(&c, &nlen)) == NULL ||
 		    (data_blob = buffer_get_string_ret(&c, &dlen)) == NULL) {
-			error("Certificate constraints corrupt");
+			error("Certificate options corrupt");
 			goto out;
 		}
 		buffer_append(&data, data_blob, dlen);
@@ -439,7 +440,7 @@ auth_cert_constraints(Buffer *c_orig, struct passwd *pw)
 			}
 			if (cert_forced_command != NULL) {
 				error("Certificate has multiple "
-				    "force-command constraints");
+				    "force-command options");
 				xfree(command);
 				goto out;
 			}
@@ -459,7 +460,7 @@ auth_cert_constraints(Buffer *c_orig, struct passwd *pw)
 			}
 			if (cert_source_address_done++) {
 				error("Certificate has multiple "
-				    "source-address constraints");
+				    "source-address options");
 				xfree(allowed);
 				goto out;
 			}
@@ -502,7 +503,7 @@ auth_cert_constraints(Buffer *c_orig, struct passwd *pw)
 		name = data_blob = NULL;
 	}
 
-	/* successfully parsed all constraints */
+	/* successfully parsed all options */
 	ret = 0;
 
 	no_port_forwarding_flag |= cert_no_port_forwarding_flag;
diff --git a/auth-options.h b/auth-options.h
index 694edc84..20f0dbe3 100644
--- a/auth-options.h
+++ b/auth-options.h
@@ -1,4 +1,4 @@
-/* $OpenBSD: auth-options.h,v 1.18 2010/02/26 20:29:54 djm Exp $ */
+/* $OpenBSD: auth-options.h,v 1.19 2010/04/16 01:47:26 djm Exp $ */
 
 /*
  * Author: Tatu Ylonen <ylo@cs.hut.fi>
@@ -34,6 +34,6 @@ extern int key_is_cert_authority;
 
 int	auth_parse_options(struct passwd *, char *, char *, u_long);
 void	auth_clear_options(void);
-int	auth_cert_constraints(Buffer *, struct passwd *);
+int	auth_cert_options(Key *, struct passwd *);
 
 #endif
diff --git a/auth-rsa.c b/auth-rsa.c
index 65571a89..326937ac 100644
--- a/auth-rsa.c
+++ b/auth-rsa.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: auth-rsa.c,v 1.74 2010/03/04 10:36:03 djm Exp $ */
+/* $OpenBSD: auth-rsa.c,v 1.75 2010/04/16 01:47:26 djm Exp $ */
 /*
  * Author: Tatu Ylonen <ylo@cs.hut.fi>
  * Copyright (c) 1995 Tatu Ylonen <ylo@cs.hut.fi>, Espoo, Finland
@@ -34,11 +34,11 @@
 #include "uidswap.h"
 #include "match.h"
 #include "buffer.h"
-#include "auth-options.h"
 #include "pathnames.h"
 #include "log.h"
 #include "servconf.h"
 #include "key.h"
+#include "auth-options.h"
 #include "hostfile.h"
 #include "auth.h"
 #ifdef GSSAPI
diff --git a/auth2-pubkey.c b/auth2-pubkey.c
index c4cadf4e..83ecd659 100644
--- a/auth2-pubkey.c
+++ b/auth2-pubkey.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: auth2-pubkey.c,v 1.22 2010/03/10 23:27:17 djm Exp $ */
+/* $OpenBSD: auth2-pubkey.c,v 1.23 2010/04/16 01:47:26 djm Exp $ */
 /*
  * Copyright (c) 2000 Markus Friedl.  All rights reserved.
  *
@@ -235,7 +235,7 @@ user_key_allowed2(struct passwd *pw, Key *key, char *file)
 		}
 		if (auth_parse_options(pw, key_options, file, linenum) != 1)
 			continue;
-		if (key->type == KEY_RSA_CERT || key->type == KEY_DSA_CERT) {
+		if (key_is_cert(key)) {
 			if (!key_is_cert_authority)
 				continue;
 			if (!key_equal(found, key->cert->signature_key))
@@ -251,8 +251,7 @@ user_key_allowed2(struct passwd *pw, Key *key, char *file)
 				auth_debug_add("%s", reason);
 				continue;
 			}
-			if (auth_cert_constraints(&key->cert->constraints,
-			    pw) != 0) {
+			if (auth_cert_options(key, pw) != 0) {
 				xfree(fp);
 				continue;
 			}
@@ -307,7 +306,7 @@ user_cert_trusted_ca(struct passwd *pw, Key *key)
 		auth_debug_add("%s", reason);
 		goto out;
 	}
-	if (auth_cert_constraints(&key->cert->constraints, pw) != 0)
+	if (auth_cert_options(key, pw) != 0)
 		goto out;
 
 	verbose("Accepted certificate ID \"%s\" signed by %s CA %s via %s",
diff --git a/authfd.c b/authfd.c
index 28a8cf2d..739722fb 100644
--- a/authfd.c
+++ b/authfd.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: authfd.c,v 1.82 2010/02/26 20:29:54 djm Exp $ */
+/* $OpenBSD: authfd.c,v 1.83 2010/04/16 01:47:26 djm Exp $ */
 /*
  * Author: Tatu Ylonen <ylo@cs.hut.fi>
  * Copyright (c) 1995 Tatu Ylonen <ylo@cs.hut.fi>, Espoo, Finland
@@ -483,6 +483,7 @@ ssh_encode_identity_ssh2(Buffer *b, Key *key, const char *comment)
 		buffer_put_bignum2(b, key->rsa->p);
 		buffer_put_bignum2(b, key->rsa->q);
 		break;
+	case KEY_RSA_CERT_V00:
 	case KEY_RSA_CERT:
 		if (key->cert == NULL || buffer_len(&key->cert->certblob) == 0)
 			fatal("%s: no cert/certblob", __func__);
@@ -500,6 +501,7 @@ ssh_encode_identity_ssh2(Buffer *b, Key *key, const char *comment)
 		buffer_put_bignum2(b, key->dsa->pub_key);
 		buffer_put_bignum2(b, key->dsa->priv_key);
 		break;
+	case KEY_DSA_CERT_V00:
 	case KEY_DSA_CERT:
 		if (key->cert == NULL || buffer_len(&key->cert->certblob) == 0)
 			fatal("%s: no cert/certblob", __func__);
@@ -535,8 +537,10 @@ ssh_add_identity_constrained(AuthenticationConnection *auth, Key *key,
 		break;
 	case KEY_RSA:
 	case KEY_RSA_CERT:
+	case KEY_RSA_CERT_V00:
 	case KEY_DSA:
 	case KEY_DSA_CERT:
+	case KEY_DSA_CERT_V00:
 		type = constrained ?
 		    SSH2_AGENTC_ADD_ID_CONSTRAINED :
 		    SSH2_AGENTC_ADD_IDENTITY;
diff --git a/key.c b/key.c
index 66592c7e..34f678b3 100644
--- a/key.c
+++ b/key.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: key.c,v 1.86 2010/03/15 19:40:02 stevesk Exp $ */
+/* $OpenBSD: key.c,v 1.87 2010/04/16 01:47:26 djm Exp $ */
 /*
  * read_bignum():
  * Copyright (c) 1995 Tatu Ylonen <ylo@cs.hut.fi>, Espoo, Finland
@@ -61,7 +61,8 @@ cert_new(void)
 
 	cert = xcalloc(1, sizeof(*cert));
 	buffer_init(&cert->certblob);
-	buffer_init(&cert->constraints);
+	buffer_init(&cert->critical);
+	buffer_init(&cert->extensions);
 	cert->key_id = NULL;
 	cert->principals = NULL;
 	cert->signature_key = NULL;
@@ -82,6 +83,7 @@ key_new(int type)
 	switch (k->type) {
 	case KEY_RSA1:
 	case KEY_RSA:
+	case KEY_RSA_CERT_V00:
 	case KEY_RSA_CERT:
 		if ((rsa = RSA_new()) == NULL)
 			fatal("key_new: RSA_new failed");
@@ -92,6 +94,7 @@ key_new(int type)
 		k->rsa = rsa;
 		break;
 	case KEY_DSA:
+	case KEY_DSA_CERT_V00:
 	case KEY_DSA_CERT:
 		if ((dsa = DSA_new()) == NULL)
 			fatal("key_new: DSA_new failed");
@@ -124,6 +127,7 @@ key_add_private(Key *k)
 	switch (k->type) {
 	case KEY_RSA1:
 	case KEY_RSA:
+	case KEY_RSA_CERT_V00:
 	case KEY_RSA_CERT:
 		if ((k->rsa->d = BN_new()) == NULL)
 			fatal("key_new_private: BN_new failed");
@@ -139,6 +143,7 @@ key_add_private(Key *k)
 			fatal("key_new_private: BN_new failed");
 		break;
 	case KEY_DSA:
+	case KEY_DSA_CERT_V00:
 	case KEY_DSA_CERT:
 		if ((k->dsa->priv_key = BN_new()) == NULL)
 			fatal("key_new_private: BN_new failed");
@@ -165,7 +170,8 @@ cert_free(struct KeyCert *cert)
 	u_int i;
 
 	buffer_free(&cert->certblob);
-	buffer_free(&cert->constraints);
+	buffer_free(&cert->critical);
+	buffer_free(&cert->extensions);
 	if (cert->key_id != NULL)
 		xfree(cert->key_id);
 	for (i = 0; i < cert->nprincipals; i++)
@@ -184,12 +190,14 @@ key_free(Key *k)
 	switch (k->type) {
 	case KEY_RSA1:
 	case KEY_RSA:
+	case KEY_RSA_CERT_V00:
 	case KEY_RSA_CERT:
 		if (k->rsa != NULL)
 			RSA_free(k->rsa);
 		k->rsa = NULL;
 		break;
 	case KEY_DSA:
+	case KEY_DSA_CERT_V00:
 	case KEY_DSA_CERT:
 		if (k->dsa != NULL)
 			DSA_free(k->dsa);
@@ -238,11 +246,13 @@ key_equal_public(const Key *a, const Key *b)
 
 	switch (a->type) {
 	case KEY_RSA1:
+	case KEY_RSA_CERT_V00:
 	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_V00:
 	case KEY_DSA_CERT:
 	case KEY_DSA:
 		return a->dsa != NULL && b->dsa != NULL &&
@@ -304,6 +314,8 @@ key_fingerprint_raw(Key *k, enum fp_type dgst_type, u_int *dgst_raw_length)
 	case KEY_RSA:
 		key_to_blob(k, &blob, &len);
 		break;
+	case KEY_DSA_CERT_V00:
+	case KEY_RSA_CERT_V00:
 	case KEY_DSA_CERT:
 	case KEY_RSA_CERT:
 		/* We want a fingerprint of the _key_ not of the cert */
@@ -631,6 +643,8 @@ key_read(Key *ret, char **cpp)
 	case KEY_UNSPEC:
 	case KEY_RSA:
 	case KEY_DSA:
+	case KEY_DSA_CERT_V00:
+	case KEY_RSA_CERT_V00:
 	case KEY_DSA_CERT:
 	case KEY_RSA_CERT:
 		space = strchr(cp, ' ');
@@ -757,11 +771,13 @@ key_write(const Key *key, FILE *f)
 		error("key_write: failed for RSA key");
 		return 0;
 	case KEY_DSA:
+	case KEY_DSA_CERT_V00:
 	case KEY_DSA_CERT:
 		if (key->dsa == NULL)
 			return 0;
 		break;
 	case KEY_RSA:
+	case KEY_RSA_CERT_V00:
 	case KEY_RSA_CERT:
 		if (key->rsa == NULL)
 			return 0;
@@ -793,6 +809,10 @@ key_type(const Key *k)
 		return "RSA";
 	case KEY_DSA:
 		return "DSA";
+	case KEY_RSA_CERT_V00:
+		return "RSA-CERT-V00";
+	case KEY_DSA_CERT_V00:
+		return "DSA-CERT-V00";
 	case KEY_RSA_CERT:
 		return "RSA-CERT";
 	case KEY_DSA_CERT:
@@ -822,10 +842,14 @@ key_ssh_name(const Key *k)
 		return "ssh-rsa";
 	case KEY_DSA:
 		return "ssh-dss";
-	case KEY_RSA_CERT:
+	case KEY_RSA_CERT_V00:
 		return "ssh-rsa-cert-v00@openssh.com";
-	case KEY_DSA_CERT:
+	case KEY_DSA_CERT_V00:
 		return "ssh-dss-cert-v00@openssh.com";
+	case KEY_RSA_CERT:
+		return "ssh-rsa-cert-v01@openssh.com";
+	case KEY_DSA_CERT:
+		return "ssh-dss-cert-v01@openssh.com";
 	}
 	return "ssh-unknown";
 }
@@ -836,9 +860,11 @@ key_size(const Key *k)
 	switch (k->type) {
 	case KEY_RSA1:
 	case KEY_RSA:
+	case KEY_RSA_CERT_V00:
 	case KEY_RSA_CERT:
 		return BN_num_bits(k->rsa->n);
 	case KEY_DSA:
+	case KEY_DSA_CERT_V00:
 	case KEY_DSA_CERT:
 		return BN_num_bits(k->dsa->p);
 	}
@@ -882,6 +908,8 @@ key_generate(int type, u_int bits)
 	case KEY_RSA1:
 		k->rsa = rsa_generate_private_key(bits);
 		break;
+	case KEY_RSA_CERT_V00:
+	case KEY_DSA_CERT_V00:
 	case KEY_RSA_CERT:
 	case KEY_DSA_CERT:
 		fatal("key_generate: cert keys cannot be generated directly");
@@ -912,9 +940,12 @@ key_cert_copy(const Key *from_key, struct Key *to_key)
 	buffer_append(&to->certblob, buffer_ptr(&from->certblob),
 	    buffer_len(&from->certblob));
 
-	buffer_append(&to->constraints, buffer_ptr(&from->constraints),
-	    buffer_len(&from->constraints));
+	buffer_append(&to->critical,
+	    buffer_ptr(&from->critical), buffer_len(&from->critical));
+	buffer_append(&to->extensions,
+	    buffer_ptr(&from->extensions), buffer_len(&from->extensions));
 
+	to->serial = from->serial;
 	to->type = from->type;
 	to->key_id = from->key_id == NULL ? NULL : xstrdup(from->key_id);
 	to->valid_after = from->valid_after;
@@ -940,6 +971,7 @@ key_from_private(const Key *k)
 	Key *n = NULL;
 	switch (k->type) {
 	case KEY_DSA:
+	case KEY_DSA_CERT_V00:
 	case KEY_DSA_CERT:
 		n = key_new(k->type);
 		if ((BN_copy(n->dsa->p, k->dsa->p) == NULL) ||
@@ -950,6 +982,7 @@ key_from_private(const Key *k)
 		break;
 	case KEY_RSA:
 	case KEY_RSA1:
+	case KEY_RSA_CERT_V00:
 	case KEY_RSA_CERT:
 		n = key_new(k->type);
 		if ((BN_copy(n->rsa->n, k->rsa->n) == NULL) ||
@@ -979,8 +1012,12 @@ key_type_from_name(char *name)
 	} 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;
+		return KEY_RSA_CERT_V00;
 	} else if (strcmp(name, "ssh-dss-cert-v00@openssh.com") == 0) {
+		return KEY_DSA_CERT_V00;
+	} else if (strcmp(name, "ssh-rsa-cert-v01@openssh.com") == 0) {
+		return KEY_RSA_CERT;
+	} else if (strcmp(name, "ssh-dss-cert-v01@openssh.com") == 0) {
 		return KEY_DSA_CERT;
 	}
 	debug2("key_type_from_name: unknown key type '%s'", name);
@@ -1012,26 +1049,31 @@ key_names_valid2(const char *names)
 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, kidlen;
+	u_char *principals, *critical, *exts, *sig_key, *sig;
+	u_int signed_len, plen, clen, sklen, slen, kidlen, elen;
 	Buffer tmp;
 	char *principal;
 	int ret = -1;
+	int v00 = key->type == KEY_DSA_CERT_V00 ||
+	    key->type == KEY_RSA_CERT_V00;
 
 	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 ||
+	elen = 0; /* Not touched for v00 certs */
+	principals = exts = critical = sig_key = sig = NULL;
+	if ((!v00 && buffer_get_int64_ret(&key->cert->serial, b) != 0) ||
+	    buffer_get_int_ret(&key->cert->type, b) != 0 ||
 	    (key->cert->key_id = buffer_get_string_ret(b, &kidlen)) == 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 ||
+	    (critical = buffer_get_string_ret(b, &clen)) == NULL ||
+	    (!v00 && (exts = buffer_get_string_ret(b, &elen)) == NULL) ||
+	    (v00 && buffer_get_string_ptr_ret(b, NULL) == NULL) || /* nonce */
+	    buffer_get_string_ptr_ret(b, NULL) == NULL || /* reserved */
 	    (sig_key = buffer_get_string_ret(b, &sklen)) == NULL) {
 		error("%s: parse error", __func__);
 		goto out;
@@ -1078,13 +1120,25 @@ cert_parse(Buffer *b, Key *key, const u_char *blob, u_int blen)
 
 	buffer_clear(&tmp);
 
-	buffer_append(&key->cert->constraints, constraints, clen);
-	buffer_append(&tmp, constraints, clen);
+	buffer_append(&key->cert->critical, critical, clen);
+	buffer_append(&tmp, critical, clen);
 	/* validate structure */
 	while (buffer_len(&tmp) != 0) {
 		if (buffer_get_string_ptr_ret(&tmp, NULL) == NULL ||
 		    buffer_get_string_ptr_ret(&tmp, NULL) == NULL) {
-			error("%s: Constraints data invalid", __func__);
+			error("%s: critical option data invalid", __func__);
+			goto out;
+		}
+	}
+	buffer_clear(&tmp);
+
+	buffer_append(&key->cert->extensions, exts, elen);
+	buffer_append(&tmp, exts, elen);
+	/* validate structure */
+	while (buffer_len(&tmp) != 0) {
+		if (buffer_get_string_ptr_ret(&tmp, NULL) == NULL ||
+		    buffer_get_string_ptr_ret(&tmp, NULL) == NULL) {
+			error("%s: extension data invalid", __func__);
 			goto out;
 		}
 	}
@@ -1121,8 +1175,10 @@ cert_parse(Buffer *b, Key *key, const u_char *blob, u_int blen)
 	buffer_free(&tmp);
 	if (principals != NULL)
 		xfree(principals);
-	if (constraints != NULL)
-		xfree(constraints);
+	if (critical != NULL)
+		xfree(critical);
+	if (exts != NULL)
+		xfree(exts);
 	if (sig_key != NULL)
 		xfree(sig_key);
 	if (sig != NULL)
@@ -1151,8 +1207,11 @@ key_from_blob(const u_char *blob, u_int blen)
 	type = key_type_from_name(ktype);
 
 	switch (type) {
-	case KEY_RSA:
 	case KEY_RSA_CERT:
+		(void)buffer_get_string_ptr_ret(&b, NULL); /* Skip nonce */
+		/* FALLTHROUGH */
+	case KEY_RSA:
+	case KEY_RSA_CERT_V00:
 		key = key_new(type);
 		if (buffer_get_bignum2_ret(&b, key->rsa->e) == -1 ||
 		    buffer_get_bignum2_ret(&b, key->rsa->n) == -1) {
@@ -1166,8 +1225,11 @@ key_from_blob(const u_char *blob, u_int blen)
 		RSA_print_fp(stderr, key->rsa, 8);
 #endif
 		break;
-	case KEY_DSA:
 	case KEY_DSA_CERT:
+		(void)buffer_get_string_ptr_ret(&b, NULL); /* Skip nonce */
+		/* FALLTHROUGH */
+	case KEY_DSA:
+	case KEY_DSA_CERT_V00:
 		key = key_new(type);
 		if (buffer_get_bignum2_ret(&b, key->dsa->p) == -1 ||
 		    buffer_get_bignum2_ret(&b, key->dsa->q) == -1 ||
@@ -1213,6 +1275,8 @@ key_to_blob(const Key *key, u_char **blobp, u_int *lenp)
 	}
 	buffer_init(&b);
 	switch (key->type) {
+	case KEY_DSA_CERT_V00:
+	case KEY_RSA_CERT_V00:
 	case KEY_DSA_CERT:
 	case KEY_RSA_CERT:
 		/* Use the existing blob */
@@ -1255,9 +1319,11 @@ key_sign(
     const u_char *data, u_int datalen)
 {
 	switch (key->type) {
+	case KEY_DSA_CERT_V00:
 	case KEY_DSA_CERT:
 	case KEY_DSA:
 		return ssh_dss_sign(key, sigp, lenp, data, datalen);
+	case KEY_RSA_CERT_V00:
 	case KEY_RSA_CERT:
 	case KEY_RSA:
 		return ssh_rsa_sign(key, sigp, lenp, data, datalen);
@@ -1281,9 +1347,11 @@ key_verify(
 		return -1;
 
 	switch (key->type) {
+	case KEY_DSA_CERT_V00:
 	case KEY_DSA_CERT:
 	case KEY_DSA:
 		return ssh_dss_verify(key, signature, signaturelen, data, datalen);
+	case KEY_RSA_CERT_V00:
 	case KEY_RSA_CERT:
 	case KEY_RSA:
 		return ssh_rsa_verify(key, signature, signaturelen, data, datalen);
@@ -1306,6 +1374,7 @@ key_demote(const Key *k)
 	pk->rsa = NULL;
 
 	switch (k->type) {
+	case KEY_RSA_CERT_V00:
 	case KEY_RSA_CERT:
 		key_cert_copy(k, pk);
 		/* FALLTHROUGH */
@@ -1318,6 +1387,7 @@ 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_V00:
 	case KEY_DSA_CERT:
 		key_cert_copy(k, pk);
 		/* FALLTHROUGH */
@@ -1344,8 +1414,17 @@ key_demote(const Key *k)
 int
 key_is_cert(const Key *k)
 {
-	return k != NULL &&
-	    (k->type == KEY_RSA_CERT || k->type == KEY_DSA_CERT);
+	if (k == NULL)
+		return 0;
+	switch (k->type) {
+	case KEY_RSA_CERT_V00:
+	case KEY_DSA_CERT_V00:
+	case KEY_RSA_CERT:
+	case KEY_DSA_CERT:
+		return 1;
+	default:
+		return 0;
+	}
 }
 
 /* Return the cert-less equivalent to a certified key type */
@@ -1353,8 +1432,10 @@ int
 key_type_plain(int type)
 {
 	switch (type) {
+	case KEY_RSA_CERT_V00:
 	case KEY_RSA_CERT:
 		return KEY_RSA;
+	case KEY_DSA_CERT_V00:
 	case KEY_DSA_CERT:
 		return KEY_DSA;
 	default:
@@ -1364,16 +1445,16 @@ key_type_plain(int type)
 
 /* Convert a KEY_RSA or KEY_DSA to their _CERT equivalent */
 int
-key_to_certified(Key *k)
+key_to_certified(Key *k, int legacy)
 {
 	switch (k->type) {
 	case KEY_RSA:
 		k->cert = cert_new();
-		k->type = KEY_RSA_CERT;
+		k->type = legacy ? KEY_RSA_CERT_V00 : KEY_RSA_CERT;
 		return 0;
 	case KEY_DSA:
 		k->cert = cert_new();
-		k->typ