[crypto] Allow certificate chains to be long-lived data structures

At present, certificate chain validation is treated as an
instantaneous process that can be carried out using only data that is
already in memory.  This model does not allow for validation to
include non-instantaneous steps, such as downloading a cross-signing
certificate, or determining certificate revocation status via OCSP.

Redesign the internal representation of certificate chains to allow
chains to outlive the scope of the original source of certificates
(such as a TLS Certificate record).

Allow for certificates to be cached, so that each certificate needs to
be validated only once.

Signed-off-by: Michael Brown <mcb30@ipxe.org>

9 files changed, 1075 insertions, 463 deletions

diff --git a/src/crypto/cms.c b/src/crypto/cms.c
index 04fc2a8..ee09dff 100644
--- a/src/crypto/cms.c
+++ b/src/crypto/cms.c
@@ -32,6 +32,7 @@ FILE_LICENCE ( GPL2_OR_LATER );
 #include <errno.h>
 #include <ipxe/asn1.h>
 #include <ipxe/x509.h>
+#include <ipxe/malloc.h>
 #include <ipxe/uaccess.h>
 #include <ipxe/cms.h>
 
@@ -44,14 +45,14 @@ FILE_LICENCE ( GPL2_OR_LATER );
 	__einfo_error ( EINFO_EACCES_NON_CODE_SIGNING )
 #define EINFO_EACCES_NON_CODE_SIGNING \
 	__einfo_uniqify ( EINFO_EACCES, 0x02, "Not a code-signing certificate" )
-#define EACCES_INCOMPLETE \
-	__einfo_error ( EINFO_EACCES_INCOMPLETE )
-#define EINFO_EACCES_INCOMPLETE \
-	__einfo_uniqify ( EINFO_EACCES, 0x03, "Incomplete certificate chain" )
 #define EACCES_WRONG_NAME \
 	__einfo_error ( EINFO_EACCES_WRONG_NAME )
 #define EINFO_EACCES_WRONG_NAME \
 	__einfo_uniqify ( EINFO_EACCES, 0x04, "Incorrect certificate name" )
+#define EACCES_NO_SIGNATURES \
+	__einfo_error ( EINFO_EACCES_NO_SIGNATURES )
+#define EINFO_EACCES_NO_SIGNATURES \
+	__einfo_uniqify ( EINFO_EACCES, 0x05, "No signatures present" )
 #define EINVAL_DIGEST \
 	__einfo_error ( EINFO_EINVAL_DIGEST )
 #define EINFO_EINVAL_DIGEST \
@@ -108,6 +109,113 @@ static int cms_parse_content_type ( struct cms_signature *sig,
 }
 
 /**
+ * Parse CMS signature certificate list
+ *
+ * @v sig		CMS signature
+ * @v raw		ASN.1 cursor
+ * @ret rc		Return status code
+ */
+static int cms_parse_certificates ( struct cms_signature *sig,
+				    const struct asn1_cursor *raw ) {
+	struct asn1_cursor cursor;
+	struct x509_certificate *cert;
+	int rc;
+
+	/* Enter certificates */
+	memcpy ( &cursor, raw, sizeof ( cursor ) );
+	asn1_enter ( &cursor, ASN1_EXPLICIT_TAG ( 0 ) );
+
+	/* Add each certificate */
+	while ( cursor.len ) {
+
+		/* Parse certificate */
+		if ( ( rc = x509_certificate ( cursor.data, cursor.len,
+					       &cert ) ) != 0 ) {
+			DBGC ( sig, "CMS %p could not parse certificate: %s\n",
+			       sig, strerror ( rc) );
+			DBGC_HDA ( sig, 0, cursor.data, cursor.len );
+			goto err_parse;
+		}
+		DBGC ( sig, "CMS %p found certificate %s\n",
+		       sig, cert->subject.name );
+
+		/* Add certificate to list */
+		if ( ( rc = x509_append ( sig->certificates, cert ) ) != 0 ) {
+			DBGC ( sig, "CMS %p could not append certificate: %s\n",
+			       sig, strerror ( rc ) );
+			goto err_append;
+		}
+
+		/* Drop reference to certificate */
+		x509_put ( cert );
+		cert = NULL;
+
+		/* Move to next certificate */
+		asn1_skip_any ( &cursor );
+	}
+
+	return 0;
+
+ err_append:
+	x509_put ( cert );
+ err_parse:
+	return rc;
+}
+
+/**
+ * Identify CMS signature certificate by issuer and serial number
+ *
+ * @v sig		CMS signature
+ * @v issuer		Issuer
+ * @v serial		Serial number
+ * @ret cert		X.509 certificate, or NULL if not found
+ */
+static struct x509_certificate *
+cms_find_issuer_serial ( struct cms_signature *sig,
+			 const struct asn1_cursor *issuer,
+			 const struct asn1_cursor *serial ) {
+	struct x509_link *link;
+	struct x509_certificate *cert;
+
+	/* Scan through certificate list */
+	list_for_each_entry ( link, &sig->certificates->links, list ) {
+
+		/* Check issuer and serial number */
+		cert = link->cert;
+		if ( ( asn1_compare ( issuer, &cert->issuer.raw ) == 0 ) &&
+		     ( asn1_compare ( serial, &cert->serial.raw ) == 0 ) )
+			return cert;
+	}
+
+	return NULL;
+}
+
+/**
+ * Identify CMS signature certificate by subject
+ *
+ * @v sig		CMS signature
+ * @v subject		Subject
+ * @ret cert		X.509 certificate, or NULL if not found
+ */
+static struct x509_certificate *
+cms_find_subject ( struct cms_signature *sig,
+		   const struct asn1_cursor *subject ) {
+	struct x509_link *link;
+	struct x509_certificate *cert;
+
+	/* Scan through certificate list */
+	list_for_each_entry ( link, &sig->certificates->links, list ) {
+
+		/* Check subject */
+		cert = link->cert;
+		if ( asn1_compare ( subject, &cert->subject.raw ) == 0 )
+			return cert;
+	}
+
+	return NULL;
+}
+
+/**
  * Parse CMS signature signer identifier
  *
  * @v sig		CMS signature
@@ -119,34 +227,63 @@ static int cms_parse_signer_identifier ( struct cms_signature *sig,
 					 struct cms_signer_info *info,
 					 const struct asn1_cursor *raw ) {
 	struct asn1_cursor cursor;
+	struct asn1_cursor serial;
+	struct asn1_cursor issuer;
+	struct x509_certificate *cert;
+	struct x509_certificate *previous;
 	int rc;
 
 	/* Enter issuerAndSerialNumber */
 	memcpy ( &cursor, raw, sizeof ( cursor ) );
 	asn1_enter ( &cursor, ASN1_SEQUENCE );
 
