- 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@
diff --git a/ChangeLog b/ChangeLog
index fd4ce5d..b058de0 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 1ed9e20..a2069f5 100644
--- a/PROTOCOL.certkeys
+++ b/PROTOCOL.certkeys
@@ -16,7 +16,7 @@
 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 @@
 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 @@
 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 @@
 
 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 @@
 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 @@
 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 @@
 
 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 69b314f..60d5f74 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 @@
 }
 
 /*
- * 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 @@
 
 	/* 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 @@
 			}
 			if (cert_forced_command != NULL) {
 				error("Certificate has multiple "
-				    "force-command constraints");
+				    "force-command options");
 				xfree(command);
 				goto out;
 			}
@@ -459,7 +460,7 @@
 			}
 			if (cert_source_address_done++) {
 				error("Certificate has multiple "
-				    "source-address constraints");
+				    "source-address options");
 				xfree(allowed);
 				goto out;
 			}
@@ -502,7 +503,7 @@
 		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 694edc8..20f0dbe 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 @@
 
 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 65571a8..326937a 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 c4cadf4..83ecd65 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 @@
 		}
 		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 @@
 				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 @@
 		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 28a8cf2..739722f 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 @@
 		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 @@
 		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 @@
 		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 66592c7..34f678b 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 = 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 @@
 	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 @@
 		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 @@
 	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 @@
 			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 @@
 	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 @@
 	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 @@
 
 	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 @@
 	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 @@
 	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 @@
 		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 @@
 		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 @@
 		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 @@
 	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 @@
 	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 @@
 	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 *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 @@
 		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 @@
 	} 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 @@
 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 @@
 
 	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 @@
 	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 @@
 	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 @@
 		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 @@
 	}
 	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 @@
     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 @@
 		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 @@
 	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 @@
 		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 @@
 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 @@
 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 @@
 
 /* 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->type = KEY_DSA_CERT;
+		k->type = legacy ? KEY_DSA_CERT_V00 : KEY_DSA_CERT;
 		return 0;
 	default:
 		error("%s: key has incorrect type %s", __func__, key_type(k));
@@ -1386,10 +1467,12 @@
 key_drop_cert(Key *k)
 {
 	switch (k->type) {
+	case KEY_RSA_CERT_V00:
 	case KEY_RSA_CERT:
 		cert_free(k->cert);
 		k->type = KEY_RSA;
 		return 0;
+	case KEY_DSA_CERT_V00:
 	case KEY_DSA_CERT:
 		cert_free(k->cert);
 		k->type = KEY_DSA;
@@ -1430,13 +1513,21 @@
 	buffer_clear(&k->cert->certblob);
 	buffer_put_cstring(&k->cert->certblob, key_ssh_name(k));
 
+	/* -v01 certs put nonce first */
+	if (k->type == KEY_DSA_CERT || k->type == KEY_RSA_CERT) {
+		arc4random_buf(&nonce, sizeof(nonce));
+		buffer_put_string(&k->cert->certblob, nonce, sizeof(nonce));
+	}
+
 	switch (k->type) {
+	case KEY_DSA_CERT_V00:
 	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_V00:
 	case KEY_RSA_CERT:
 		buffer_put_bignum2(&k->cert->certblob, k->rsa->e);
 		buffer_put_bignum2(&k->cert->certblob, k->rsa->n);
@@ -1448,6 +1539,10 @@
 		return -1;
 	}
 
+	/* -v01 certs have a serial number next */
+	if (k->type == KEY_DSA_CERT || k->type == KEY_RSA_CERT)
+		buffer_put_int64(&k->cert->certblob, k->cert->serial);
+
 	buffer_put_int(&k->cert->certblob, k->cert->type);
 	buffer_put_cstring(&k->cert->certblob, k->cert->key_id);
 
@@ -1461,11 +1556,19 @@
 	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));
+	    buffer_ptr(&k->cert->critical), buffer_len(&k->cert->critical));
 
-	arc4random_buf(&nonce, sizeof(nonce));
-	buffer_put_string(&k->cert->certblob, nonce, sizeof(nonce));
+	/* -v01 certs have non-critical options here */
+	if (k->type == KEY_DSA_CERT || k->type == KEY_RSA_CERT) {
+		buffer_put_string(&k->cert->certblob,
+		    buffer_ptr(&k->cert->extensions),
+		    buffer_len(&k->cert->extensions));
+	}
+
+	/* -v00 certs put the nonce at the end */
+	if (k->type == KEY_DSA_CERT_V00 || k->type == KEY_RSA_CERT_V00)
+		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);
@@ -1536,3 +1639,15 @@
 	}
 	return 0;
 }
+
+int
+key_cert_is_legacy(Key *k)
+{
+	switch (k->type) {
+	case KEY_DSA_CERT_V00:
+	case KEY_RSA_CERT_V00:
+		return 1;
+	default:
+		return 0;
+	}
+}
diff --git a/key.h b/key.h
index 4f17777..11d30ea 100644
--- a/key.h
+++ b/key.h
@@ -1,4 +1,4 @@
-/* $OpenBSD: key.h,v 1.29 2010/03/15 19:40:02 stevesk Exp $ */
+/* $OpenBSD: key.h,v 1.30 2010/04/16 01:47:26 djm Exp $ */
 
 /*
  * Copyright (c) 2000, 2001 Markus Friedl.  All rights reserved.
@@ -37,6 +37,8 @@
 	KEY_DSA,
 	KEY_RSA_CERT,
 	KEY_DSA_CERT,
+	KEY_RSA_CERT_V00,
+	KEY_DSA_CERT_V00,
 	KEY_UNSPEC
 };
 enum fp_type {
@@ -56,11 +58,13 @@
 struct KeyCert {
 	Buffer		 certblob; /* Kept around for use on wire */
 	u_int		 type; /* SSH2_CERT_TYPE_USER or SSH2_CERT_TYPE_HOST */
+	u_int64_t	 serial;
 	char		*key_id;
 	u_int		 nprincipals;
 	char		**principals;
 	u_int64_t	 valid_after, valid_before;
-	Buffer		 constraints;
+	Buffer		 critical;
+	Buffer		 extensions;
 	Key		*signature_key;
 };
 
@@ -92,12 +96,13 @@
 int	 key_type_from_name(char *);
 int	 key_is_cert(const Key *);
 int	 key_type_plain(int);
-int	 key_to_certified(Key *);
+int	 key_to_certified(Key *, int);
 int	 key_drop_cert(Key *);
 int	 key_certify(Key *, Key *);
 void	 key_cert_copy(const Key *, struct Key *);
 int	 key_cert_check_authority(const Key *, int, int, const char *,
 	    const char **);
+int	 key_cert_is_legacy(Key *);
 
 Key		*key_from_blob(const u_char *, u_int);
 int		 key_to_blob(const Key *, u_char **, u_int *);
diff --git a/myproposal.h b/myproposal.h
index 98f27fd..7bedfab 100644
--- a/myproposal.h
+++ b/myproposal.h
@@ -1,4 +1,4 @@
-/* $OpenBSD: myproposal.h,v 1.24 2010/02/26 20:29:54 djm Exp $ */
+/* $OpenBSD: myproposal.h,v 1.25 2010/04/16 01:47:26 djm Exp $ */
 
 /*
  * Copyright (c) 2000 Markus Friedl.  All rights reserved.
@@ -40,9 +40,12 @@
 	"diffie-hellman-group1-sha1"
 #endif
 
-#define	KEX_DEFAULT_PK_ALG	"ssh-rsa-cert-v00@openssh.com," \
-				"ssh-dss-cert-v00@openssh.com," \
-				"ssh-rsa,ssh-dss"
+#define	KEX_DEFAULT_PK_ALG	\
+				"ssh-rsa-cert-v01@openssh.com," \
+				"ssh-dss-cert-v01@openssh.com," \
+				"ssh-rsa-cert-v00@openssh.com," \
+ 				"ssh-dss-cert-v00@openssh.com," \
+ 				"ssh-rsa,ssh-dss"
 
 #define	KEX_DEFAULT_ENCRYPT \
 	"aes128-ctr,aes192-ctr,aes256-ctr," \
diff --git a/ssh-add.c b/ssh-add.c
index ad9f7a8..cba1078 100644
--- a/ssh-add.c
+++ b/ssh-add.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: ssh-add.c,v 1.94 2010/03/01 11:07:06 otto Exp $ */
+/* $OpenBSD: ssh-add.c,v 1.95 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
@@ -204,7 +204,7 @@
 	xasprintf(&certpath, "%s-cert.pub", filename);
 	if ((cert = key_load_public(certpath, NULL)) != NULL) {
 		/* Graft with private bits */
-		if (key_to_certified(private) != 0)
+		if (key_to_certified(private, key_cert_is_legacy(cert)) != 0)
 			fatal("%s: key_to_certified failed", __func__);
 		key_cert_copy(cert, private);
 		key_free(cert);
diff --git a/ssh-agent.c b/ssh-agent.c
index b5c5652..2c0e286 100644
--- a/ssh-agent.c
+++ b/ssh-agent.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: ssh-agent.c,v 1.165 2010/02/26 20:29:54 djm Exp $ */
+/* $OpenBSD: ssh-agent.c,v 1.166 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
@@ -500,6 +500,7 @@
 			buffer_get_bignum2(&e->request, k->dsa->pub_key);
 			buffer_get_bignum2(&e->request, k->dsa->priv_key);
 			break;
+		case KEY_DSA_CERT_V00:
 		case KEY_DSA_CERT:
 			cert = buffer_get_string(&e->request, &len);
 			if ((k = key_from_blob(cert, len)) == NULL)
@@ -520,6 +521,7 @@
 			/* Generate additional parameters */
 			rsa_generate_additional_parameters(k->rsa);
 			break;
