[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>

2 files changed, 636 insertions, 225 deletions

diff --git a/src/crypto/cms.c b/src/crypto/cms.c
index 04fc2a88..ee09dff3 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 a0ed816d..be2e1009 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;
 }