-	/* Record issuer */
-	memcpy ( &info->issuer, &cursor, sizeof ( info->issuer ) );
-	if ( ( rc = asn1_shrink ( &info->issuer, ASN1_SEQUENCE ) ) != 0 ) {
+	/* Identify issuer */
+	memcpy ( &issuer, &cursor, sizeof ( issuer ) );
+	if ( ( rc = asn1_shrink ( &issuer, ASN1_SEQUENCE ) ) != 0 ) {
 		DBGC ( sig, "CMS %p/%p could not locate issuer: %s\n",
 		       sig, info, strerror ( rc ) );
 		DBGC_HDA ( sig, 0, raw->data, raw->len );
 		return rc;
 	}
 	DBGC ( sig, "CMS %p/%p issuer is:\n", sig, info );
-	DBGC_HDA ( sig, 0, info->issuer.data, info->issuer.len );
+	DBGC_HDA ( sig, 0, issuer.data, issuer.len );
 	asn1_skip_any ( &cursor );
 
-	/* Record serialNumber */
-	memcpy ( &info->serial, &cursor, sizeof ( info->serial ) );
-	if ( ( rc = asn1_shrink ( &info->serial, ASN1_INTEGER ) ) != 0 ) {
+	/* Identify serialNumber */
+	memcpy ( &serial, &cursor, sizeof ( serial ) );
+	if ( ( rc = asn1_shrink ( &serial, ASN1_INTEGER ) ) != 0 ) {
 		DBGC ( sig, "CMS %p/%p could not locate serialNumber: %s\n",
 		       sig, info, strerror ( rc ) );
 		DBGC_HDA ( sig, 0, raw->data, raw->len );
 		return rc;
 	}
 	DBGC ( sig, "CMS %p/%p serial number is:\n", sig, info );
-	DBGC_HDA ( sig, 0, info->serial.data, info->serial.len );
+	DBGC_HDA ( sig, 0, serial.data, serial.len );
+
+	/* Identify certificate */
+	cert = cms_find_issuer_serial ( sig, &issuer, &serial );
+	if ( ! cert ) {
+		DBGC ( sig, "CMS %p/%p could not identify signer's "
+		       "certificate\n", sig, info );
+		return -ENOENT;
+	}
+
+	/* Create certificate chain */
+	do {
+		/* Add certificate to chain */
+		if ( ( rc = x509_append ( info->chain, cert ) ) != 0 ) {
+			DBGC ( sig, "CMS %p/%p could not append certificate: "
+			       "%s\n", sig, info, strerror ( rc ) );
+			return rc;
+		}
+		DBGC ( sig, "CMS %p/%p added certificate %s\n",
+		       sig, info, cert->subject.name );
+
+		/* Locate next certificate in chain, if any */
+		previous = cert;
+		cert = cms_find_subject ( sig, &cert->issuer.raw );
+
+	} while ( ( cert != NULL ) && ( cert != previous ) );
 
 	return 0;
 }
@@ -249,8 +386,11 @@ static int cms_parse_signature_value ( struct cms_signature *sig,
 	}
 
 	/* Record signature */
-	info->signature = cursor.data;
 	info->signature_len = cursor.len;
+	info->signature = malloc ( info->signature_len );
+	if ( ! info->signature )
+		return -ENOMEM;
+	memcpy ( info->signature, cursor.data, info->signature_len );
 	DBGC ( sig, "CMS %p/%p signature value is:\n", sig, info );
 	DBGC_HDA ( sig, 0, info->signature, info->signature_len );
 
@@ -307,23 +447,21 @@ static int cms_parse_signer_info ( struct cms_signature *sig,
  * Parse CMS signature from ASN.1 data
  *
  * @v sig		CMS signature
- * @v data		Raw signature data
- * @v len		Length of raw data
+ * @v raw		ASN.1 cursor
  * @ret rc		Return status code
  */
-int cms_parse ( struct cms_signature *sig, const void *data, size_t len ) {
+static int cms_parse ( struct cms_signature *sig,
+		       const struct asn1_cursor *raw ) {
 	struct asn1_cursor cursor;
+	struct cms_signer_info *info;
 	int rc;
 
-	/* Initialise signature */
-	memset ( sig, 0, sizeof ( *sig ) );
-	cursor.data = data;
-	cursor.len = len;
-
 	/* Enter contentInfo */
+	memcpy ( &cursor, raw, sizeof ( cursor ) );
 	asn1_enter ( &cursor, ASN1_SEQUENCE );
 
 	/* Parse contentType */
+
 	if ( ( rc = cms_parse_content_type ( sig, &cursor ) ) != 0 )
 		return rc;
 	asn1_skip_any ( &cursor );
@@ -343,14 +481,9 @@ int cms_parse ( struct cms_signature *sig, const void *data, size_t len ) {
 	/* Skip encapContentInfo */
 	asn1_skip ( &cursor, ASN1_SEQUENCE );
 
-	/* Record certificates */
-	memcpy ( &sig->certificates, &cursor, sizeof ( sig->certificates ) );
-	if ( ( rc = asn1_enter ( &sig->certificates,
-				 ASN1_EXPLICIT_TAG ( 0 ) ) ) != 0 ) {
-		DBGC ( sig, "CMS %p could not locate certificates:\n", sig );
-		DBGC_HDA ( sig, 0, data, len );
+	/* Parse certificates */
+	if ( ( rc = cms_parse_certificates ( sig, &cursor ) ) != 0 )
 		return rc;
-	}
 	asn1_skip_any ( &cursor );
 
 	/* Skip crls, if present */
@@ -359,77 +492,100 @@ int cms_parse ( struct cms_signature *sig, const void *data, size_t len ) {
 	/* Enter signerInfos */
 	asn1_enter ( &cursor, ASN1_SET );
 
-	/* Parse first signerInfo */
-	if ( ( rc = cms_parse_signer_info ( sig, &sig->info, &cursor ) ) != 0 )
-		return rc;
+	/* Add each signerInfo.  Errors are handled by ensuring that
+	 * cms_put() will always be able to free any allocated memory.
+	 */
+	while ( cursor.len ) {
+
+		/* Allocate signer information block */
+		info = zalloc ( sizeof ( *info ) );
+		if ( ! info )
+			return -ENOMEM;
+		list_add ( &info->list, &sig->info );
+
+		/* Allocate certificate chain */
+		info->chain = x509_alloc_chain();
+		if ( ! info->chain )
+			return -ENOMEM;
+
+		/* Parse signerInfo */
+		if ( ( rc = cms_parse_signer_info ( sig, info,
+						    &cursor ) ) != 0 )
+			return rc;
+		asn1_skip_any ( &cursor );
+	}
 
 	return 0;
 }
 
-/** CMS certificate chain context */
-struct cms_chain_context {
-	/** Signature */
-	struct cms_signature *sig;
-	/** Signer information */
+/**
+ * Free CMS signature
+ *
+ * @v refcnt		Reference count
+ */
+static void cms_free ( struct refcnt *refcnt ) {
+	struct cms_signature *sig =
+		container_of ( refcnt, struct cms_signature, refcnt );
 	struct cms_signer_info *info;
-};
+	struct cms_signer_info *tmp;
+
+	list_for_each_entry_safe ( info, tmp, &sig->info, list ) {
+		list_del ( &info->list );
+		x509_chain_put ( info->chain );
+		free ( info->signature );
+		free ( info );
+	}
+	x509_chain_put ( sig->certificates );
+	free ( sig );
+}
 
 /**
- * Parse next certificate in chain
+ * Create CMS signature
  *
- * @v cert		X.509 certificate to parse
- * @v previous		Previous X.509 certificate, or NULL
- * @v ctx		Chain context
+ * @v data		Raw signature data
+ * @v len		Length of raw data
+ * @ret sig		CMS signature
  * @ret rc		Return status code
+ *
+ * On success, the caller holds a reference to the CMS signature, and
+ * is responsible for ultimately calling cms_put().
  */
-static int cms_parse_next ( struct x509_certificate *cert,
-			    const struct x509_certificate *previous,
-			    void *ctx ) {
-	struct cms_chain_context *context = ctx;
-	struct cms_signature *sig = context->sig;
-	struct cms_signer_info *info = context->info;
+int cms_signature ( const void *data, size_t len, struct cms_signature **sig ) {
 	struct asn1_cursor cursor;
 	int rc;
 
-	/* Search for relevant certificate */
-	memcpy ( &cursor, &sig->certificates, sizeof ( cursor ) );
-	while ( cursor.len ) {
+	/* Allocate and initialise signature */
+	*sig = zalloc ( sizeof ( **sig ) );
+	if ( ! *sig ) {
+		rc = -ENOMEM;
+		goto err_alloc;
+	}
+	ref_init ( &(*sig)->refcnt, cms_free );
+	INIT_LIST_HEAD ( &(*sig)->info );
+
+	/* Allocate certificate list */
+	(*sig)->certificates = x509_alloc_chain();
+	if ( ! (*sig)->certificates ) {
+		rc = -ENOMEM;
+		goto err_alloc_chain;
+	}
 
-		/* Parse certificate */
-		if ( ( rc = x509_parse ( cert, cursor.data,
-					 cursor.len ) ) != 0 ) {
-			DBGC ( sig, "CMS %p/%p could not parse certificate:\n",
-			       sig, info );
-			DBGC_HDA ( sig, 0, cursor.data, cursor.len );
-			return rc;
-		}
+	/* Initialise cursor */
+	cursor.data = data;
+	cursor.len = len;
+	asn1_shrink_any ( &cursor );
 
-		if ( previous == NULL ) {
-			/* First certificate: check issuer and serial
-			 * number against signer info
-			 */
-			if ( ( asn1_compare ( &info->issuer,
-					      &cert->issuer.raw ) == 0 ) &&
-			     ( asn1_compare ( &info->serial,
-					      &cert->serial.raw ) == 0 ) ) {
-				return 0;
-			}
-		} else {
-			/* Subsequent certificates: check subject
-			 * against previous certificate's issuer.
-			 */
-			if ( asn1_compare ( &previous->issuer.raw,
-					    &cert->subject.raw ) == 0 ) {
-				return 0;
-			}
-		}
+	/* Parse signature */
+	if ( ( rc = cms_parse ( *sig, &cursor ) ) != 0 )
+		goto err_parse;
 
-		/* Move to next certificate */
-		asn1_skip_any ( &cursor );
-	}
+	return 0;
 
-	DBGC ( sig, "CMS %p/%p reached end of certificate chain\n", sig, info );
-	return -EACCES_INCOMPLETE;
+ err_parse:
+ err_alloc_chain:
+	cms_put ( *sig );
+ err_alloc:
+	return rc;
 }
 
 /**
@@ -525,7 +681,6 @@ static int cms_verify_digest ( struct cms_signature *sig,
  * @v info		Signer information
  * @v data		Signed data
  * @v len		Length of signed data
- * @v name		Required common name, or NULL to allow any name
  * @v time		Time at which to validate certificates
  * @v root		Root certificate store, or NULL to use default
  * @ret rc		Return status code
@@ -533,48 +688,37 @@ static int cms_verify_digest ( struct cms_signature *sig,
 static int cms_verify_signer_info ( struct cms_signature *sig,
 				    struct cms_signer_info *info,
 				    userptr_t data, size_t len,
-				    const char *name, time_t time,
-				    struct x509_root *root ) {
-	struct cms_chain_context context;
-	struct x509_certificate cert;
+				    time_t time, struct x509_root *root ) {
+	struct x509_certificate *cert;
 	int rc;
 
 	/* Validate certificate chain */
-	context.sig = sig;
-	context.info = info;
-	if ( ( rc = x509_validate_chain ( cms_parse_next, &context, time, root,
-					  &cert ) ) != 0 ) {
+	if ( ( rc = x509_validate_chain ( info->chain, time, root ) ) != 0 ) {
 		DBGC ( sig, "CMS %p/%p could not validate chain: %s\n",
 		       sig, info, strerror ( rc ) );
 		return rc;
 	}
 
+	/* Extract code-signing certificate */
+	cert = x509_first ( info->chain );
+	assert ( cert != NULL );
+
 	/* Check that certificate can create digital signatures */
-	if ( ! ( cert.extensions.usage.bits & X509_DIGITAL_SIGNATURE ) ) {
+	if ( ! ( cert->extensions.usage.bits & X509_DIGITAL_SIGNATURE ) ) {
 		DBGC ( sig, "CMS %p/%p certificate cannot create signatures\n",
 		       sig, info );
 		return -EACCES_NON_SIGNING;
 	}
 
 	/* Check that certificate can sign code */
-	if ( ! ( cert.extensions.ext_usage.bits & X509_CODE_SIGNING ) ) {
+	if ( ! ( cert->extensions.ext_usage.bits & X509_CODE_SIGNING ) ) {
 		DBGC ( sig, "CMS %p/%p certificate is not code-signing\n",
 		       sig, info );
 		return -EACCES_NON_CODE_SIGNING;
 	}
 
-	/* Check certificate name, if applicable */
-	if ( ( name != NULL ) &&
-	     ( ( cert.subject.name.len != strlen ( name ) ) ||
-	       ( memcmp ( cert.subject.name.data, name,
-			  cert.subject.name.len ) != 0 ) ) ) {
-		DBGC ( sig, "CMS %p/%p certificate name incorrect\n",
-		       sig, info );
-		return -EACCES_WRONG_NAME;
-	}
-
 	/* Verify digest */
-	if ( ( rc = cms_verify_digest ( sig, info, &cert, data, len ) ) != 0 )
+	if ( ( rc = cms_verify_digest ( sig, info, cert, data, len ) ) != 0 )
 		return rc;
 
 	return 0;
@@ -586,19 +730,40 @@ static int cms_verify_signer_info ( struct cms_signature *sig,
  * @v sig		CMS signature
  * @v data		Signed data
  * @v len		Length of signed data
- * @v name		Required common name, or NULL to allow any name
+ * @v name		Required common name, or NULL to check all signatures
  * @v time		Time at which to validate certificates
  * @v root		Root certificate store, or NULL to use default
  * @ret rc		Return status code
  */
 int cms_verify ( struct cms_signature *sig, userptr_t data, size_t len,
 		 const char *name, time_t time, struct x509_root *root ) {
+	struct cms_signer_info *info;
+	struct x509_certificate *cert;
+	int count = 0;
 	int rc;
 
-	/* Verify using first signerInfo */
-	if ( ( rc = cms_verify_signer_info ( sig, &sig->info, data, len,
-					     name, time, root ) ) != 0 )
-		return rc;
+	/* Verify using all signerInfos */
+	list_for_each_entry ( info, &sig->info, list ) {
+		cert = x509_first ( info->chain );
+		if ( name && ( strcmp ( name, cert->subject.name ) != 0 ) )
+			continue;
+		if ( ( rc = cms_verify_signer_info ( sig, info, data, len,
+						     time, root ) ) != 0 )
+			return rc;
+		count++;
+	}
+
+	/* Check that we have verified at least one signature */
+	if ( count == 0 ) {
+		if ( name ) {
+			DBGC ( sig, "CMS %p had no signatures matching name "
+			       "%s\n", sig, name );
+			return -EACCES_WRONG_NAME;
+		} else {
+			DBGC ( sig, "CMS %p had no signatures\n", sig );
+			return -EACCES_NO_SIGNATURES;
+		}
+	}
 
 	return 0;
 }
diff --git a/src/crypto/x509.c b/src/crypto/x509.c
index a0ed816..be2e100 100644
--- a/src/crypto/x509.c
+++ b/src/crypto/x509.c
@@ -18,11 +18,14 @@
 
 FILE_LICENCE ( GPL2_OR_LATER );
 
+#include <stdlib.h>
 #include <string.h>
 #include <ctype.h>
 #include <time.h>
 #include <errno.h>
 #include <assert.h>
+#include <ipxe/list.h>
+#include <ipxe/malloc.h>
 #include <ipxe/asn1.h>
 #include <ipxe/crypto.h>
 #include <ipxe/md5.h>
@@ -97,6 +100,58 @@ FILE_LICENCE ( GPL2_OR_LATER );
 	__einfo_error ( EINFO_EACCES_UNTRUSTED )
 #define EINFO_EACCES_UNTRUSTED \
 	__einfo_uniqify ( EINFO_EACCES, 0x06, "Untrusted root certificate" )
+#define EACCES_OUT_OF_ORDER \
+	__einfo_error ( EINFO_EACCES_OUT_OF_ORDER )
+#define EINFO_EACCES_OUT_OF_ORDER \
+	__einfo_uniqify ( EINFO_EACCES, 0x07, "Validation out of order" )
+#define EACCES_EMPTY \
+	__einfo_error ( EINFO_EACCES_EMPTY )
+#define EINFO_EACCES_EMPTY \
+	__einfo_uniqify ( EINFO_EACCES, 0x08, "Empty certificate chain" )
+
+/** Certificate cache */
+static LIST_HEAD ( x509_cache );
+
+/**
+ * Free X.509 certificate
+ *
+ * @v refcnt		Reference count
+ */
+static void x509_free ( struct refcnt *refcnt ) {
+	struct x509_certificate *cert =
+		container_of ( refcnt, struct x509_certificate, refcnt );
+
+	DBGC ( cert, "X509 %p freed\n", cert );
+	free ( cert->subject.name );
+	free ( cert->extensions.auth_info.ocsp.uri );
+	free ( cert );
+}
+
+/**
+ * Discard a cached certificate
+ *
+ * @ret discarded	Number of cached items discarded
+ */
+static unsigned int x509_discard ( void ) {
+	struct x509_certificate *cert;
+
+	/* Discard the least recently used certificate for which the
+	 * only reference is held by the cache itself.
+	 */
+	list_for_each_entry_reverse ( cert, &x509_cache, list ) {
+		if ( cert->refcnt.count == 0 ) {
+			list_del ( &cert->list );
+			x509_put ( cert );
+			return 1;
+		}
+	}
+	return 0;
+}
+
+/** X.509 cache discarder */
+struct cache_discarder x509_cache_discarder __cache_discarder = {
+	.discard = x509_discard,
+};
 
 /** "commonName" object identifier */
 static uint8_t oid_common_name[] = { ASN1_OID_COMMON_NAME };
@@ -113,9 +168,9 @@ static struct asn1_cursor oid_common_name_cursor =
  * @v raw		ASN.1 cursor
  * @ret rc		Return status code
  */
-int x509_parse_pubkey_algorithm ( struct x509_certificate *cert,
-				  struct asn1_algorithm **algorithm,
-				  const struct asn1_cursor *raw ) {
+static int x509_parse_pubkey_algorithm ( struct x509_certificate *cert,
+					 struct asn1_algorithm **algorithm,
+					 const struct asn1_cursor *raw ) {
 
 	/* Parse algorithm */
 	*algorithm = asn1_algorithm ( raw );
@@ -486,8 +541,7 @@ static int x509_parse_validity ( struct x509_certificate *cert,
  * @v raw		ASN.1 cursor
  * @ret rc		Return status code
  */
-static int x509_parse_common_name ( struct x509_certificate *cert,
-				    struct x509_string *name,
+static int x509_parse_common_name ( struct x509_certificate *cert, char **name,
 				    const struct asn1_cursor *raw ) {
 	struct asn1_cursor cursor;
 	struct asn1_cursor oid_cursor;
@@ -500,6 +554,8 @@ static int x509_parse_common_name ( struct x509_certificate *cert,
 
 	/* Scan through name list */
 	for ( ; cursor.len ; asn1_skip_any ( &cursor ) ) {
+
+		/* Check for "commonName" OID */
 		memcpy ( &oid_cursor, &cursor, sizeof ( oid_cursor ) );
 		asn1_enter ( &oid_cursor, ASN1_SET );
 		asn1_enter ( &oid_cursor, ASN1_SEQUENCE );
@@ -513,8 +569,12 @@ static int x509_parse_common_name ( struct x509_certificate *cert,
 			DBGC_HDA ( cert, 0, raw->data, raw->len );
 			return rc;
 		}
-		name->data = name_cursor.data;
-		name->len = name_cursor.len;
+
+		/* Allocate name */
+		*name = zalloc ( name_cursor.len + 1 /* NUL */ );
+		if ( ! *name )
+			return -ENOMEM;
+		memcpy ( *name, name_cursor.data, name_cursor.len );
 		return 0;
 	}
 
@@ -533,7 +593,7 @@ static int x509_parse_common_name ( struct x509_certificate *cert,
 static int x509_parse_subject ( struct x509_certificate *cert,
 				const struct asn1_cursor *raw ) {
 	struct x509_subject *subject = &cert->subject;
-	struct x509_string *name = &subject->name;
+	char **name = &subject->name;
 	int rc;
 
 	/* Record raw subject */
@@ -545,8 +605,7 @@ static int x509_parse_subject ( struct x509_certificate *cert,
 	/* Parse common name */
 	if ( ( rc = x509_parse_common_name ( cert, name, raw ) ) != 0 )
 		return rc;
-	DBGC ( cert, "X509 %p common name is:\n", cert );
-	DBGC_HDA ( cert, 0, name->data, name->len );
+	DBGC ( cert, "X509 %p common name is \"%s\":\n", cert, *name );
 
 	return 0;
 }
@@ -625,7 +684,7 @@ static int x509_parse_basic_constraints ( struct x509_certificate *cert,
 		return 0;
 
 	/* Parse "pathLenConstraint", if present and applicable */
-	basic->path_len = -1U; /* Default is unlimited */
+	basic->path_len = X509_PATH_LEN_UNLIMITED;
 	if ( asn1_type ( &cursor ) == ASN1_INTEGER ) {
 		if ( ( rc = asn1_integer ( &cursor, &path_len ) ) != 0 ) {
 			DBGC ( cert, "X509 %p cannot parse pathLenConstraint: "
@@ -783,10 +842,11 @@ static int x509_parse_ocsp ( struct x509_certificate *cert,
 	}
 
 	/* Record URI */
-	ocsp->uri.data = cursor.data;
-	ocsp->uri.len = cursor.len;
-	DBGC ( cert, "X509 %p OCSP URI is:\n", cert );
-	DBGC_HDA ( cert, 0, ocsp->uri.data, ocsp->uri.len );
+	ocsp->uri = zalloc ( cursor.len + 1 /* NUL */ );
+	if ( ! ocsp->uri )
+		return -ENOMEM;
+	memcpy ( ocsp->uri, cursor.data, cursor.len );
+	DBGC ( cert, "X509 %p OCSP URI is %s:\n", cert, ocsp->uri );
 
 	return 0;
 }
@@ -1112,25 +1172,22 @@ static int x509_parse_tbscertificate ( struct x509_certificate *cert,
  * Parse X.509 certificate from ASN.1 data
  *
  * @v cert		X.509 certificate
- * @v data		Raw certificate data
- * @v len		Length of raw data
+ * @v raw		ASN.1 cursor
  * @ret rc		Return status code
  */
-int x509_parse ( struct x509_certificate *cert, const void *data, size_t len ) {
+static int x509_parse ( struct x509_certificate *cert,
+			const struct asn1_cursor *raw ) {
 	struct x509_signature *signature = &cert->signature;
 	struct asn1_algorithm **signature_algorithm = &signature->algorithm;
 	struct x509_bit_string *signature_value = &signature->value;
 	struct asn1_cursor cursor;
 	int rc;
 
-	/* Initialise certificate */
-	memset ( cert, 0, sizeof ( *cert ) );
-	cert->raw.data = data;
-	cert->raw.len = len;
-	asn1_shrink_any ( &cert->raw );
+	/* Record raw certificate */
+	memcpy ( &cursor, raw, sizeof ( cursor ) );
+	memcpy ( &cert->raw, &cursor, sizeof ( cert->raw ) );
 
 	/* Enter certificate */
-	memcpy ( &cursor, &cert->raw, sizeof ( cursor ) );
 	asn1_enter ( &cursor, ASN1_SEQUENCE );
 
 	/* Parse tbsCertificate */
@@ -1168,7 +1225,72 @@ int x509_parse ( struct x509_certificate *cert, const void *data, size_t len ) {
 }
 
 /**
- * Verify X.509 certificate signature
+ * Create X.509 certificate
+ *
+ * @v data		Raw certificate data
+ * @v len		Length of raw data
+ * @ret cert		X.509 certificate
+ * @ret rc		Return status code
+ *
+ * On success, the caller holds a reference to the X.509 certificate,
+ * and is responsible for ultimately calling x509_put().
+ */
+int x509_certificate ( const void *data, size_t len,
+		       struct x509_certificate **cert ) {
+	struct asn1_cursor cursor;
+	void *raw;
+	int rc;
+
+	/* Initialise cursor */
+	cursor.data = data;
+	cursor.len = len;
+	asn1_shrink_any ( &cursor );
+
+	/* Search for certificate within cache */
+	list_for_each_entry ( (*cert), &x509_cache, list ) {
+		if ( asn1_compare ( &cursor, &(*cert)->raw ) == 0 ) {
+
+			DBGC ( *cert, "X509 %p \"%s\" cache hit\n",
+			       *cert, (*cert)->subject.name );
+
+			/* Mark as most recently used */
+			list_del ( &(*cert)->list );
+			list_add ( &(*cert)->list, &x509_cache );
+
+			/* Add caller's reference */
+			x509_get ( *cert );
+
+			return 0;
+		}
+	}
+
+	/* Allocate and initialise certificate */
+	*cert = zalloc ( sizeof ( **cert ) + cursor.len );
+	if ( ! *cert )
+		return -ENOMEM;
+	ref_init ( &(*cert)->refcnt, x509_free );
+	INIT_LIST_HEAD ( &(*cert)->list );
+	raw = ( *cert + 1 );
+
+	/* Copy raw data */
+	memcpy ( raw, cursor.data, cursor.len );
+	cursor.data = raw;
+
+	/* Parse certificate */
+	if ( ( rc = x509_parse ( *cert, &cursor ) ) != 0 ) {
+		x509_put ( *cert );
+		return rc;
+	}
+
+	/* Add certificate to cache */
+	x509_get ( *cert );
+	list_add ( &(*cert)->list, &x509_cache );
+
+	return 0;
+}
+
+/**
+ * Check X.509 certificate signature
  *
  * @v cert		X.509 certificate
  * @v public_key	X.509 public key
@@ -1192,14 +1314,15 @@ static int x509_check_signature ( struct x509_certificate *cert,
 	digest_init ( digest, digest_ctx );
 	digest_update ( digest, digest_ctx, cert->tbs.data, cert->tbs.len );
 	digest_final ( digest, digest_ctx, digest_out );
-	DBGC ( cert, "X509 %p digest:\n", cert );
+	DBGC ( cert, "X509 %p \"%s\" digest:\n", cert, cert->subject.name );
 	DBGC_HDA ( cert, 0, digest_out, sizeof ( digest_out ) );
 
 	/* Check that signature public key algorithm matches signer */
 	if ( public_key->algorithm->pubkey != pubkey ) {
-		DBGC ( cert, "X509 %p signature algorithm %s does not match "
-		       "signer's algorithm %s\n",
-		       cert, algorithm->name, public_key->algorithm->name );
+		DBGC ( cert, "X509 %p \"%s\" signature algorithm %s does not "
+		       "match signer's algorithm %s\n",
+		       cert, cert->subject.name, algorithm->name,
+		       public_key->algorithm->name );
 		rc = -EINVAL_ALGORITHM_MISMATCH;
 		goto err_mismatch;
 	}
@@ -1207,15 +1330,15 @@ static int x509_check_signature ( struct x509_certificate *cert,
 	/* Verify signature using signer's public key */
 	if ( ( rc = pubkey_init ( pubkey, pubkey_ctx, public_key->raw.data,
 				  public_key->raw.len ) ) != 0 ) {
-		DBGC ( cert, "X509 %p cannot initialise public key: %s\n",
-		       cert, strerror ( rc ) );
+		DBGC ( cert, "X509 %p \"%s\" cannot initialise public key: "
+		       "%s\n", cert, cert->subject.name, strerror ( rc ) );
 		goto err_pubkey_init;
 	}
 	if ( ( rc = pubkey_verify ( pubkey, pubkey_ctx, digest, digest_out,
 				    signature->value.data,
 				    signature->value.len ) ) != 0 ) {
-		DBGC ( cert, "X509 %p signature verification failed: %s\n",
-		       cert, strerror ( rc ) );
+		DBGC ( cert, "X509 %p \"%s\" signature verification failed: "
+		       "%s\n", cert, cert->subject.name, strerror ( rc ) );
 		goto err_pubkey_verify;
 	}
 
@@ -1230,14 +1353,14 @@ static int x509_check_signature ( struct x509_certificate *cert,
 }
 
 /**
- * Validate X.509 certificate against issuer certificate
+ * Check X.509 certificate against issuer certificate
  *
  * @v cert		X.509 certificate
  * @v issuer		X.509 issuer certificate
  * @ret rc		Return status code
  */
-int x509_validate_issuer ( struct x509_certificate *cert,
-			   struct x509_certificate *issuer ) {
+int x509_check_issuer ( struct x509_certificate *cert,
+			struct x509_certificate *issuer ) {
 	struct x509_public_key *public_key = &issuer->subject.public_key;
 	int rc;
 
@@ -1254,8 +1377,9 @@ int x509_validate_issuer ( struct x509_certificate *cert,
 	 * for some enjoyable ranting on this subject.
 	 */
 	if ( asn1_compare ( &cert->issuer.raw, &issuer->subject.raw ) != 0 ) {
-		DBGC ( cert, "X509 %p issuer does not match X509 %p subject\n",
-		       cert, issuer );
+		DBGC ( cert, "X509 %p \"%s\" issuer does not match X509 %p "
+		       "\"%s\" subject\n", cert, cert->subject.name,
+		       issuer, issuer->subject.name );
 		DBGC_HDA ( cert, 0, cert->issuer.raw.data,
 			   cert->issuer.raw.len );
 		DBGC_HDA ( issuer, 0, issuer->subject.raw.data,
@@ -1265,14 +1389,16 @@ int x509_validate_issuer ( struct x509_certificate *cert,
 
 	/* Check that issuer is allowed to sign certificates */
 	if ( ! issuer->extensions.basic.ca ) {
-		DBGC ( issuer, "X509 %p cannot sign X509 %p: not a CA "
-		       "certificate\n", issuer, cert );
+		DBGC ( issuer, "X509 %p \"%s\" cannot sign X509 %p \"%s\": "
+		       "not a CA certificate\n", issuer, issuer->subject.name,
+		       cert, cert->subject.name );
 		return -EACCES_NOT_CA;
 	}
 	if ( issuer->extensions.usage.present &&
 	     ( ! ( issuer->extensions.usage.bits & X509_KEY_CERT_SIGN ) ) ) {
-		DBGC ( issuer, "X509 %p cannot sign X509 %p: no keyCertSign "
-		       "usage\n", issuer, cert );
+		DBGC ( issuer, "X509 %p \"%s\" cannot sign X509 %p \"%s\": "
+		       "no keyCertSign usage\n", issuer, issuer->subject.name,
+		       cert, cert->subject.name );
 		return -EACCES_KEY_USAGE;
 	}
 
@@ -1280,8 +1406,6 @@ int x509_validate_issuer ( struct x509_certificate *cert,
 	if ( ( rc = x509_check_signature ( cert, public_key ) ) != 0 )
 		return rc;
 
-	DBGC ( cert, "X509 %p successfully validated using X509 %p\n",
-	       cert, issuer );
 	return 0;
 }
 
@@ -1293,7 +1417,8 @@ int x509_validate_issuer ( struct x509_certificate *cert,
  * @v fingerprint	Fingerprint buffer
  */
 void x509_fingerprint ( struct x509_certificate *cert,
-			struct digest_algorithm *digest, void *fingerprint ) {
+			struct digest_algorithm *digest,
+			void *fingerprint ) {
 	uint8_t ctx[ digest->ctxsize ];
 
 	/* Calculate fingerprint */
@@ -1303,14 +1428,13 @@ void x509_fingerprint ( struct x509_certificate *cert,
 }
 
 /**
- * Validate X.509 root certificate
+ * Check X.509 root certificate
  *
  * @v cert		X.509 certificate
  * @v root		X.509 root certificate store
  * @ret rc		Return status code
  */
-int x509_validate_root ( struct x509_certificate *cert,
-			 struct x509_root *root ) {
+int x509_check_root ( struct x509_certificate *cert, struct x509_root *root ) {
 	struct digest_algorithm *digest = root->digest;
 	uint8_t fingerprint[ digest->digestsize ];
 	const uint8_t *root_fingerprint = root->fingerprints;
@@ -1323,122 +1447,244 @@ int x509_validate_root ( struct x509_certificate *cert,
 	for ( i = 0 ; i < root->count ; i++ ) {
 		if ( memcmp ( fingerprint, root_fingerprint,
 			      sizeof ( fingerprint ) ) == 0 ) {
-			DBGC ( cert, "X509 %p is a root certificate\n", cert );
+			DBGC ( cert, "X509 %p \"%s\" is a root certificate\n",
+			       cert, cert->subject.name );
 			return 0;
 		}
 		root_fingerprint += sizeof ( fingerprint );
 	}
 
-	DBGC ( cert, "X509 %p is not a root certificate\n", cert );
+	DBGC ( cert, "X509 %p \"%s\" is not a root certificate\n",
+	       cert, cert->subject.name );
 	return -ENOENT;
 }
 
 /**
- * Validate X.509 certificate validity period
+ * Check X.509 certificate validity period
  *
  * @v cert		X.509 certificate
- * @v time		Time at which to validate certificate
+ * @v time		Time at which to check certificate
  * @ret rc		Return status code
  */
-int x509_validate_time ( struct x509_certificate *cert, time_t time ) {
+int x509_check_time ( struct x509_certificate *cert, time_t time ) {
 	struct x509_validity *validity = &cert->validity;
 
 	/* Check validity period */
 	if ( time < validity->not_before.time ) {
-		DBGC ( cert, "X509 %p is not yet valid (at time %lld)\n",
-		       cert, time );
+		DBGC ( cert, "X509 %p \"%s\" is not yet valid (at time %lld)\n",
+		       cert, cert->subject.name, time );
 		return -EACCES_EXPIRED;
 	}
 	if ( time > validity->not_after.time ) {
-		DBGC ( cert, "X509 %p has expired (at time %lld)\n",
-		       cert, time );
+		DBGC ( cert, "X509 %p \"%s\" has expired (at time %lld)\n",
+		       cert, cert->subject.name, time );
 		return -EACCES_EXPIRED;
 	}
 
-	DBGC ( cert, "X509 %p is valid (at time %lld)\n", cert, time );
+	DBGC ( cert, "X509 %p \"%s\" is valid (at time %lld)\n",
+	       cert, cert->subject.name, time );
 	return 0;
 }
 
 /**
- * Validate X.509 certificate chain
+ * Validate X.509 certificate
  *
- * @v parse_next	Parse next X.509 certificate in chain
- * @v context		Context for parse_next()
- * @v time		Time at which to validate certificates
+ * @v cert		X.509 certificate
+ * @v issuer		Issuing X.509 certificate (or NULL)
+ * @v time		Time at which to validate certificate
  * @v root		Root certificate store, or NULL to use default
- * @v first		Initial X.509 certificate to fill in, or NULL
  * @ret rc		Return status code
+ *
+ * The issuing certificate must have already been validated.
+ *
+ * Validation results are cached: if a certificate has already been
+ * successfully validated then @c issuer, @c time, and @c root will be
+ * ignored.
  */
-int x509_validate_chain ( int ( * parse_next )
-			  ( struct x509_certificate *cert,
-			    const struct x509_certificate *previous,
-			    void *context ),
-			  void *context, time_t time, struct x509_root *root,
-			  struct x509_certificate *first ) {
-	struct x509_certificate temp[2];
-	struct x509_certificate *current = &temp[0];
-	struct x509_certificate *next = &temp[1];
-	struct x509_certificate *swap;
-	unsigned int path_len = 0;
+static int x509_validate ( struct x509_certificate *cert,
+			   struct x509_certificate *issuer,
+			   time_t time, struct x509_root *root ) {
+	unsigned int max_path_remaining;
 	int rc;
 
 	/* Use default root certificate store if none specified */
 	if ( ! root )
 		root = &root_certificates;
 
-	/* Get first certificate in chain */
-	if ( ( rc = parse_next ( current, NULL, context ) ) != 0 ) {
-		DBGC ( context, "X509 chain %p could not get first "
-		       "certificate: %s\n", context, strerror ( rc ) );
+	/* Return success if certificate has already been validated */
+	if ( cert->valid )
+		return 0;
+
+	/* Fail if certificate is invalid at specified time */
+	if ( ( rc = x509_check_time ( cert, time ) ) != 0 )
 		return rc;
+
+	/* Succeed if certificate is a trusted root certificate */
+	if ( x509_check_root ( cert, root ) == 0 ) {
+		cert->valid = 1;
+		cert->path_remaining = ( cert->extensions.basic.path_len + 1 );
+		return 0;
 	}
 
-	/* Record first certificate, if applicable */
-	if ( first )
-		memcpy ( first, current, sizeof ( *first ) );
+	/* Fail unless we have an issuer */
+	if ( ! issuer ) {
+		DBGC ( cert, "X509 %p \"%s\" has no issuer\n",
+		       cert, cert->subject.name );
+		return -EACCES_UNTRUSTED;
+	}
 
-	/* Process chain */
-	while ( 1 ) {
+	/* Fail unless issuer has already been validated */
+	if ( ! issuer->valid ) {
+		DBGC ( cert, "X509 %p \"%s\" issuer %p \"%s\" has not yet "
+		       "been validated\n", cert, cert->subject.name,
+		       issuer, issuer->subject.name );
+		return -EACCES_OUT_OF_ORDER;
+	}
 
-		/* Check that certificate is valid at specified time */
-		if ( ( rc = x509_validate_time ( current, time ) ) != 0 )
-			return rc;
+	/* Fail if issuing certificate cannot validate this certificate */
+	if ( ( rc = x509_check_issuer ( cert, issuer ) ) != 0 )
+		return rc;
 
-		/* Succeed if we have reached a trusted root certificate */
-		if ( x509_validate_root ( current, root ) == 0 )
-			return 0;
+	/* Fail if path length constraint is violated */
+	if ( issuer->path_remaining == 0 ) {
+		DBGC ( cert, "X509 %p \"%s\" issuer %p \"%s\" path length "
+		       "exceeded\n", cert, cert->subject.name,
+		       issuer, issuer->subject.name );
+		return -EACCES_PATH_LEN;
+	}
 
-		/* Fail if we have reached an untrusted root certificate */
-		if ( asn1_compare ( &current->issuer.raw,
-				    &current->subject.raw ) == 0 ) {
-			DBGC ( context, "X509 chain %p reached untrusted root "
-			       "certificate\n", context );
-			return -EACCES_UNTRUSTED;
-		}
+	/* Calculate effective path length */
+	cert->path_remaining = ( issuer->path_remaining - 1 );
+	max_path_remaining = ( cert->extensions.basic.path_len + 1 );
+	if ( cert->path_remaining > max_path_remaining )
+		cert->path_remaining = max_path_remaining;
 
-		/* Get next certificate in chain */
-		if ( ( rc = parse_next ( next, current, context ) ) != 0 ) {
-			DBGC ( context, "X509 chain %p could not get next "
-			       "certificate: %s\n", context, strerror ( rc ) );
-			return rc;
-		}
+	/* Mark certificate as valid */
+	cert->valid = 1;
 
-		/* Validate current certificate against next certificate */
-		if ( ( rc = x509_validate_issuer ( current, next ) ) != 0 )
-			return rc;
+	DBGC ( cert, "X509 %p \"%s\" successfully validated using issuer %p "
+	       "\"%s\"\n", cert, cert->subject.name,
+	       issuer, issuer->subject.name );
+	return 0;
+}
+
+/**
+ * Free X.509 certificate chain
+ *
+ * @v refcnt		Reference count
+ */
+static void x509_free_chain ( struct refcnt *refcnt ) {
+	struct x509_chain *chain =
+		container_of ( refcnt, struct x509_chain, refcnt );
+	struct x509_link *link;
+	struct x509_link *tmp;
+
+	DBGC ( chain, "X509 chain %p freed\n", chain );
+
+	/* Free each link in the chain */
+	list_for_each_entry_safe ( link, tmp, &chain->links, list ) {
+		x509_put ( link->cert );
+		list_del ( &link->list );
+		free ( link );
+	}
+
+	/* Free chain */
+	free ( chain );
+}
+
+/**
+ * Allocate X.509 certificate chain
+ *
+ * @ret chain		X.509 certificate chain, or NULL
+ */
+struct x509_chain * x509_alloc_chain ( void ) {
+	struct x509_chain *chain;
+
+	/* Allocate chain */
+	chain = zalloc ( sizeof ( *chain ) );
+	if ( ! chain )
+		return NULL;
+
+	/* Initialise chain */
+	ref_init ( &chain->refcnt, x509_free_chain );
+	INIT_LIST_HEAD ( &chain->links );
+
+	DBGC ( chain, "X509 chain %p allocated\n", chain );
+	return chain;
+}
+
+/**
+ * Append X.509 certificate to X.509 certificate chain
+ *
+ * @v chain		X.509 certificate chain
+ * @v cert		X.509 certificate
+ * @ret rc		Return status code
+ */
+int x509_append ( struct x509_chain *chain, struct x509_certificate *cert ) {
+	struct x509_link *link;
+
+	/* Allocate link */
+	link = zalloc ( sizeof ( *link ) );
+	if ( ! link )
+		return -ENOMEM;
+
+	/* Add link to chain */
+	link->cert = x509_get ( cert );
+	list_add_tail ( &link->list, &chain->links );
+	DBGC ( chain, "X509 chain %p added X509 %p \"%s\"\n",
+	       chain, cert, cert->subject.name );
+
+	return 0;
+}
+
+/**
+ * Validate X.509 certificate chain
+ *
+ * @v chain		X.509 certificate chain
+ * @v time		Time at which to validate certificates
+ * @v root		Root certificate store, or NULL to use default
+ * @ret rc		Return status code
+ */
+int x509_validate_chain ( struct x509_chain *chain, time_t time,
+			  struct x509_root *root ) {
+	struct x509_certificate *issuer = NULL;
+	struct x509_link *link;
+	int rc;
 
-		/* Validate path length constraint */
-		if ( path_len > next->extensions.basic.path_len ) {
-			DBGC ( context, "X509 chain %p path length %d exceeds "
-			       "maximum %d\n", context, path_len,
-			       next->extensions.basic.path_len );
-			return -EACCES_PATH_LEN;
+	/* Sanity check */
+	if ( list_empty ( &chain->links ) ) {
+		DBGC ( chain, "X509 chain %p is empty\n", chain );
+		return -EACCES_EMPTY;
+	}
+
+	/* Find first certificate that can be validated as a
+	 * standalone (i.e.  is already valid, or can be validated as
+	 * a trusted root certificate).
+	 */
+	list_for_each_entry ( link, &chain->links, list ) {
+
+		/* Try validating this certificate as a standalone */
+		if ( ( rc = x509_validate ( link->cert, NULL, time,
+					    root ) ) != 0 )
+			continue;
+
+		/* Work back up to start of chain, performing pairwise
+		 * validation.
+		 */
+		issuer = link->cert;
+		list_for_each_entry_continue_reverse ( link, &chain->links,
+						       list ) {
+
+			/* Validate this certificate against its issuer */
+			if ( ( rc = x509_validate ( link->cert, issuer, time,
+						    root ) ) != 0 )
+				return rc;
+			issuer = link->cert;
 		}
-		path_len++;
 
-		/* Move to next certificate in chain */
-		swap = current;
-		current = next;
-		next = swap;
+		return 0;
 	}
+
+	DBGC ( chain, "X509 chain %p found no valid certificates\n", chain );
+	return -EACCES_UNTRUSTED;
 }
diff --git a/src/include/ipxe/cms.h b/src/include/ipxe/cms.h
index f355bf1..eadeca4 100644
--- a/src/include/ipxe/cms.h
+++ b/src/include/ipxe/cms.h
@@ -13,37 +13,62 @@ FILE_LICENCE ( GPL2_OR_LATER );
 #include <ipxe/asn1.h>
 #include <ipxe/crypto.h>
 #include <ipxe/x509.h>
+#include <ipxe/refcnt.h>
 #include <ipxe/uaccess.h>
 
 /** CMS signer information */
 struct cms_signer_info {
-	/** Issuer name */
-	struct asn1_cursor issuer;
-	/** Serial number */
-	struct asn1_cursor serial;
+	/** List of signer information blocks */
+	struct list_head list;
+
+	/** Certificate chain */
+	struct x509_chain *chain;
+
 	/** Digest algorithm */
 	struct digest_algorithm *digest;
 	/** Public-key algorithm */
 	struct pubkey_algorithm *pubkey;
+
 	/** Signature */
-	const void *signature;
+	void *signature;
 	/** Length of signature */
 	size_t signature_len;
 };
 
 /** A CMS signature */
 struct cms_signature {
-	/** Raw certificate list */
-	struct asn1_cursor certificates;
-	/** Signer information
-	 *
-	 * We currently use only the first signer information block.
-	 */
-	struct cms_signer_info info;
+	/** Reference count */
+	struct refcnt refcnt;
+	/** List of all certificates */
+	struct x509_chain *certificates;
+	/** List of signer information blocks */
+	struct list_head info;
 };
 
-extern int cms_parse ( struct cms_signature *sig, const void *data,
-		       size_t len );
+/**
+ * Get reference to CMS signature
+ *
+ * @v sig		CMS signature
+ * @ret sig		CMS signature
+ */
+static inline __attribute__ (( always_inline )) struct cms_signature *
+cms_get ( struct cms_signature *sig ) {
+	ref_get ( &sig->refcnt );
+	return sig;
+}
+
+/**
+ * Drop reference to CMS signature
+ *
+ * @v sig		CMS signature
+ */
+static inline __attribute__ (( always_inline )) void
+cms_put ( struct cms_signature *sig ) {
+	ref_put ( &sig->refcnt );
+}
+
+extern int cms_signature ( const void *data, size_t len,
+			   struct cms_signature **sig );
 extern int cms_verify ( struct cms_signature *sig, userptr_t data, size_t len,
 			const char *name, time_t time, struct x509_root *root );
 
diff --git a/src/include/ipxe/tls.h b/src/include/ipxe/tls.h
index 7722333..07f5d3e 100644
--- a/src/include/ipxe/tls.h
+++ b/src/include/ipxe/tls.h
@@ -235,6 +235,9 @@ struct tls_session {
 	/** Public-key algorithm used for Certificate Verify (if sent) */
 	struct pubkey_algorithm *verify_pubkey;
 
+	/** Server certificate chain */
+	struct x509_chain *chain;
+
 	/** TX sequence number */
 	uint64_t tx_seq;
 	/** TX pending transmissions */
diff --git a/src/include/ipxe/x509.h b/src/include/ipxe/x509.h
index 271ed2e..b9db204 100644
--- a/src/include/ipxe/x509.h
+++ b/src/include/ipxe/x509.h
@@ -13,6 +13,8 @@ FILE_LICENCE ( GPL2_OR_LATER );
 #include <stddef.h>
 #include <time.h>
 #include <ipxe/asn1.h>
+#include <ipxe/refcnt.h>
+#include <ipxe/list.h>
 
 /** An X.509 bit string */
 struct x509_bit_string {
@@ -50,14 +52,6 @@ struct x509_validity {
 	struct x509_time not_after;
 };
 
-/** An X.509 string */
-struct x509_string {
-	/** String (not NUL-terminated) */
-	const void *data;
-	/** Length of name */
-	size_t len;
-};
-
 /** An X.509 certificate public key */
 struct x509_public_key {
 	/** Raw public key */
@@ -71,7 +65,7 @@ struct x509_subject {
 	/** Raw subject */
 	struct asn1_cursor raw;
 	/** Common name */
-	struct x509_string name;
+	char *name;
 	/** Public key information */
 	struct x509_public_key public_key;
 };
@@ -92,6 +86,13 @@ struct x509_basic_constraints {
 	unsigned int path_len;
 };
 
+/** Unlimited path length
+ *
+ * We use -2U, since this quantity represents one *fewer* than the
+ * maximum number of remaining certificates in a chain.
+ */
+#define X509_PATH_LEN_UNLIMITED -2U
+
 /** An X.509 certificate key usage */
 struct x509_key_usage {
 	/** Key usage extension is present */
@@ -131,7 +132,7 @@ enum x509_extended_key_usage_bits {
 /** X.509 certificate OCSP responder */
 struct x509_ocsp_responder {
 	/** URI */
-	struct x509_string uri;
+	char *uri;
 };
 
 /** X.509 certificate authority information access */
@@ -154,6 +155,16 @@ struct x509_extensions {
 
 /** An X.509 certificate */
 struct x509_certificate {
+	/** Reference count */
+	struct refcnt refcnt;
+	/** List of certificates in cache */
+	struct list_head list;
+
+	/** Certificate has been validated */
+	int valid;
+	/** Maximum number of subsequent certificates in chain */
+	unsigned int path_remaining;
+
 	/** Raw certificate */
 	struct asn1_cursor raw;
 	/** Version */
@@ -176,6 +187,80 @@ struct x509_certificate {
 	struct x509_extensions extensions;
 };
 
+/**
+ * Get reference to X.509 certificate
+ *
+ * @v cert		X.509 certificate
+ * @ret cert		X.509 certificate
+ */
+static inline __attribute__ (( always_inline )) struct x509_certificate *
+x509_get ( struct x509_certificate *cert ) {
+	ref_get ( &cert->refcnt );
+	return cert;
+}
+
+/**
+ * Drop reference to X.509 certificate
+ *
+ * @v cert		X.509 certificate
+ */
+static inline __attribute__ (( always_inline )) void
+x509_put ( struct x509_certificate *cert ) {
+	ref_put ( &cert->refcnt );
+}
+
+/** A link in an X.509 certificate chain */
+struct x509_link {
+	/** List of links */
+	struct list_head list;
+	/** Certificate */
+	struct x509_certificate *cert;
+};
+
+/** An X.509 certificate chain */
+struct x509_chain {
+	/** Reference count */
+	struct refcnt refcnt;
+	/** List of links */
+	struct list_head links;
+};
+
+/**
+ * Get reference to X.509 certificate chain
+ *
+ * @v chain		X.509 certificate chain
+ * @ret chain		X.509 certificate chain
+ */
+static inline __attribute__ (( always_inline )) struct x509_chain *
+x509_chain_get ( struct x509_chain *chain ) {
+	ref_get ( &chain->refcnt );
+	return chain;
+}
+
+/**
+ * Drop reference to X.509 certificate chain
+ *
+ * @v chain		X.509 certificate chain
+ */
+static inline __attribute__ (( always_inline )) void
+x509_chain_put ( struct x509_chain *chain ) {
+	ref_put ( &chain->refcnt );
+}
+
+/**
+ * Get first certificate in X.509 certificate chain
+ *
+ * @v chain		X.509 certificate chain
+ * @ret cert		X.509 certificate, or NULL
+ */
+static inline __attribute__ (( always_inline )) struct x509_certificate *
+x509_first ( struct x509_chain *chain ) {
+	struct x509_link *link;
+
+	link = list_first_entry ( &chain->links, struct x509_link, list );
+	return ( link ? link->cert : NULL );
+}
+
 /** An X.509 extension */
 struct x509_extension {
 	/** Name */
@@ -228,22 +313,45 @@ struct x509_root {
 	const void *fingerprints;
 };
 
-extern int x509_parse ( struct x509_certificate *cert,
-			const void *data, size_t len );
-extern int x509_validate_issuer ( struct x509_certificate *cert,
-				  struct x509_certificate *issuer );
+extern int x509_certificate ( const void *data, size_t len,
+			      struct x509_certificate **cert );
+
+extern struct x509_chain * x509_alloc_chain ( void );
+extern int x509_append ( struct x509_chain *chain,
+			 struct x509_certificate *cert );
+extern int x509_validate_chain ( struct x509_chain *chain, time_t time,
+				 struct x509_root *root );
+
+/* Functions exposed only for unit testing */
+extern int x509_check_issuer ( struct x509_certificate *cert,
+			       struct x509_certificate *issuer );
 extern void x509_fingerprint ( struct x509_certificate *cert,
 			       struct digest_algorithm *digest,
 			       void *fingerprint );
-extern int x509_validate_root ( struct x509_certificate *cert,
-				struct x509_root *root );
-extern int x509_validate_time ( struct x509_certificate *cert, time_t time );
-extern int x509_validate_chain ( int ( * parse_next )
-				 ( struct x509_certificate *cert,
-				   const struct x509_certificate *previous,
-				   void *context ),
-				 void *context, time_t time,
-				 struct x509_root *root,
-				 struct x509_certificate *first );
+extern int x509_check_root ( struct x509_certificate *cert,
+			     struct x509_root *root );
+extern int x509_check_time ( struct x509_certificate *cert, time_t time );
+
+/**
+ * Invalidate X.509 certificate
+ *
+ * @v cert		X.509 certificate
+ */
+static inline void x509_invalidate ( struct x509_certificate *cert ) {
+	cert->valid = 0;
+	cert->path_remaining = 0;
+}
+
+/**
+ * Invalidate X.509 certificate chain
+ *
+ * @v chain		X.509 certificate chain
+ */
+static inline void x509_invalidate_chain ( struct x509_chain *chain ) {
+	struct x509_link *link;
+
+	list_for_each_entry ( link, &chain->links, list )
+		x509_invalidate ( link->cert );
+}
 
 #endif /* _IPXE_X509_H */
diff --git a/src/net/tls.c b/src/net/tls.c
index 3d46a2c..0624215 100644
--- a/src/net/tls.c
+++ b/src/net/tls.c
@@ -46,10 +46,6 @@ FILE_LICENCE ( GPL2_OR_LATER );
 #include <ipxe/tls.h>
 
 /* Disambiguate the various error causes */
-#define EACCES_INCOMPLETE \
-	__einfo_error ( EINFO_EACCES_INCOMPLETE )
-#define EINFO_EACCES_INCOMPLETE \
-	__einfo_uniqify ( EINFO_EACCES, 0x01, "Incomplete certificate chain" )
 #define EACCES_WRONG_NAME \
 	__einfo_error ( EINFO_EACCES_WRONG_NAME )
 #define EINFO_EACCES_WRONG_NAME \
@@ -184,6 +180,7 @@ static void free_tls ( struct refcnt *refcnt ) {
 	tls_clear_cipher ( tls, &tls->rx_cipherspec );
 	tls_clear_cipher ( tls, &tls->rx_cipherspec_pending );
 	free ( tls->rx_data );
+	x509_chain_put ( tls->chain );
 
 	/* Free TLS structure itself */
 	free ( tls );	
@@ -899,7 +896,7 @@ static int tls_send_certificate ( struct tls_session *tls ) {
 			uint8_t data[ client_certificate.len ];
 		} __attribute__ (( packed )) certificates[num_certificates];
 	} __attribute__ (( packed )) *certificate;
-	struct x509_certificate cert;
+	struct x509_certificate *cert;
 	int rc;
 
 	/* If we have a certificate to send, determine the applicable
@@ -909,13 +906,16 @@ static int tls_send_certificate ( struct tls_session *tls ) {
 	if ( num_certificates ) {
 
 		/* Parse certificate to determine public-key algorithm */
-		if ( ( rc = x509_parse ( &cert, client_certificate.data,
-					 client_certificate.len ) ) != 0 ) {
+		if ( ( rc = x509_certificate ( client_certificate.data,
+					       client_certificate.len,
+					       &cert ) ) != 0 ) {
 			DBGC ( tls, "TLS %p could not parse client "
 			       "certificate: %s\n", tls, strerror ( rc ) );
 			return rc;
 		}
-		tls->verify_pubkey = cert.signature_algorithm->pubkey;
+		tls->verify_pubkey = cert->signature_algorithm->pubkey;
+		x509_put ( cert );
+		cert = NULL;
 
 		/* Schedule CertificateVerify transmission */
 		tls->tx_pending |= TLS_TX_CERTIFICATE_VERIFY;
@@ -1267,64 +1267,88 @@ static int tls_new_server_hello ( struct tls_session *tls,
 	return 0;
 }
 
-/** TLS certificate chain context */
-struct tls_certificate_context {
-	/** TLS session */
-	struct tls_session *tls;
-	/** Current certificate */
-	const void *current;
-	/** End of certificates */
-	const void *end;
-};
-
 /**
- * Parse next certificate in TLS certificate list
+ * Parse certificate chain
  *
- * @v cert		X.509 certificate to fill in
- * @v previous		Previous X.509 certificate, or NULL
- * @v ctx		Context
+ * @v tls		TLS session
+ * @v data		Certificate chain
+ * @v len		Length of certificate chain
  * @ret rc		Return status code
  */
-static int tls_parse_next ( struct x509_certificate *cert,
-			    const struct x509_certificate *previous __unused,
-			    void *ctx ) {
-	struct tls_certificate_context *context = ctx;
-	struct tls_session *tls = context->tls;
+static int tls_parse_chain ( struct tls_session *tls,
+			     const void *data, size_t len ) {
+	const void *end = ( data + len );
 	const struct {
 		uint8_t length[3];
-		uint8_t certificate[0];
-	} __attribute__ (( packed )) *current = context->current;
-	const void *data;
+		uint8_t data[0];
+	} __attribute__ (( packed )) *certificate;
+	size_t certificate_len;
+	struct x509_certificate *cert;
 	const void *next;
-	size_t len;
 	int rc;
 
-	/* Return error at end of chain */
-	if ( context->current >= context->end ) {
-		DBGC ( tls, "TLS %p reached end of certificate chain\n", tls );
-		return -EACCES_INCOMPLETE;
-	}
+	/* Free any existing certificate chain */
+	x509_chain_put ( tls->chain );
+	tls->chain = NULL;
 
-	/* Extract current certificate and update context */
-	data = current->certificate;
-	len = tls_uint24 ( current->length );
-	next = ( data + len );
-	if ( next > context->end ) {
-		DBGC ( tls, "TLS %p overlength certificate\n", tls );
-		DBGC_HDA ( tls, 0, context->current,
-			   ( context->end - context->current ) );
-		return -EINVAL;
+	/* Create certificate chain */
+	tls->chain = x509_alloc_chain();
+	if ( ! tls->chain ) {
+		rc = -ENOMEM;
+		goto err_alloc_chain;
 	}
-	context->current = next;
 
-	/* Parse current certificate */
-	if ( ( rc = x509_parse ( cert, data, len ) ) != 0 ) {
-		DBGC ( tls, "TLS %p could not parse certificate: %s\n",
-		       tls, strerror ( rc ) );
-		return rc;
+	/* Add certificates to chain */
+	while ( data < end ) {
+
+		/* Extract raw certificate data */
+		certificate = data;
+		certificate_len = tls_uint24 ( certificate->length );
+		next = ( certificate->data + certificate_len );
+		if ( next > end ) {
+			DBGC ( tls, "TLS %p overlength certificate:\n", tls );
+			DBGC_HDA ( tls, 0, data, ( end - data ) );
+			rc = -EINVAL;
+			goto err_overlength;
+		}
+
+		/* Parse certificate */
+		if ( ( rc = x509_certificate ( certificate->data,
+					       certificate_len,
+					       &cert ) ) != 0 ) {
+			DBGC ( tls, "TLS %p could not parse certificate: %s\n",
+			       tls, strerror ( rc ) );
+			DBGC_HDA ( tls, 0, data, ( end - data ) );
+			goto err_parse;
+		}
+		DBGC ( tls, "TLS %p found certificate %s\n",
+		       tls, cert->subject.name );
+
+		/* Append certificate to chain */
+		if ( ( rc = x509_append ( tls->chain, cert ) ) != 0 ) {
+			DBGC ( tls, "TLS %p could not append certificate: %s\n",
+			       tls, strerror ( rc ) );
+			goto err_append;
+		}
+
+		/* Drop reference to certificate */
+		x509_put ( cert );
+		cert = NULL;
+
+		/* Move to next certificate in list */
+		data = next;
 	}
 
 	return 0;
+
+ err_append:
+	x509_put ( cert );
+ err_parse:
+ err_overlength:
+	x509_chain_put ( tls->chain );
+	tls->chain = NULL;
+ err_alloc_chain:
+	return rc;
 }
 
 /**
@@ -1341,14 +1365,11 @@ static int tls_new_certificate ( struct tls_session *tls,
 		uint8_t length[3];
 		uint8_t certificates[0];
 	} __attribute__ (( packed )) *certificate = data;
-	size_t elements_len = tls_uint24 ( certificate->length );
-	const void *end = ( certificate->certificates + elements_len );
+	size_t certificates_len = tls_uint24 ( certificate->length );
+	const void *end = ( certificate->certificates + certificates_len );
 	struct tls_cipherspec *cipherspec = &tls->tx_cipherspec_pending;
 	struct pubkey_algorithm *pubkey = cipherspec->suite->pubkey;
-	struct tls_certificate_context context;
-	struct x509_certificate cert;
-	struct x509_string *name = &cert.subject.name;
-	struct x509_public_key *key = &cert.subject.public_key;
+	struct x509_certificate *cert;
 	time_t now;
 	int rc;
 
@@ -1360,28 +1381,34 @@ static int tls_new_certificate ( struct tls_session *tls,
 		return -EINVAL;
 	}
 
-	/* Parse first certificate and validate certificate chain */
-	context.tls = tls;
-	context.current = certificate->certificates;
-	context.end = end;
+	/* Parse certificate chain */
+	if ( ( rc = tls_parse_chain ( tls, certificate->certificates,
+				      certificates_len ) ) != 0 )
+		return rc;
+
+	/* Validate certificate chain */
 	now = time ( NULL );
-	if ( ( rc = x509_validate_chain ( tls_parse_next, &context,
-					  now, NULL, &cert ) ) != 0 ) {
+	if ( ( rc = x509_validate_chain ( tls->chain, now, NULL ) ) != 0 ) {
 		DBGC ( tls, "TLS %p could not validate certificate chain: %s\n",
 		       tls, strerror ( rc ) );
 		return rc;
 	}
 
+	/* Extract first certificate */
+	cert = x509_first ( tls->chain );
+	assert ( cert != NULL );
+
 	/* Verify server name */
-	if ( ( name->len != strlen ( tls->name ) ) ||
-	     ( memcmp ( name->data, tls->name, name->len ) != 0 ) ) {
-		DBGC ( tls, "TLS %p server name incorrect\n", tls );
+	if ( strcmp ( tls->name, cert->subject.name ) != 0 ) {
+		DBGC ( tls, "TLS %p server name incorrect (expected %s, got "
+		       "%s)\n", tls, tls->name, cert->subject.name );
 		return -EACCES_WRONG_NAME;
 	}
 
 	/* Initialise public key algorithm */
 	if ( ( rc = pubkey_init ( pubkey, cipherspec->pubkey_ctx,
-				  key->raw.data, key->raw.len ) ) != 0 ) {
+				  cert->subject.public_key.raw.data,
+				  cert->subject.public_key.raw.len ) ) != 0 ) {
 		DBGC ( tls, "TLS %p cannot initialise public key: %s\n",
 		       tls, strerror ( rc ) );
 		return rc;
diff --git a/src/tests/cms_test.c b/src/tests/cms_test.c
index 5179651..9de0228 100644
--- a/src/tests/cms_test.c
+++ b/src/tests/cms_test.c
@@ -52,6 +52,9 @@ struct cms_test_signature {
 	const void *data;
 	/** Length of data */
 	size_t len;
+
+	/** Parsed signature */
+	struct cms_signature *sig;
 };
 
 /** Define inline data */
@@ -1331,42 +1334,40 @@ static time_t test_expired = 1375573111ULL; /* Sat Aug  3 23:38:31 2013 */
 /**
  * Report signature parsing test result
  *
- * @v sig		Test signature
+ * @v sgn		Test signature
  */
-#define cms_parse_ok( sig ) do {					\
-	struct cms_signature temp;					\
-	ok ( cms_parse ( &temp, (sig)->data, (sig)->len ) == 0 );	\
+#define cms_signature_ok( sgn ) do {					\
+	ok ( cms_signature ( (sgn)->data, (sgn)->len,			\
+			     &(sgn)->sig ) == 0 );			\
 	} while ( 0 )
 
 /**
  * Report signature verification test result
  *
- * @v sig		Test signature
+ * @v sgn		Test signature
  * @v code		Test signed code
  * @v name		Test verification name
  * @v time		Test verification time
  * @v root		Test root certificate store
  */
-#define cms_verify_ok( sig, code, name, time, root ) do {		\
-	struct cms_signature temp;					\
-	ok ( cms_parse ( &temp, (sig)->data, (sig)->len ) == 0 );	\
-	ok ( cms_verify ( &temp, virt_to_user ( (code)->data ),		\
+#define cms_verify_ok( sgn, code, name, time, root ) do {		\
+	x509_invalidate_chain ( (sgn)->sig->certificates );		\
+	ok ( cms_verify ( (sgn)->sig, virt_to_user ( (code)->data ),	\
 			  (code)->len, name, time, root ) == 0 );	\
 	} while ( 0 )
 
 /**
  * Report signature verification failure test result
  *
- * @v sig		Test signature
+ * @v sgn		Test signature
  * @v code		Test signed code
  * @v name		Test verification name
  * @v time		Test verification time
  * @v root		Test root certificate store
  */
-#define cms_verify_fail_ok( sig, code, name, time, root ) do {		\
-	struct cms_signature temp;					\
-	ok ( cms_parse ( &temp, (sig)->data, (sig)->len ) == 0 );	\
-	ok ( cms_verify ( &temp, virt_to_user ( (code)->data ),		\
+#define cms_verify_fail_ok( sgn, code, name, time, root ) do {		\
+	x509_invalidate_chain ( (sgn)->sig->certificates );		\
+	ok ( cms_verify ( (sgn)->sig, virt_to_user ( (code)->data ),	\
 			  (code)->len, name, time, root ) != 0 );	\
 	} while ( 0 )
 
@@ -1377,10 +1378,10 @@ static time_t test_expired = 1375573111ULL; /* Sat Aug  3 23:38:31 2013 */
 static void cms_test_exec ( void ) {
 
 	/* Check that all signatures can be parsed */
-	cms_parse_ok ( &codesigned_sig );
-	cms_parse_ok ( &brokenchain_sig );
-	cms_parse_ok ( &genericsigned_sig );
-	cms_parse_ok ( &nonsigned_sig );
+	cms_signature_ok ( &codesigned_sig );
+	cms_signature_ok ( &brokenchain_sig );
+	cms_signature_ok ( &genericsigned_sig );
+	cms_signature_ok ( &nonsigned_sig );
 
 	/* Check good signature */
 	cms_verify_ok ( &codesigned_sig, &test_code,
@@ -1415,6 +1416,12 @@ static void cms_test_exec ( void ) {
 	/* Check expired signature */
 	cms_verify_fail_ok ( &codesigned_sig, &test_code,
 			     NULL, test_expired, &test_root );
+
+	/* Drop signature references */
+	cms_put ( nonsigned_sig.sig );
+	cms_put ( genericsigned_sig.sig );
+	cms_put ( brokenchain_sig.sig );
+	cms_put ( codesigned_sig.sig );
 }
 
 /** CMS self-test */
diff --git a/src/tests/x509_test.c b/src/tests/x509_test.c
index 7803315..3a3c9d0 100644
--- a/src/tests/x509_test.c
+++ b/src/tests/x509_test.c
@@ -31,6 +31,7 @@ FILE_LICENCE ( GPL2_OR_LATER );
 #include <string.h>
 #include <errno.h>
 #include <ipxe/x509.h>
+#include <ipxe/asn1.h>
 #include <ipxe/sha256.h>
 #include <ipxe/test.h>
 
@@ -45,6 +46,9 @@ struct x509_test_certificate {
 	size_t len;
 	/** Fingerprint */
 	const void *fingerprint;
+
+	/** Parsed certificate */
+	struct x509_certificate *cert;
 };
 
 /** An X.509 test certificate chain */
@@ -53,6 +57,9 @@ struct x509_test_chain {
 	struct x509_test_certificate **certs;
 	/** Number of certificates */
 	unsigned int count;
+
+	/** Parsed certificate chain */
+	struct x509_chain *chain;
 };
 
 /** Define inline certificate data */
@@ -683,172 +690,147 @@ static time_t test_expired = 1375573111ULL; /* Sat Aug  3 23:38:31 2013 */
 /** Time at which CA test certificates are invalid */
 static time_t test_ca_expired = 2205014905ULL; /* Wed Nov 16 00:08:25 2039 */
 
-/** An X.509 test certificate chain context */
-struct x509_test_chain_context {
-	/** Test certificate chain */
-	struct x509_test_chain *chain;
-	/** Index within chain */
-	unsigned int index;
-};
-
 /**
- * Parse next certificate in chain
+ * Report certificate parsing test result
  *
- * @v cert		X.509 certificate to parse
- * @v previous		Previous X.509 certificate, or NULL
- * @v ctx		Chain context
- * @ret rc		Return status code
+ * @v crt		Test certificate
  */
-static int
-x509_test_parse_next ( struct x509_certificate *cert,
-		       const struct x509_certificate *previous __unused,
-		       void *ctx ) {
-	struct x509_test_chain_context *context = ctx;
-	struct x509_test_certificate *test_cert;
-
-	/* Return error at end of chain */
-	if ( context->index >= context->chain->count )
-		return -ENOENT;
-
-	/* Get next test certificate */
-	test_cert = context->chain->certs[ context->index++ ];
-
-	/* Parse certificate */
-	return x509_parse ( cert, test_cert->data, test_cert->len );
-}
+#define x509_certificate_ok( crt ) do {					\
+	ok ( x509_certificate ( (crt)->data, (crt)->len,		\
+				&(crt)->cert ) == 0 );			\
+	} while ( 0 )
 
 /**
- * Report certificate parsing test result
+ * Report cached certificate parsing test result
  *
- * @v cert		Test certificate
+ * @v crt		Test certificate
  */
-#define x509_parse_ok( cert ) do {					\
-	struct x509_certificate temp;					\
-	ok ( x509_parse ( &temp, (cert)->data, (cert)->len ) == 0 );	\
+#define x509_cached_ok( crt ) do {					\
+	struct x509_certificate *temp;					\
+	ok ( x509_certificate ( (crt)->data, (crt)->len,		\
+				&temp ) == 0 );				\
+	ok ( temp == (crt)->cert );					\
+	x509_put ( temp );						\
 	} while ( 0 )
 
 /**
  * Report certificate fingerprint test result
  *
- * @v cert		Test certificate
+ * @v crt		Test certificate
  */
-#define x509_fingerprint_ok( cert ) do {				\
-	struct x509_certificate temp;					\
+#define x509_fingerprint_ok( crt ) do {					\
 	uint8_t fingerprint[ x509_test_algorithm.digestsize ];		\
-	ok ( x509_parse ( &temp, (cert)->data, (cert)->len ) == 0 );	\
-	x509_fingerprint ( &temp, &x509_test_algorithm, fingerprint );	\
-	ok ( memcmp ( fingerprint, (cert)->fingerprint,			\
+	x509_fingerprint ( (crt)->cert, &x509_test_algorithm,		\
+			   fingerprint );				\
+	ok ( memcmp ( fingerprint, (crt)->fingerprint,			\
 		      sizeof ( fingerprint ) ) == 0 );			\
 	} while ( 0 )
 
 /**
  * Report certificate issuer validation test result
  *
- * @v cert		Test certificate
+ * @v crt		Test certificate
  * @v issuer		Test issuer
  */
-#define x509_validate_issuer_ok( cert, issuer ) do {			\
-	struct x509_certificate cert_temp;				\
-	struct x509_certificate issuer_temp;				\
-	ok ( x509_parse ( &cert_temp, (cert)->data,			\
-			  (cert)->len ) == 0 );				\
-	ok ( x509_parse ( &issuer_temp, (issuer)->data,			\
-			  (issuer)->len ) == 0 );			\
-	ok ( x509_validate_issuer ( &cert_temp, &issuer_temp ) == 0 );	\
+#define x509_check_issuer_ok( crt, issuer ) do {			\
+	ok ( x509_check_issuer ( (crt)->cert, (issuer)->cert ) == 0 );	\
 	} while ( 0 )
 
 /**
  * Report certificate issuer validation failure test result
  *
- * @v cert		Test certificate
+ * @v crt		Test certificate
  * @v issuer		Test issuer
  */
-#define x509_validate_issuer_fail_ok( cert, issuer ) do {		\
-	struct x509_certificate cert_temp;				\
-	struct x509_certificate issuer_temp;				\
-	ok ( x509_parse ( &cert_temp, (cert)->data,			\
-			  (cert)->len ) == 0 );				\
-	ok ( x509_parse ( &issuer_temp, (issuer)->data,			\
-			  (issuer)->len ) == 0 );			\
-	ok ( x509_validate_issuer ( &cert_temp, &issuer_temp ) != 0 );	\
+#define x509_check_issuer_fail_ok( crt, issuer ) do {			\
+	ok ( x509_check_issuer ( (crt)->cert, (issuer)->cert ) != 0 );	\
 	} while ( 0 )
 
 /**
  * Report certificate root validation test result
  *
- * @v cert		Test certificate
+ * @v crt		Test certificate
  * @v root		Test root certificate store
  */
-#define x509_validate_root_ok( cert, root ) do {			\
-	struct x509_certificate temp;					\
-	ok ( x509_parse ( &temp, (cert)->data, (cert)->len ) == 0 );	\
-	ok ( x509_validate_root ( &temp, root ) == 0 );			\
+#define x509_check_root_ok( crt, root ) do {				\
+	ok ( x509_check_root ( (crt)->cert, root ) == 0 );		\
 	} while ( 0 )
 
 /**
  * Report certificate root validation failure test result
  *
- * @v cert		Test certificate
+ * @v crt		Test certificate
  * @v root		Test root certificate store
  */
-#define x509_validate_root_fail_ok( cert, root ) do {			\
-	struct x509_certificate temp;					\
-	ok ( x509_parse ( &temp, (cert)->data, (cert)->len ) == 0 );	\
-	ok ( x509_validate_root ( &temp, root ) != 0 );			\
+#define x509_check_root_fail_ok( crt, root ) do {			\
+	ok ( x509_check_root ( (crt)->cert, root ) != 0 );		\
 	} while ( 0 )
 
 /**
  * Report certificate time validation test result
  *
- * @v cert		Test certificate
+ * @v crt		Test certificate
  * @v time		Test time
  */
-#define x509_validate_time_ok( cert, time ) do {			\
-	struct x509_certificate temp;					\
-	ok ( x509_parse ( &temp, (cert)->data, (cert)->len ) == 0 );	\
-	ok ( x509_validate_time ( &temp, time ) == 0 );			\
+#define x509_check_time_ok( crt, time ) do {				\
+	ok ( x509_check_time ( (crt)->cert, time ) == 0 );		\
 	} while ( 0 )
 
 /**
  * Report certificate time validation failure test result
  *
- * @v cert		Test certificate
+ * @v crt		Test certificate
  * @v time		Test time
  */
-#define x509_validate_time_fail_ok( cert, time ) do {			\
-	struct x509_certificate temp;					\
-	ok ( x509_parse ( &temp, (cert)->data, (cert)->len ) == 0 );	\
-	ok ( x509_validate_time ( &temp, time ) != 0 );			\
+#define x509_check_time_fail_ok( crt, time ) do {			\
+	ok ( x509_check_time ( (crt)->cert, time ) != 0 );		\
+	} while ( 0 )
+
+/**
+ * Report certificate chain parsing test result
+ *
+ * @v chn		Test certificate chain
+ */
+#define x509_chain_ok( chn ) do {					\
+	unsigned int i;							\
+	struct x509_certificate *first;					\
+	(chn)->chain = x509_alloc_chain();				\
+	ok ( (chn)->chain != NULL );					\
+	for ( i = 0 ; i < (chn)->count ; i++ ) {			\
+		ok ( x509_append ( (chn)->chain,			\
+				   (chn)->certs[i]->cert ) == 0 );	\
+	}								\
+	first = x509_first ( (chn)->chain );				\
+	ok ( first != NULL );						\
+	ok ( first->raw.len == (chn)->certs[0]->len );			\
+	ok ( memcmp ( first->raw.data, (chn)->certs[0]->data,		\
+		      first->raw.len ) == 0 );				\
 	} while ( 0 )
 
 /**
  * Report certificate chain validation test result
  *
- * @v chain		Test certificate chain
+ * @v chn		Test certificate chain
  * @v time		Test certificate validation time
  * @v root		Test root certificate store
  */
-#define x509_validate_chain_ok( chain, time, root ) do {		\
-	struct x509_test_chain_context context = { (chain), 0 };	\
-	struct x509_certificate temp;					\
-	ok ( x509_validate_chain ( x509_test_parse_next, &context,	\
-				   (time), (root), &temp ) == 0 );	\
-	ok ( temp.raw.data == (chain)->certs[0]->data );		\
-	ok ( temp.raw.len == (chain)->certs[0]->len );			\
+#define x509_validate_chain_ok( chn, time, root ) do {			\
+	x509_invalidate_chain ( (chn)->chain );				\
+	ok ( x509_validate_chain ( (chn)->chain, (time),		\
+				   (root) ) == 0 );			\
 	} while ( 0 )
 
 /**
  * Report certificate chain validation failure test result
  *
- * @v chain		Test certificate chain
+ * @v chn		Test certificate chain
  * @v time		Test certificate validation time
  * @v root		Test root certificate store
  */
-#define x509_validate_chain_fail_ok( chain, time, root ) do {		\
-	struct x509_test_chain_context context = { (chain), 0 };	\
-	struct x509_certificate temp;					\
-	ok ( x509_validate_chain ( x509_test_parse_next, &context,	\
-				   (time), (root), &temp ) != 0 );	\
+#define x509_validate_chain_fail_ok( chn, time, root ) do {		\
+	x509_invalidate_chain ( (chn)->chain );				\
+	ok ( x509_validate_chain ( (chn)->chain, (time),		\
+				   (root) ) != 0 );			\
 	} while ( 0 )
 
 /**
@@ -857,6 +839,24 @@ x509_test_parse_next ( struct x509_certificate *cert,
  */
 static void x509_test_exec ( void ) {
 
+	/* Parse all certificates */
+	x509_certificate_ok ( &root_crt );
+	x509_certificate_ok ( &intermediate_crt );
+	x509_certificate_ok ( &leaf_crt );
+	x509_certificate_ok ( &useless_crt );
+	x509_certificate_ok ( &server_crt );
+	x509_certificate_ok ( &not_ca_crt );
+	x509_certificate_ok ( &bad_path_len_crt );
+
+	/* Check cache functionality */
+	x509_cached_ok ( &root_crt );
+	x509_cached_ok ( &intermediate_crt );
+	x509_cached_ok ( &leaf_crt );
+	x509_cached_ok ( &useless_crt );
+	x509_cached_ok ( &server_crt );
+	x509_cached_ok ( &not_ca_crt );
+	x509_cached_ok ( &bad_path_len_crt );
+
 	/* Check all certificate fingerprints */
 	x509_fingerprint_ok ( &root_crt );
 	x509_fingerprint_ok ( &intermediate_crt );
@@ -867,26 +867,34 @@ static void x509_test_exec ( void ) {
 	x509_fingerprint_ok ( &bad_path_len_crt );
 
 	/* Check pairwise issuing */
-	x509_validate_issuer_ok ( &intermediate_crt, &root_crt );
-	x509_validate_issuer_ok ( &leaf_crt, &intermediate_crt );
-	x509_validate_issuer_ok ( &useless_crt, &leaf_crt );
-	x509_validate_issuer_ok ( &server_crt, &leaf_crt );
-	x509_validate_issuer_fail_ok ( &not_ca_crt, &server_crt );
-	x509_validate_issuer_ok ( &bad_path_len_crt, &useless_crt );
+	x509_check_issuer_ok ( &intermediate_crt, &root_crt );
+	x509_check_issuer_ok ( &leaf_crt, &intermediate_crt );
+	x509_check_issuer_ok ( &useless_crt, &leaf_crt );
+	x509_check_issuer_ok ( &server_crt, &leaf_crt );
+	x509_check_issuer_fail_ok ( &not_ca_crt, &server_crt );
+	x509_check_issuer_ok ( &bad_path_len_crt, &useless_crt );
 
 	/* Check root certificate stores */
-	x509_validate_root_ok ( &root_crt, &test_root );
-	x509_validate_root_fail_ok ( &intermediate_crt, &test_root );
-	x509_validate_root_ok ( &intermediate_crt, &intermediate_root );
-	x509_validate_root_fail_ok ( &root_crt, &intermediate_root );
-	x509_validate_root_fail_ok ( &root_crt, &dummy_root );
+	x509_check_root_ok ( &root_crt, &test_root );
+	x509_check_root_fail_ok ( &intermediate_crt, &test_root );
+	x509_check_root_ok ( &intermediate_crt, &intermediate_root );
+	x509_check_root_fail_ok ( &root_crt, &intermediate_root );
+	x509_check_root_fail_ok ( &root_crt, &dummy_root );
 
 	/* Check certificate validity periods */
-	x509_validate_time_ok ( &server_crt, test_time );
-	x509_validate_time_fail_ok ( &server_crt, test_expired );
-	x509_validate_time_ok ( &root_crt, test_time );
-	x509_validate_time_ok ( &root_crt, test_expired );
-	x509_validate_time_fail_ok ( &root_crt, test_ca_expired );
+	x509_check_time_ok ( &server_crt, test_time );
+	x509_check_time_fail_ok ( &server_crt, test_expired );
+	x509_check_time_ok ( &root_crt, test_time );
+	x509_check_time_ok ( &root_crt, test_expired );
+	x509_check_time_fail_ok ( &root_crt, test_ca_expired );
+
+	/* Parse all certificate chains */
+	x509_chain_ok ( &server_chain );
+	x509_chain_ok ( &broken_server_chain );
+	x509_chain_ok ( &incomplete_server_chain );
+	x509_chain_ok ( &not_ca_chain );
+	x509_chain_ok ( &useless_chain );
+	x509_chain_ok ( &bad_path_len_chain );
 
 	/* Check certificate chains */
 	x509_validate_chain_ok ( &server_chain, test_time, &test_root );
@@ -908,6 +916,23 @@ static void x509_test_exec ( void ) {
 	x509_validate_chain_ok ( &useless_chain, test_expired, &test_root );
 	x509_validate_chain_fail_ok ( &useless_chain, test_ca_expired,
 				      &test_root );
+
+	/* Drop chain references */
+	x509_chain_put ( bad_path_len_chain.chain );
+	x509_chain_put ( useless_chain.chain );
+	x509_chain_put ( not_ca_chain.chain );
+	x509_chain_put ( incomplete_server_chain.chain );
+	x509_chain_put ( broken_server_chain.chain );
+	x509_chain_put ( server_chain.chain );
+
+	/* Drop certificate references */
+	x509_put ( bad_path_len_crt.cert );
+	x509_put ( not_ca_crt.cert );
+	x509_put ( server_crt.cert );
+	x509_put ( useless_crt.cert );
+	x509_put ( leaf_crt.cert );
+	x509_put ( intermediate_crt.cert );
+	x509_put ( root_crt.cert );
 }
 
 /** X.509 self-test */
diff --git a/src/usr/imgtrust.c b/src/usr/imgtrust.c
index 5966078..651f049 100644
--- a/src/usr/imgtrust.c
+++ b/src/usr/imgtrust.c
@@ -45,7 +45,7 @@ int imgverify ( struct image *image, struct image *signature,
 		const char *name ) {
 	size_t len;
 	void *data;
-	struct cms_signature sig;
+	struct cms_signature *sig;
 	time_t now;
 	int rc;
 
@@ -62,25 +62,31 @@ int imgverify ( struct image *image, struct image *signature,
 	copy_from_user ( data, signature->data, 0, len );
 
 	/* Parse signature */
-	if ( ( rc = cms_parse ( &sig, data, len ) ) != 0 )
+	if ( ( rc = cms_signature ( data, len, &sig ) ) != 0 )
 		goto err_parse;
 
+	/* Free internal copy of signature */
+	free ( data );
+	data = NULL;
+
 	/* Use signature to verify image */
 	now = time ( NULL );
-	if ( ( rc = cms_verify ( &sig, image->data, image->len,
+	if ( ( rc = cms_verify ( sig, image->data, image->len,
 				 name, now, NULL ) ) != 0 )
 		goto err_verify;
 
+	/* Drop reference to signature */
+	cms_put ( sig );
+	sig = NULL;
+
 	/* Mark image as trusted */
 	image_trust ( image );
 	syslog ( LOG_NOTICE, "Image \"%s\" signature OK\n", image->name );
 
-	/* Free internal copy of signature */
-	free ( data );
-
 	return 0;
 
  err_verify:
+	cms_put ( sig );
  err_parse:
 	free ( data );
  err_alloc: