[crypto] Generalise X.509 cache to a full certificate store

Expand the concept of the X.509 cache to provide the functionality of
a certificate store.  Certificates in the store will be automatically
used to complete certificate chains where applicable.

The certificate store may be prepopulated at build time using the
CERT=... build command line option.  For example:

  make bin/ipxe.usb CERT=mycert1.crt,mycert2.crt

Certificates within the certificate store are not implicitly trusted;
the trust list is specified using TRUST=... as before.  For example:

  make bin/ipxe.usb CERT=root.crt TRUST=root.crt

This can be used to embed the full trusted root certificate within the
iPXE binary, which is potentially useful in an HTTPS-only environment
in which there is no HTTP server from which to automatically download
cross-signed certificates or other certificate chain fragments.

This usage of CERT= extends the existing use of CERT= to specify the
client certificate.  The client certificate is now identified
automatically by checking for a match against the private key.  For
example:

  make bin/ipxe.usb CERT=root.crt,client.crt TRUST=root.crt KEY=client.key

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

5 files changed, 437 insertions, 238 deletions

diff --git a/src/crypto/certstore.c b/src/crypto/certstore.c
new file mode 100644
index 00000000..77cf6ebb
--- /dev/null
+++ b/src/crypto/certstore.c
@@ -0,0 +1,275 @@
+/*
+ * Copyright (C) 2014 Michael Brown <mbrown@fensystems.co.uk>.
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License as
+ * published by the Free Software Foundation; either version 2 of the
+ * License, or any later version.
+ *
+ * This program is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
+ * 02110-1301, USA.
+ */
+
+FILE_LICENCE ( GPL2_OR_LATER );
+
+#include <string.h>
+#include <stdlib.h>
+#include <ipxe/init.h>
+#include <ipxe/dhcp.h>
+#include <ipxe/settings.h>
+#include <ipxe/malloc.h>
+#include <ipxe/crypto.h>
+#include <ipxe/asn1.h>
+#include <ipxe/x509.h>
+#include <ipxe/certstore.h>
+
+/** @file
+ *
+ * Certificate store
+ *
+ */
+
+/** Raw certificate data for all permanent stored certificates */
+#undef CERT
+#define CERT( _index, _path )						\
+	extern char stored_cert_ ## _index ## _data[];			\
+	extern char stored_cert_ ## _index ## _len[];			\
+	__asm__ ( ".section \".rodata\", \"a\", @progbits\n\t"		\
+		  "\nstored_cert_" #_index "_data:\n\t"			\
+		  ".incbin \"" _path "\"\n\t"				\
+		  "\nstored_cert_" #_index "_end:\n\t"			\
+		  ".equ stored_cert_" #_index "_len, "			\
+			"( stored_cert_" #_index "_end - "		\
+			"  stored_cert_" #_index "_data )\n\t"		\
+		  ".previous\n\t" );
+CERT_ALL
+
+/** Raw certificate cursors for all permanent stored certificates */
+#undef CERT
+#define CERT( _index, _path ) {						\
+	.data = stored_cert_ ## _index ## _data,			\
+	.len = ( size_t ) stored_cert_ ## _index ## _len, 		\
+},
+static struct asn1_cursor certstore_raw[] = {
+	CERT_ALL
+};
+
+/** X.509 certificate structures for all permanent stored certificates */
+static struct x509_certificate certstore_certs[ sizeof ( certstore_raw ) /
+						sizeof ( certstore_raw[0] ) ];
+
+/** Certificate store */
+struct x509_chain certstore = {
+	.refcnt = REF_INIT ( ref_no_free ),
+	.links = LIST_HEAD_INIT ( certstore.links ),
+};
+
+/**
+ * Mark stored certificate as most recently used
+ *
+ * @v cert		X.509 certificate
+ * @ret cert		X.509 certificate
+ */
+static struct x509_certificate *
+certstore_found ( struct x509_certificate *cert ) {
+
+	/* Mark as most recently used */
+	list_del ( &cert->store.list );
+	list_add ( &cert->store.list, &certstore.links );
+	DBGC2 ( &certstore, "CERTSTORE found certificate %s\n",
+		x509_name ( cert ) );
+
+	return cert;
+}
+
+/**
+ * Find certificate in store
+ *
+ * @v raw		Raw certificate data
+ * @ret cert		X.509 certificate, or NULL if not found
+ */
+struct x509_certificate * certstore_find ( struct asn1_cursor *raw ) {
+	struct x509_certificate *cert;
+
+	/* Search for certificate within store */
+	list_for_each_entry ( cert, &certstore.links, store.list ) {
+		if ( asn1_compare ( raw, &cert->raw ) == 0 )
+			return certstore_found ( cert );
+	}
+	return NULL;
+}
+
+/**
+ * Find certificate in store corresponding to a private key
+ *
+ * @v key		Private key
+ * @ret cert		X.509 certificate, or NULL if not found
+ */
+struct x509_certificate * certstore_find_key ( struct asn1_cursor *key ) {
+	struct x509_certificate *cert;
+
+	/* Search for certificate within store */
+	list_for_each_entry ( cert, &certstore.links, store.list ) {
+		if ( pubkey_match ( cert->signature_algorithm->pubkey,
+				    key->data, key->len,
+				    cert->subject.public_key.raw.data,
+				    cert->subject.public_key.raw.len ) == 0 )
+			return certstore_found ( cert );
+	}
+	return NULL;
+}
+
+/**
+ * Add certificate to store
+ *
+ * @v cert		X.509 certificate
+ */
+void certstore_add ( struct x509_certificate *cert ) {
+
+	/* Add certificate to store */
+	cert->store.cert = cert;
+	x509_get ( cert );
+	list_add ( &cert->store.list, &certstore.links );
+	DBGC ( &certstore, "CERTSTORE added certificate %s\n",
+	       x509_name ( cert ) );
+}
+
+/**
+ * Discard a stored certificate
+ *
+ * @ret discarded	Number of cached items discarded
+ */
+static unsigned int certstore_discard ( void ) {
+	struct x509_certificate *cert;
+
+	/* Discard the least recently used certificate for which the
+	 * only reference is held by the store itself.
+	 */
+	list_for_each_entry_reverse ( cert, &certstore.links, store.list ) {
+		if ( cert->refcnt.count == 0 ) {
+			DBGC ( &certstore, "CERTSTORE discarded certificate "
+			       "%s\n", x509_name ( cert ) );
+			list_del ( &cert->store.list );
+			x509_put ( cert );
+			return 1;
+		}
+	}
+	return 0;
+}
+
+/** Certificate store cache discarder */
+struct cache_discarder certstore_discarder __cache_discarder ( CACHE_NORMAL ) ={
+	.discard = certstore_discard,
+};
+
+/**
+ * Construct permanent certificate store
+ *
+ */
+static void certstore_init ( void ) {
+	struct asn1_cursor *raw;
+	struct x509_certificate *cert;
+	int i;
+	int rc;
+
+	/* Skip if we have no permanent stored certificates */
+	if ( ! sizeof ( certstore_raw ) )
+		return;
+
+	/* Add certificates */
+	for ( i = 0 ; i < ( int ) ( sizeof ( certstore_raw ) /
+				    sizeof ( certstore_raw[0] ) ) ; i++ ) {
+
+		/* Skip if certificate already present in store */
+		raw = &certstore_raw[i];
+		if ( ( cert = certstore_find ( raw ) ) != NULL ) {
+			DBGC ( &certstore, "CERTSTORE permanent certificate %d "
+			       "is a duplicate of %s\n", i, x509_name ( cert ));
+			continue;
+		}
+
+		/* Parse certificate */
+		cert = &certstore_certs[i];
+		ref_init ( &cert->refcnt, ref_no_free );
+		if ( ( rc = x509_parse ( cert, raw ) ) != 0 ) {
+			DBGC ( &certstore, "CERTSTORE could not parse "
+			       "permanent certificate %d: %s\n",
+			       i, strerror ( rc ) );
+			continue;
+		}
+
+		/* Add certificate to store.  Certificate will never
+		 * be discarded from the store, since we retain a
+		 * permanent reference to it.
+		 */
+		certstore_add ( cert );
+		DBGC ( &certstore, "CERTSTORE permanent certificate %d is %s\n",
+		       i, x509_name ( cert ) );
+	}
+}
+
+/** Certificate store initialisation function */
+struct init_fn certstore_init_fn __init_fn ( INIT_LATE ) = {
+	.initialise = certstore_init,
+};
+
+/** Additional certificate setting */
+static struct setting cert_setting __setting ( SETTING_CRYPTO, cert ) = {
+	.name = "cert",
+	.description = "Certificate",
+	.tag = DHCP_EB_CERT,
+	.type = &setting_type_hex,
+};
+
+/**
+ * Apply certificate store configuration settings
+ *
+ * @ret rc		Return status code
+ */
+static int certstore_apply_settings ( void ) {
+	static struct x509_certificate *cert = NULL;
+	struct x509_certificate *old_cert;
+	void *cert_data;
+	int len;
+	int rc;
+
+	/* Record any existing additional certificate */
+	old_cert = cert;
+	cert = NULL;
+
+	/* Add additional certificate, if any */
+	if ( ( len = fetch_raw_setting_copy ( NULL, &cert_setting,
+					      &cert_data ) ) >= 0 ) {
+		if ( ( rc = x509_certificate ( cert_data, len, &cert ) ) == 0 ){
+			DBGC ( &certstore, "CERTSTORE added additional "
+			       "certificate %s\n", x509_name ( cert ) );
+		} else {
+			DBGC ( &certstore, "CERTSTORE could not parse "
+			       "additional certificate: %s\n",
+			       strerror ( rc ) );
+			/* Do not fail; leave as an unusable certificate */
+		}
+		free ( cert_data );
+	}
+
+	/* Free old additional certificiate.  Do this after reparsing
+	 * the additional certificate; in the common case that the
+	 * certificate has not changed, this will allow the stored
+	 * certificate to be reused.
+	 */
+	x509_put ( old_cert );
+
+	return 0;
+}
+
+/** Certificate store settings applicator */
+struct settings_applicator certstore_applicator __settings_applicator = {
+	.apply = certstore_apply_settings,
+};
diff --git a/src/crypto/clientcert.c b/src/crypto/clientcert.c
deleted file mode 100644
index 3a662865..00000000
--- a/src/crypto/clientcert.c
+++ /dev/null
@@ -1,170 +0,0 @@
-/*
- * Copyright (C) 2012 Michael Brown <mbrown@fensystems.co.uk>.
- *
- * This program is free software; you can redistribute it and/or
- * modify it under the terms of the GNU General Public License as
- * published by the Free Software Foundation; either version 2 of the
- * License, or any later version.
- *
- * This program is distributed in the hope that it will be useful, but
- * WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
- * General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with this program; if not, write to the Free Software
- * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
- * 02110-1301, USA.
- */
-
-FILE_LICENCE ( GPL2_OR_LATER );
-
-#include <stdint.h>
-#include <stdlib.h>
-#include <string.h>
-#include <ipxe/dhcp.h>
-#include <ipxe/settings.h>
-#include <ipxe/clientcert.h>
-
-/** @file
- *
- * Client certificate store
- *
- * Life would in theory be easier if we could use a single file to
- * hold both the certificate and corresponding private key.
- * Unfortunately, the only common format which supports this is
- * PKCS#12 (aka PFX), which is too ugly to be allowed anywhere near my
- * codebase.  See, for reference and amusement:
- *
- *    http://www.cs.auckland.ac.nz/~pgut001/pubs/pfx.html
- *
- */
-
-/* Sanity checks */
-#if defined(CERTIFICATE) && ! defined(PRIVATE_KEY)
-#warning "Attempting to embed certificate with no corresponding private key"
-#endif
-#if defined(PRIVATE_KEY) && ! defined(CERTIFICATE)
-#warning "Attempting to embed private key with no corresponding certificate"
-#endif
-
-/* Allow client certificates to be overridden if not explicitly specified */
-#ifdef CERTIFICATE
-#define ALLOW_CERT_OVERRIDE 0
-#else
-#define ALLOW_CERT_OVERRIDE 1
-#endif
-
-/* Raw client certificate data */
-extern char client_certificate_data[];
-extern char client_certificate_len[];
-__asm__ ( ".section \".rodata\", \"a\", @progbits\n\t"
-	  "\nclient_certificate_data:\n\t"
-#ifdef CERTIFICATE
-	  ".incbin \"" CERTIFICATE "\"\n\t"
-#endif /* CERTIFICATE */
-	  ".size client_certificate_data, ( . - client_certificate_data )\n\t"
-	  ".equ client_certificate_len, ( . - client_certificate_data )\n\t"
-	  ".previous\n\t" );
-
-/* Raw client private key data */
-extern char client_private_key_data[];
-extern char client_private_key_len[];
-__asm__ ( ".section \".rodata\", \"a\", @progbits\n\t"
-	  "\nclient_private_key_data:\n\t"
-#ifdef PRIVATE_KEY
-	  ".incbin \"" PRIVATE_KEY "\"\n\t"
-#endif /* PRIVATE_KEY */
-	  ".size client_private_key_data, ( . - client_private_key_data )\n\t"
-	  ".equ client_private_key_len, ( . - client_private_key_data )\n\t"
-	  ".previous\n\t" );
-
-/** Client certificate */
-struct client_certificate client_certificate = {
-	.data = client_certificate_data,
-	.len = ( ( size_t ) client_certificate_len ),
-};
-
-/** Client private key */
-struct client_private_key client_private_key = {
-	.data = client_private_key_data,
-	.len = ( ( size_t ) client_private_key_len ),
-};
-
-/** Client certificate setting */
-static struct setting cert_setting __setting ( SETTING_CRYPTO, cert ) = {
-	.name = "cert",
-	.description = "Client certificate",
-	.tag = DHCP_EB_CERT,
-	.type = &setting_type_hex,
-};
-
-/** Client private key setting */
-static struct setting privkey_setting __setting ( SETTING_CRYPTO, privkey ) = {
-	.name = "privkey",
-	.description = "Client private key",
-	.tag = DHCP_EB_KEY,
-	.type = &setting_type_hex,
-};
-
-/**
- * Apply client certificate store configuration settings
- *
- * @ret rc		Return status code
- */
-static int clientcert_apply_settings ( void ) {
-	static void *cert = NULL;
-	static void *key = NULL;
-	int len;
-
-	/* Allow client certificate to be overridden only if
-	 * not explicitly specified at build time.
-	 */
-	if ( ALLOW_CERT_OVERRIDE ) {
-
-		/* Restore default client certificate */
-		client_certificate.data = client_certificate_data;
-		client_certificate.len = ( ( size_t ) client_certificate_len );
-
-		/* Fetch new client certificate, if any */
-		free ( cert );
-		if ( ( len = fetch_raw_setting_copy ( NULL, &cert_setting,
-						      &cert ) ) >= 0 ) {
-			client_certificate.data = cert;
-			client_certificate.len = len;
-		}
-
-		/* Restore default client private key */
-		client_private_key.data = client_private_key_data;
-		client_private_key.len = ( ( size_t ) client_private_key_len );
-
-		/* Fetch new client private key, if any */
-		free ( key );
-		if ( ( len = fetch_raw_setting_copy ( NULL, &privkey_setting,
-						      &key ) ) >= 0 ) {
-			client_private_key.data = key;
-			client_private_key.len = len;
-		}
-	}
-
-	/* Debug */
-	if ( have_client_certificate() ) {
-		DBGC ( &client_certificate, "CLIENTCERT using %s "
-		       "certificate:\n", ( cert ? "external" : "built-in" ) );
-		DBGC_HDA ( &client_certificate, 0, client_certificate.data,
-			   client_certificate.len );
-		DBGC ( &client_certificate, "CLIENTCERT using %s private "
-		       "key:\n", ( key ? "external" : "built-in" ) );
-		DBGC_HDA ( &client_certificate, 0, client_private_key.data,
-			   client_private_key.len );
-	} else {
-		DBGC ( &client_certificate, "CLIENTCERT has no certificate\n" );
-	}
-
-	return 0;
-}
-
-/** Client certificate store settings applicator */
-struct settings_applicator clientcert_applicator __settings_applicator = {
-	.apply = clientcert_apply_settings,
-};
diff --git a/src/crypto/cms.c b/src/crypto/cms.c
index 6191d1bb..b4a41de6 100644
--- a/src/crypto/cms.c
+++ b/src/crypto/cms.c
@@ -617,18 +617,21 @@ static int cms_verify_digest ( struct cms_signature *sig,
  * @v data		Signed data
  * @v len		Length of signed data
  * @v time		Time at which to validate certificates
- * @v root		Root certificate store, or NULL to use default
+ * @v store		Certificate store, or NULL to use default
+ * @v root		Root certificate list, or NULL to use default
  * @ret rc		Return status code
  */
 static int cms_verify_signer_info ( struct cms_signature *sig,
 				    struct cms_signer_info *info,
 				    userptr_t data, size_t len,
-				    time_t time, struct x509_root *root ) {
+				    time_t time, struct x509_chain *store,
+				    struct x509_root *root ) {
 	struct x509_certificate *cert;
 	int rc;
 
 	/* Validate certificate chain */
-	if ( ( rc = x509_validate_chain ( info->chain, time, root ) ) != 0 ) {
+	if ( ( rc = x509_validate_chain ( info->chain, time, store,
+					  root ) ) != 0 ) {
 		DBGC ( sig, "CMS %p/%p could not validate chain: %s\n",
 		       sig, info, strerror ( rc ) );
 		return rc;
@@ -667,11 +670,13 @@ static int cms_verify_signer_info ( struct cms_signature *sig,
  * @v len		Length of signed data
  * @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
+ * @v store		Certificate store, or NULL to use default
+ * @v root		Root certificate list, 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 ) {
+		 const char *name, time_t time, struct x509_chain *store,
+		 struct x509_root *root ) {
 	struct cms_signer_info *info;
 	struct x509_certificate *cert;
 	int count = 0;
@@ -682,8 +687,8 @@ int cms_verify ( struct cms_signature *sig, userptr_t data, size_t len,
 		cert = x509_first ( info->chain );
 		if ( name && ( x509_check_name ( cert, name ) != 0 ) )
 			continue;
-		if ( ( rc = cms_verify_signer_info ( sig, info, data, len,
-						     time, root ) ) != 0 )
+		if ( ( rc = cms_verify_signer_info ( sig, info, data, len, time,
+						     store, root ) ) != 0 )
 			return rc;
 		count++;
 	}
diff --git a/src/crypto/privkey.c b/src/crypto/privkey.c
new file mode 100644
index 00000000..e010649c
--- /dev/null
+++ b/src/crypto/privkey.c
@@ -0,0 +1,118 @@
+/*
+ * Copyright (C) 2012 Michael Brown <mbrown@fensystems.co.uk>.
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License as
+ * published by the Free Software Foundation; either version 2 of the
+ * License, or any later version.
+ *
+ * This program is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
+ * 02110-1301, USA.
+ */
+
+FILE_LICENCE ( GPL2_OR_LATER );
+
+#include <stdint.h>
+#include <stdlib.h>
+#include <string.h>
+#include <ipxe/dhcp.h>
+#include <ipxe/settings.h>
+#include <ipxe/x509.h>
+#include <ipxe/privkey.h>
+
+/** @file
+ *
+ * Private key
+ *
+ * Life would in theory be easier if we could use a single file to
+ * hold both the certificate and corresponding private key.
+ * Unfortunately, the only common format which supports this is
+ * PKCS#12 (aka PFX), which is too ugly to be allowed anywhere near my
+ * codebase.  See, for reference and amusement:
+ *
+ *    http://www.cs.auckland.ac.nz/~pgut001/pubs/pfx.html
+ */
+
+/* Allow private key to be overridden if not explicitly specified */
+#ifdef PRIVATE_KEY
+#define ALLOW_KEY_OVERRIDE 0
+#else
+#define ALLOW_KEY_OVERRIDE 1
+#endif
+
+/* Raw private key data */
+extern char private_key_data[];
+extern char private_key_len[];
+__asm__ ( ".section \".rodata\", \"a\", @progbits\n\t"
+	  "\nprivate_key_data:\n\t"
+#ifdef PRIVATE_KEY
+	  ".incbin \"" PRIVATE_KEY "\"\n\t"
+#endif /* PRIVATE_KEY */
+	  ".size private_key_data, ( . - private_key_data )\n\t"
+	  ".equ private_key_len, ( . - private_key_data )\n\t"
+	  ".previous\n\t" );
+
+/** Private key */
+struct asn1_cursor private_key = {
+	.data = private_key_data,
+	.len = ( ( size_t ) private_key_len ),
+};
+
+/** Private key setting */
+static struct setting privkey_setting __setting ( SETTING_CRYPTO, privkey ) = {
+	.name = "privkey",
+	.description = "Private key",
+	.tag = DHCP_EB_KEY,
+	.type = &setting_type_hex,
+};
+
+/**
+ * Apply private key configuration settings
+ *
+ * @ret rc		Return status code
+ */
+static int privkey_apply_settings ( void ) {
+	static void *key_data = NULL;
+	int len;
+
+	/* Allow private key to be overridden only if not explicitly
+	 * specified at build time.
+	 */
+	if ( ALLOW_KEY_OVERRIDE ) {
+
+		/* Restore default private key */
+		private_key.data = private_key_data;
+		private_key.len = ( ( size_t ) private_key_len );
+
+		/* Fetch new private key, if any */
+		free ( key_data );
+		if ( ( len = fetch_raw_setting_copy ( NULL, &privkey_setting,
+						      &key_data ) ) >= 0 ) {
+			private_key.data = key_data;
+			private_key.len = len;
+		}
+	}
+
+	/* Debug */
+	if ( private_key.len ) {
+		DBGC ( &private_key, "PRIVKEY using %s private key:\n",
+		       ( key_data ? "external" : "built-in" ) );
+		DBGC_HDA ( &private_key, 0, private_key.data, private_key.len );
+	} else {
+		DBGC ( &private_key, "PRIVKEY has no private key\n" );
+	}
+
+	return 0;
+}
+
+/** Private key settings applicator */
+struct settings_applicator privkey_applicator __settings_applicator = {
+	.apply = privkey_apply_settings,
+};
diff --git a/src/crypto/x509.c b/src/crypto/x509.c
index 29bb2296..38acb2ac 100644
--- a/src/crypto/x509.c
+++ b/src/crypto/x509.c
@@ -24,7 +24,6 @@ FILE_LICENCE ( GPL2_OR_LATER );
 #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>
@@ -32,6 +31,7 @@ FILE_LICENCE ( GPL2_OR_LATER );
 #include <ipxe/sha256.h>
 #include <ipxe/rsa.h>
 #include <ipxe/rootcert.h>
+#include <ipxe/certstore.h>
 #include <ipxe/x509.h>
 
 /** @file
@@ -107,9 +107,10 @@ FILE_LICENCE ( GPL2_OR_LATER );
 	__einfo_error ( EINFO_EACCES_WRONG_NAME )
 #define EINFO_EACCES_WRONG_NAME \
 	__einfo_uniqify ( EINFO_EACCES, 0x0a, "Incorrect certificate name" )
-
-/** Certificate cache */
-static LIST_HEAD ( x509_cache );
+#define EACCES_USELESS \
+	__einfo_error ( EINFO_EACCES_USELESS )
+#define EINFO_EACCES_USELESS \
+	__einfo_uniqify ( EINFO_EACCES, 0x0b, "No usable certificates" )
 
 /**
  * Get X.509 certificate name (for debugging)
@@ -130,32 +131,6 @@ const char * x509_name ( struct x509_certificate *cert ) {
 	return buf;
 }
 
-/**
- * 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_discarder __cache_discarder ( CACHE_NORMAL ) = {
-	.discard = x509_discard,
-};
-
 /** "commonName" object identifier */
 static uint8_t oid_common_name[] = { ASN1_OID_COMMON_NAME };
 
@@ -955,8 +930,8 @@ static int x509_parse_tbscertificate ( struct x509_certificate *cert,
  * @v raw		ASN.1 cursor
  * @ret rc		Return status code
  */
-static int x509_parse ( struct x509_certificate *cert,
-			const struct asn1_cursor *raw ) {
+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 asn1_bit_string *signature_value = &signature->value;
@@ -1032,22 +1007,12 @@ int x509_certificate ( const void *data, size_t len,
 	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 ) {
-
-			DBGC2 ( *cert, "X509 %p \"%s\" cache hit\n",
-				*cert, x509_name ( *cert ) );
+	/* Return stored certificate, if present */
+	if ( ( *cert = certstore_find ( &cursor ) ) != NULL ) {
 
-			/* Mark as most recently used */
-			list_del ( &(*cert)->list );
-			list_add ( &(*cert)->list, &x509_cache );
-
-			/* Add caller's reference */
-			x509_get ( *cert );
-
-			return 0;
-		}
+		/* Add caller's reference */
+		x509_get ( *cert );
+		return 0;
 	}
 
 	/* Allocate and initialise certificate */
@@ -1055,7 +1020,6 @@ int x509_certificate ( const void *data, size_t len,
 	if ( ! *cert )
 		return -ENOMEM;
 	ref_init ( &(*cert)->refcnt, NULL );
-	INIT_LIST_HEAD ( &(*cert)->list );
 	raw = ( *cert + 1 );
 
 	/* Copy raw data */
@@ -1069,9 +1033,8 @@ int x509_certificate ( const void *data, size_t len,
 		return rc;
 	}
 
-	/* Add certificate to cache */
-	x509_get ( *cert );
-	list_add ( &(*cert)->list, &x509_cache );
+	/* Add certificate to store */
+	certstore_add ( *cert );
 
 	return 0;
 }
@@ -1221,7 +1184,7 @@ void x509_fingerprint ( struct x509_certificate *cert,
  * Check X.509 root certificate
  *
  * @v cert		X.509 certificate
- * @v root		X.509 root certificate store
+ * @v root		X.509 root certificate list
  * @ret rc		Return status code
  */
 int x509_check_root ( struct x509_certificate *cert, struct x509_root *root ) {
@@ -1282,7 +1245,7 @@ int x509_check_time ( struct x509_certificate *cert, time_t time ) {
  * @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 root		Root certificate list, or NULL to use default
  * @ret rc		Return status code
  *
  * The issuing certificate must have already been validated.
@@ -1533,7 +1496,7 @@ int x509_auto_append ( struct x509_chain *chain, struct x509_chain *certs ) {
 	cert = x509_last ( chain );
 	if ( ! cert ) {
 		DBGC ( chain, "X509 chain %p has no certificates\n", chain );
-		return -EINVAL;
+		return -EACCES_EMPTY;
 	}
 
 	/* Append certificates, in order */
@@ -1560,17 +1523,23 @@ int x509_auto_append ( struct x509_chain *chain, struct x509_chain *certs ) {
  *
  * @v chain		X.509 certificate chain
  * @v time		Time at which to validate certificates
- * @v root		Root certificate store, or NULL to use default
+ * @v store		Certificate store, or NULL to use default
+ * @v root		Root certificate list, 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_chain *store, struct x509_root *root ) {
 	struct x509_certificate *issuer = NULL;
 	struct x509_link *link;
 	int rc;
 
-	/* Error to be used if chain contains no certifictes */
-	rc = -EACCES_EMPTY;
+	/* Use default certificate store if none specified */
+	if ( ! store )
+		store = &certstore;
+
+	/* Append any applicable certificates from the certificate store */
+	if ( ( rc = x509_auto_append ( chain, store ) ) != 0 )
+		return rc;
 
 	/* Find first certificate that can be validated as a
 	 * standalone (i.e.  is already valid, or can be validated as
@@ -1600,7 +1569,9 @@ int x509_validate_chain ( struct x509_chain *chain, time_t time,
 		return 0;
 	}
 
-	DBGC ( chain, "X509 chain %p found no valid certificates: %s\n",
-	       chain, strerror ( rc ) );
-	return rc;
+	DBGC ( chain, "X509 chain %p found no usable certificates\n", chain );
+	return -EACCES_USELESS;
 }
+
+/* Drag in certificate store */
+REQUIRE_OBJECT ( certstore );