+		case KEY_RSA_CERT_V00:
 		case KEY_RSA_CERT:
 			cert = buffer_get_string(&e->request, &len);
 			if ((k = key_from_blob(cert, len)) == NULL)
@@ -540,6 +542,7 @@
 	/* enable blinding */
 	switch (k->type) {
 	case KEY_RSA:
+	case KEY_RSA_CERT_V00:
 	case KEY_RSA_CERT:
 	case KEY_RSA1:
 		if (RSA_blinding_on(k->rsa, NULL) != 1) {
diff --git a/ssh-dss.c b/ssh-dss.c
index 449f493..175e4d0 100644
--- a/ssh-dss.c
+++ b/ssh-dss.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: ssh-dss.c,v 1.25 2010/02/26 20:29:54 djm Exp $ */
+/* $OpenBSD: ssh-dss.c,v 1.26 2010/04/16 01:47:26 djm Exp $ */
 /*
  * Copyright (c) 2000 Markus Friedl.  All rights reserved.
  *
@@ -53,9 +53,8 @@
 	u_int rlen, slen, len, dlen;
 	Buffer b;
 
-	if (key == NULL ||
-	    (key->type != KEY_DSA && key->type != KEY_DSA_CERT) ||
-	    key->dsa == NULL) {
+	if (key == NULL || key->dsa == NULL || (key->type != KEY_DSA &&
+	    key->type != KEY_DSA_CERT && key->type != KEY_DSA_CERT_V00)) {
 		error("ssh_dss_sign: no DSA key");
 		return -1;
 	}
@@ -118,9 +117,8 @@
 	int rlen, ret;
 	Buffer b;
 
-	if (key == NULL ||
-	    (key->type != KEY_DSA && key->type != KEY_DSA_CERT) ||
-	    key->dsa == NULL) {
+	if (key == NULL || key->dsa == NULL || (key->type != KEY_DSA &&
+	    key->type != KEY_DSA_CERT && key->type != KEY_DSA_CERT_V00)) {
 		error("ssh_dss_verify: no DSA key");
 		return -1;
 	}
diff --git a/ssh-keygen.1 b/ssh-keygen.1
index 3e03a9b..aacd4d3 100644
--- a/ssh-keygen.1
+++ b/ssh-keygen.1
@@ -1,4 +1,4 @@
-.\"	$OpenBSD: ssh-keygen.1,v 1.92 2010/03/13 23:38:13 jmc Exp $
+.\"	$OpenBSD: ssh-keygen.1,v 1.93 2010/04/16 01:47:26 djm Exp $
 .\"
 .\"  -*- nroff -*-
 .\"
@@ -37,7 +37,7 @@
 .\" (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 .\" THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 .\"
-.Dd $Mdocdate: March 13 2010 $
+.Dd $Mdocdate: April 16 2010 $
 .Dt SSH-KEYGEN 1
 .Os
 .Sh NAME
@@ -110,8 +110,9 @@
 .Fl I Ar certificate_identity
 .Op Fl h
 .Op Fl n Ar principals
-.Op Fl O Ar constraint
+.Op Fl O Ar option
 .Op Fl V Ar validity_interval
+.Op Fl z Ar serial_number
 .Ar
 .Nm ssh-keygen
 .Fl L
@@ -299,13 +300,13 @@
 Please see the
 .Sx CERTIFICATES
 section for details.
-.It Fl O Ar constraint
-Specify a certificate constraint when signing a key.
+.It Fl O Ar option
+Specify a certificate option when signing a key.
 This option may be specified multiple times.
 Please see the
 .Sx CERTIFICATES
 section for details.
-The constraints that are valid for user certificates are:
+The options that are valid for user certificates are:
 .Bl -tag -width Ds
 .It Ic clear
 Clear all enabled permissions.
@@ -355,7 +356,7 @@
 format.
 .El
 .Pp
-At present, no constraints are valid for host keys.
+At present, no options are valid for host keys.
 .It Fl P Ar passphrase
 Provides the (old) passphrase.
 .It Fl p
@@ -441,6 +442,10 @@
 .It Fl y
 This option will read a private
 OpenSSH format file and print an OpenSSH public key to stdout.
+.It Fl z Ar serial_number
+Specifies a serial number to be embedded in the certificate to distinguish
+this certificate from others from the same CA.
+The default serial number is zero.
 .El
 .Sh MODULI GENERATION
 .Nm
@@ -501,7 +506,7 @@
 supports signing of keys to produce certificates that may be used for
 user or host authentication.
 Certificates consist of a public key, some identity information, zero or
-more principal (user or host) names and an optional set of constraints that
+more principal (user or host) names and an optional set of options that
 are signed by a Certification Authority (CA) key.
 Clients or servers may then trust only the CA key and verify its signature
 on a certificate rather than trusting many user/host keys.
@@ -541,11 +546,11 @@
 .Dl "$ ssh-keygen -s ca_key -I key_id -h -n host.domain user_key.pub"
 .Pp
 Additional limitations on the validity and use of user certificates may
-be specified through certificate constraints.
-A constrained certificate may disable features of the SSH session, may be
+be specified through certificate options..
+A certificate option may disable features of the SSH session, may be
 valid only when presented from particular source addresses or may
 force the use of a specific command.
-For a list of valid certificate constraints, see the documentation for the
+For a list of valid certificate options, see the documentation for the
 .Fl O
 option above.
 .Pp
diff --git a/ssh-keygen.c b/ssh-keygen.c
index 37e516f..8938dc0 100644
--- a/ssh-keygen.c
+++ b/ssh-keygen.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: ssh-keygen.c,v 1.185 2010/03/15 19:40:02 stevesk Exp $ */
+/* $OpenBSD: ssh-keygen.c,v 1.186 2010/04/16 01:47:26 djm Exp $ */
 /*
  * Author: Tatu Ylonen <ylo@cs.hut.fi>
  * Copyright (c) 1994 Tatu Ylonen <ylo@cs.hut.fi>, Espoo, Finland
@@ -105,6 +105,9 @@
 /* Path to CA key when certifying keys. */
 char *ca_key_path = NULL;
 
+/* Certificate serial number */
+long long cert_serial = 0;
+
 /* Key type when certifying */
 u_int cert_key_type = SSH2_CERT_TYPE_USER;
 
@@ -118,18 +121,18 @@
 u_int64_t cert_valid_from = 0;
 u_int64_t cert_valid_to = ~0ULL;
 
-/* Certificate constraints */
-#define CONSTRAINT_X_FWD	(1)
-#define CONSTRAINT_AGENT_FWD	(1<<1)
-#define CONSTRAINT_PORT_FWD	(1<<2)
-#define CONSTRAINT_PTY		(1<<3)
-#define CONSTRAINT_USER_RC	(1<<4)
-#define CONSTRAINT_DEFAULT	(CONSTRAINT_X_FWD|CONSTRAINT_AGENT_FWD| \
-				CONSTRAINT_PORT_FWD|CONSTRAINT_PTY| \
-				CONSTRAINT_USER_RC)
-u_int32_t constraint_flags = CONSTRAINT_DEFAULT;
-char *constraint_command = NULL;
-char *constraint_src_addr = NULL;
+/* Certificate options */
+#define CRITOPT_X_FWD	(1)
+#define CRITOPT_AGENT_FWD	(1<<1)
+#define CRITOPT_PORT_FWD	(1<<2)
+#define CRITOPT_PTY		(1<<3)
+#define CRITOPT_USER_RC	(1<<4)
+#define CRITOPT_DEFAULT	(CRITOPT_X_FWD|CRITOPT_AGENT_FWD| \
+				CRITOPT_PORT_FWD|CRITOPT_PTY| \
+				CRITOPT_USER_RC)
+u_int32_t critical_flags = CRITOPT_DEFAULT;
+char *critical_command = NULL;
+char *critical_src_addr = NULL;
 
 /* Dump public key file in format used by real and the original SSH 2 */
 int convert_to_ssh2 = 0;
@@ -161,9 +164,13 @@
 		case KEY_RSA1:
 			name = _PATH_SSH_CLIENT_IDENTITY;
 			break;
+		case KEY_DSA_CERT:
+		case KEY_DSA_CERT_V00:
 		case KEY_DSA:
 			name = _PATH_SSH_CLIENT_ID_DSA;
 			break;
+		case KEY_RSA_CERT:
+		case KEY_RSA_CERT_V00:
 		case KEY_RSA:
 			name = _PATH_SSH_CLIENT_ID_RSA;
 			break;
@@ -1104,7 +1111,7 @@
 }
 
 static void
-add_flag_constraint(Buffer *c, const char *name)
+add_flag_option(Buffer *c, const char *name)
 {
 	debug3("%s: %s", __func__, name);
 	buffer_put_cstring(c, name);
@@ -1112,7 +1119,7 @@
 }
 
 static void
-add_string_constraint(Buffer *c, const char *name, const char *value)
+add_string_option(Buffer *c, const char *name, const char *value)
 {
 	Buffer b;
 
@@ -1127,24 +1134,23 @@
 }
 
 static void
-prepare_constraint_buf(Buffer *c)
+prepare_options_buf(Buffer *c)
 {
-
 	buffer_clear(c);
-	if ((constraint_flags & CONSTRAINT_X_FWD) != 0)
-		add_flag_constraint(c, "permit-X11-forwarding");
-	if ((constraint_flags & CONSTRAINT_AGENT_FWD) != 0)
-		add_flag_constraint(c, "permit-agent-forwarding");
-	if ((constraint_flags & CONSTRAINT_PORT_FWD) != 0)
-		add_flag_constraint(c, "permit-port-forwarding");
-	if ((constraint_flags & CONSTRAINT_PTY) != 0)
-		add_flag_constraint(c, "permit-pty");
-	if ((constraint_flags & CONSTRAINT_USER_RC) != 0)
-		add_flag_constraint(c, "permit-user-rc");
-	if (constraint_command != NULL)
-		add_string_constraint(c, "force-command", constraint_command);
-	if (constraint_src_addr != NULL)
-		add_string_constraint(c, "source-address", constraint_src_addr);
+	if ((critical_flags & CRITOPT_X_FWD) != 0)
+		add_flag_option(c, "permit-X11-forwarding");
+	if ((critical_flags & CRITOPT_AGENT_FWD) != 0)
+		add_flag_option(c, "permit-agent-forwarding");
+	if ((critical_flags & CRITOPT_PORT_FWD) != 0)
+		add_flag_option(c, "permit-port-forwarding");
+	if ((critical_flags & CRITOPT_PTY) != 0)
+		add_flag_option(c, "permit-pty");
+	if ((critical_flags & CRITOPT_USER_RC) != 0)
+		add_flag_option(c, "permit-user-rc");
+	if (critical_command != NULL)
+		add_string_option(c, "force-command", critical_command);
+	if (critical_src_addr != NULL)
+		add_string_option(c, "source-address", critical_src_addr);
 }
 
 static void
@@ -1155,12 +1161,32 @@
 	Key *ca, *public;
 	char *otmp, *tmp, *cp, *out, *comment, **plist = NULL;
 	FILE *f;
+	int v00 = 0; /* legacy keys */
 
 	tmp = tilde_expand_filename(ca_key_path, pw->pw_uid);
 	if ((ca = load_identity(tmp)) == NULL)
 		fatal("Couldn't load CA key \"%s\"", tmp);
 	xfree(tmp);
 
+	if (key_type_name != NULL) {
+		switch (key_type_from_name(key_type_name)) {
+		case KEY_RSA_CERT_V00:
+		case KEY_DSA_CERT_V00:
+			v00 = 1;
+			break;
+		case KEY_UNSPEC:
+			if (strcasecmp(key_type_name, "v00") == 0) {
+				v00 = 1;
+				break;
+			} else if (strcasecmp(key_type_name, "v01") == 0)
+				break;
+			/* FALLTHROUGH */
+		default:
+			fprintf(stderr, "unknown key type %s\n", key_type_name);
+			exit(1);
+		}
+	}
+
 	for (i = 0; i < argc; i++) {
 		/* Split list of principals */
 		n = 0;
@@ -1183,15 +1209,16 @@
 			    __func__, tmp, key_type(public));
 
 		/* Prepare certificate to sign */
-		if (key_to_certified(public) != 0)
+		if (key_to_certified(public, v00) != 0)
 			fatal("Could not upgrade key %s to certificate", tmp);
 		public->cert->type = cert_key_type;
+		public->cert->serial = (u_int64_t)cert_serial;
 		public->cert->key_id = xstrdup(cert_key_id);
 		public->cert->nprincipals = n;
 		public->cert->principals = plist;
 		public->cert->valid_after = cert_valid_from;
 		public->cert->valid_before = cert_valid_to;
-		prepare_constraint_buf(&public->cert->constraints);
+		prepare_options_buf(&public->cert->critical);
 		public->cert->signature_key = key_from_private(ca);
 
 		if (key_certify(public, ca) != 0)
@@ -1212,13 +1239,14 @@
 		fprintf(f, " %s\n", comment);
 		fclose(f);
 
-		if (!quiet)
-			logit("Signed %s key %s: id \"%s\"%s%s valid %s",
-			    cert_key_type == SSH2_CERT_TYPE_USER?"user":"host",
-			    out, cert_key_id,
+		if (!quiet) {
+			logit("Signed %s key %s: id \"%s\" serial %llu%s%s "
+			    "valid %s", key_cert_type(public), 
+			    out, public->cert->key_id, public->cert->serial,
 			    cert_principals != NULL ? " for " : "",
 			    cert_principals != NULL ? cert_principals : "",
 			    fmt_validity(cert_valid_from, cert_valid_to));
+		}
 
 		key_free(public);
 		xfree(out);
@@ -1321,50 +1349,50 @@
 }
 
 static void
-add_cert_constraint(char *opt)
+add_cert_option(char *opt)
 {
 	char *val;
 
 	if (strcmp(opt, "clear") == 0)
-		constraint_flags = 0;
+		critical_flags = 0;
 	else if (strcasecmp(opt, "no-x11-forwarding") == 0)
-		constraint_flags &= ~CONSTRAINT_X_FWD;
+		critical_flags &= ~CRITOPT_X_FWD;
 	else if (strcasecmp(opt, "permit-x11-forwarding") == 0)
-		constraint_flags |= CONSTRAINT_X_FWD;
+		critical_flags |= CRITOPT_X_FWD;
 	else if (strcasecmp(opt, "no-agent-forwarding") == 0)
-		constraint_flags &= ~CONSTRAINT_AGENT_FWD;
+		critical_flags &= ~CRITOPT_AGENT_FWD;
 	else if (strcasecmp(opt, "permit-agent-forwarding") == 0)
-		constraint_flags |= CONSTRAINT_AGENT_FWD;
+		critical_flags |= CRITOPT_AGENT_FWD;
 	else if (strcasecmp(opt, "no-port-forwarding") == 0)
-		constraint_flags &= ~CONSTRAINT_PORT_FWD;
+		critical_flags &= ~CRITOPT_PORT_FWD;
 	else if (strcasecmp(opt, "permit-port-forwarding") == 0)
-		constraint_flags |= CONSTRAINT_PORT_FWD;
+		critical_flags |= CRITOPT_PORT_FWD;
 	else if (strcasecmp(opt, "no-pty") == 0)
-		constraint_flags &= ~CONSTRAINT_PTY;
+		critical_flags &= ~CRITOPT_PTY;
 	else if (strcasecmp(opt, "permit-pty") == 0)
-		constraint_flags |= CONSTRAINT_PTY;
+		critical_flags |= CRITOPT_PTY;
 	else if (strcasecmp(opt, "no-user-rc") == 0)
-		constraint_flags &= ~CONSTRAINT_USER_RC;
+		critical_flags &= ~CRITOPT_USER_RC;
 	else if (strcasecmp(opt, "permit-user-rc") == 0)
-		constraint_flags |= CONSTRAINT_USER_RC;
+		critical_flags |= CRITOPT_USER_RC;
 	else if (strncasecmp(opt, "force-command=", 14) == 0) {
 		val = opt + 14;
 		if (*val == '\0')
-			fatal("Empty force-command constraint");
-		if (constraint_command != NULL)
+			fatal("Empty force-command option");
+		if (critical_command != NULL)
 			fatal("force-command already specified");
-		constraint_command = xstrdup(val);
+		critical_command = xstrdup(val);
 	} else if (strncasecmp(opt, "source-address=", 15) == 0) {
 		val = opt + 15;
 		if (*val == '\0')
-			fatal("Empty source-address constraint");
-		if (constraint_src_addr != NULL)
+			fatal("Empty source-address option");
+		if (critical_src_addr != NULL)
 			fatal("source-address already specified");
 		if (addr_match_cidr_list(NULL, val) != 0)
 			fatal("Invalid source-address list");
-		constraint_src_addr = xstrdup(val);
+		critical_src_addr = xstrdup(val);
 	} else
-		fatal("Unsupported certificate constraint \"%s\"", opt);
+		fatal("Unsupported certificate option \"%s\"", opt);
 }
 
 static void
@@ -1373,9 +1401,9 @@
 	Key *key;
 	struct stat st;
 	char *key_fp, *ca_fp;
-	Buffer constraints, constraint;
+	Buffer options, option;
 	u_char *name, *data;
-	u_int i, dlen;
+	u_int i, dlen, v00;
 
 	if (!have_identity)
 		ask_filename(pw, "Enter file in which the key is");
@@ -1387,17 +1415,21 @@
 		fatal("%s is not a public key", identity_file);
 	if (!key_is_cert(key))
 		fatal("%s is not a certificate", identity_file);
-	
+	v00 = key->type == KEY_RSA_CERT_V00 || key->type == KEY_DSA_CERT_V00;
+
 	key_fp = key_fingerprint(key, SSH_FP_MD5, SSH_FP_HEX);
 	ca_fp = key_fingerprint(key->cert->signature_key,
 	    SSH_FP_MD5, SSH_FP_HEX);
 
 	printf("%s:\n", identity_file);
-	printf("        %s %s certificate %s\n", key_type(key),
-	    key_cert_type(key), key_fp);
-	printf("        Signed by %s CA %s\n",
+	printf("        Type: %s %s certificate\n", key_ssh_name(key),
+	    key_cert_type(key));
+	printf("        Public key: %s %s\n", key_type(key), key_fp);
+	printf("        Signing CA: %s %s\n",
 	    key_type(key->cert->signature_key), ca_fp);
-	printf("        Key ID \"%s\"\n", key->cert->key_id);
+	printf("        Key ID: \"%s\"\n", key->cert->key_id);
+	if (!v00)
+		printf("        Serial: %llu\n", key->cert->serial);
 	printf("        Valid: %s\n",
 	    fmt_validity(key->cert->valid_after, key->cert->valid_before));
 	printf("        Principals: ");
@@ -1409,20 +1441,20 @@
 			    key->cert->principals[i]);
 		printf("\n");
 	}
-	printf("        Constraints: ");
-	if (buffer_len(&key->cert->constraints) == 0)
+	printf("        Critical Options: ");
+	if (buffer_len(&key->cert->critical) == 0)
 		printf("(none)\n");
 	else {
 		printf("\n");
-		buffer_init(&constraints);
-		buffer_append(&constraints,
-		    buffer_ptr(&key->cert->constraints),
-		    buffer_len(&key->cert->constraints));
-		buffer_init(&constraint);
-		while (buffer_len(&constraints) != 0) {
-			name = buffer_get_string(&constraints, NULL);
-			data = buffer_get_string_ptr(&constraints, &dlen);
-			buffer_append(&constraint, data, dlen);
+		buffer_init(&options);
+		buffer_append(&options,
+		    buffer_ptr(&key->cert->critical),
+		    buffer_len(&key->cert->critical));
+		buffer_init(&option);
+		while (buffer_len(&options) != 0) {
+			name = buffer_get_string(&options, NULL);
+			data = buffer_get_string_ptr(&options, &dlen);
+			buffer_append(&option, data, dlen);
 			printf("                %s", name);
 			if (strcmp(name, "permit-X11-forwarding") == 0 ||
 			    strcmp(name, "permit-agent-forwarding") == 0 ||
@@ -1432,22 +1464,43 @@
 				printf("\n");
 			else if (strcmp(name, "force-command") == 0 ||
 			    strcmp(name, "source-address") == 0) {
-				data = buffer_get_string(&constraint, NULL);
+				data = buffer_get_string(&option, NULL);
 				printf(" %s\n", data);
 				xfree(data);
 			} else {
-				printf(" UNKNOWN CONSTRAINT (len %u)\n",
-				    buffer_len(&constraint));
-				buffer_clear(&constraint);
+				printf(" UNKNOWN OPTION (len %u)\n",
+				    buffer_len(&option));
+				buffer_clear(&option);
 			}
 			xfree(name);
-			if (buffer_len(&constraint) != 0)
-				fatal("Constraint corrupt: extra data at end");
+			if (buffer_len(&option) != 0)
+				fatal("Option corrupt: extra data at end");
 		}
-		buffer_free(&constraint);
-		buffer_free(&constraints);
+		buffer_free(&option);
+		buffer_free(&options);
 	}
-
+	if (!v00) {
+		printf("        Extensions: ");
+		if (buffer_len(&key->cert->extensions) == 0)
+			printf("(none)\n");
+		else {
+			printf("\n");
+			buffer_init(&options);
+			buffer_append(&options,
+			    buffer_ptr(&key->cert->extensions),
+			    buffer_len(&key->cert->extensions));
+			buffer_init(&option);
+			while (buffer_len(&options) != 0) {
+				name = buffer_get_string(&options, NULL);
+				(void)buffer_get_string_ptr(&options, &dlen);
+				printf("                %s UNKNOWN OPTION "
+				    "(len %u)\n", name, dlen);
+				xfree(name);
+			}
+			buffer_free(&option);
+			buffer_free(&options);
+		}
+	}
 	exit(0);
 }
 
@@ -1478,7 +1531,7 @@
 	fprintf(stderr, "  -M memory   Amount of memory (MB) to use for generating DH-GEX moduli.\n");
 	fprintf(stderr, "  -n name,... User/host principal names to include in certificate\n");
 	fprintf(stderr, "  -N phrase   Provide new passphrase.\n");
-	fprintf(stderr, "  -O cnstr    Specify a certificate constraint.\n");
+	fprintf(stderr, "  -O cnstr    Specify a certificate option.\n");
 	fprintf(stderr, "  -P phrase   Provide old passphrase.\n");
 	fprintf(stderr, "  -p          Change passphrase of private key file.\n");
 	fprintf(stderr, "  -q          Quiet.\n");
@@ -1541,7 +1594,7 @@
 	}
 
 	while ((opt = getopt(argc, argv, "degiqpclBHLhvxXyF:b:f:t:D:I:P:N:n:"
-	    "O:C:r:g:R:T:G:M:S:s:a:V:W:")) != -1) {
+	    "O:C:r:g:R:T:G:M:S:s:a:V:W:z:")) != -1) {
 		switch (opt) {
 		case 'b':
 			bits = (u_int32_t)strtonum(optarg, 768, 32768, &errstr);
@@ -1597,7 +1650,7 @@
 			identity_new_passphrase = optarg;
 			break;
 		case 'O':
-			add_cert_constraint(optarg);
+			add_cert_option(optarg);
 			break;
 		case 'C':
 			identity_comment = optarg;
@@ -1612,7 +1665,7 @@
 			break;
 		case 'h':
 			cert_key_type = SSH2_CERT_TYPE_HOST;
-			constraint_flags = 0;
+			critical_flags = 0;
 			break;
 		case 'i':
 		case 'X':
@@ -1661,9 +1714,8 @@
 			break;
 		case 'M':
 			memory = (u_int32_t)strtonum(optarg, 1, UINT_MAX, &errstr);
-			if (errstr) {
+			if (errstr)
 				fatal("Memory limit is %s: %s", errstr, optarg);
-			}
 			break;
 		case 'G':
 			do_gen_candidates = 1;
@@ -1685,6 +1737,11 @@
 		case 'V':
 			parse_cert_times(optarg);
 			break;
+		case 'z':
+			cert_serial = strtonum(optarg, 0, LLONG_MAX, &errstr);
+			if (errstr)
+				fatal("Invalid serial number: %s", errstr);
+			break;
 		case '?':
 		default:
 			usage();
diff --git a/ssh-rsa.c b/ssh-rsa.c
index 842857f..bb9cc8e 100644
--- a/ssh-rsa.c
+++ b/ssh-rsa.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: ssh-rsa.c,v 1.40 2010/02/26 20:29:54 djm Exp $ */
+/* $OpenBSD: ssh-rsa.c,v 1.41 2010/04/16 01:47:26 djm Exp $ */
 /*
  * Copyright (c) 2000, 2003 Markus Friedl <markus@openbsd.org>
  *
@@ -46,9 +46,8 @@
 	int ok, nid;
 	Buffer b;
 
-	if (key == NULL ||
-	    (key->type != KEY_RSA && key->type != KEY_RSA_CERT) ||
-	    key->rsa == NULL) {
+	if (key == NULL || key->rsa == NULL || (key->type != KEY_RSA &&
+	    key->type != KEY_RSA_CERT && key->type != KEY_RSA_CERT_V00)) {
 		error("ssh_rsa_sign: no RSA key");
 		return -1;
 	}
@@ -115,9 +114,8 @@
 	u_int len, dlen, modlen;
 	int rlen, ret, nid;
 
-	if (key == NULL ||
-	    (key->type != KEY_RSA && key->type != KEY_RSA_CERT) ||
-	    key->rsa == NULL) {
+	if (key == NULL || key->rsa == NULL || (key->type != KEY_RSA &&
+	    key->type != KEY_RSA_CERT && key->type != KEY_RSA_CERT_V00)) {
 		error("ssh_rsa_verify: no RSA key");
 		return -1;
 	}
diff --git a/sshconnect.c b/sshconnect.c
index ca83bc7..3c8b8c7 100644
--- a/sshconnect.c
+++ b/sshconnect.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: sshconnect.c,v 1.222 2010/04/14 22:27:42 djm Exp $ */
+/* $OpenBSD: sshconnect.c,v 1.223 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
@@ -586,9 +586,9 @@
 		error("%s", reason);
 		return 0;
 	}
-	if (buffer_len(&host_key->cert->constraints) != 0) {
-		error("Certificate for %s contains unsupported constraint(s)",
-		    host);
+	if (buffer_len(&host_key->cert->critical) != 0) {
+		error("Certificate for %s contains unsupported "
+		    "critical options(s)", host);
 		return 0;
 	}
 	return 1;
diff --git a/sshconnect2.c b/sshconnect2.c
index 25a3323..e146a4b 100644
--- a/sshconnect2.c
+++ b/sshconnect2.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: sshconnect2.c,v 1.181 2010/04/10 02:10:56 djm Exp $ */
+/* $OpenBSD: sshconnect2.c,v 1.182 2010/04/16 01:47:26 djm Exp $ */
 /*
  * Copyright (c) 2000 Markus Friedl.  All rights reserved.
  * Copyright (c) 2008 Damien Miller.  All rights reserved.
@@ -1140,8 +1140,11 @@
 	u_int skip = 0;
 	int ret = -1;
 	int have_sig = 1;
+	char *fp;
 
-	debug3("sign_and_send_pubkey");
+	fp = key_fingerprint(id->key, SSH_FP_MD5, SSH_FP_HEX);
+	debug3("sign_and_send_pubkey: %s %s", key_type(id->key), fp);
+	xfree(fp);
 
 	if (key_to_blob(id->key, &blob, &bloblen) == 0) {
 		/* we cannot handle this key */
diff --git a/sshd.c b/sshd.c
index bc0d275..a7d3ee5 100644
--- a/sshd.c
+++ b/sshd.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: sshd.c,v 1.374 2010/03/07 11:57:13 dtucker Exp $ */
+/* $OpenBSD: sshd.c,v 1.375 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
@@ -744,6 +744,8 @@
 		if (key == NULL)
 			continue;
 		switch (key->type) {
+		case KEY_RSA_CERT_V00:
+		case KEY_DSA_CERT_V00:
 		case KEY_RSA_CERT:
 		case KEY_DSA_CERT:
 			if (buffer_len(&b) > 0)
@@ -767,10 +769,17 @@
 	Key *key;
 
 	for (i = 0; i < options.num_host_key_files; i++) {
-		if (type == KEY_RSA_CERT || type == KEY_DSA_CERT)
+		switch (type) {
+		case KEY_RSA_CERT_V00:
+		case KEY_DSA_CERT_V00:
+		case KEY_RSA_CERT:
+		case KEY_DSA_CERT:
 			key = sensitive_data.host_certificates[i];
-		else
+			break;
+		default:
 			key = sensitive_data.host_keys[i];
+			break;
+		}
 		if (key != NULL && key->type == type)
 			return need_private ?
 			    sensitive_data.host_keys[i] : key;