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

18 files changed, 640 insertions, 398 deletions

diff --git a/src/Makefile b/src/Makefile
index 66f287d4..ea987b84 100644
--- a/src/Makefile
+++ b/src/Makefile
@@ -34,6 +34,7 @@ OBJCOPY		:= $(CROSS_COMPILE)objcopy
 NM		:= $(CROSS_COMPILE)nm
 OBJDUMP		:= $(CROSS_COMPILE)objdump
 OPENSSL		:= openssl
+CSPLIT		:= csplit
 PARSEROM	:= ./util/parserom.pl
 FIXROM		:= ./util/fixrom.pl
 SYMCHECK	:= ./util/symcheck.pl
diff --git a/src/Makefile.housekeeping b/src/Makefile.housekeeping
index 22cde15e..c0c1c910 100644
--- a/src/Makefile.housekeeping
+++ b/src/Makefile.housekeeping
@@ -601,7 +601,7 @@ rootcert_DEPS += $(TRUSTED_FILES) $(TRUSTED_LIST)
 
 CFLAGS_rootcert = $(if $(TRUSTED_FPS),-DTRUSTED="$(TRUSTED_FPS)")
 
-# (Single-element) list of client certificates
+# List of embedded certificates
 #
 CERT_LIST := $(BIN)/.certificate.list
 ifeq ($(wildcard $(CERT_LIST)),)
@@ -617,24 +617,43 @@ $(CERT_LIST) : $(MAKEDEPS)
 
 VERYCLEANUP += $(CERT_LIST)
 
-# Embedded client certificate
+# Embedded certificates concatenated and then split into one file per
+# certificate (even if original files contained certificate chains)
 #
-CERT_INC := $(BIN)/.certificate.der
+CERT_FILES := $(subst $(COMMA), ,$(CERT))
+CERT_CONCAT := $(BIN)/.certificates.pem
 
-ifdef CERT
-$(CERT_INC) : $(CERT) $(CERT_LIST)
+ifneq ($(CERT),)
+
+CERT_COUNT := $(shell grep "BEGIN CERTIFICATE" $(CERT_FILES) | wc -l)
+
+$(CERT_CONCAT) : $(CERT_FILES) $(CERT_LIST)
+	$(Q)cat $(CERT_FILES) > $@
+
+# We must use an (otherwise unnecessary) pattern rule here to encode
+# the fact that one "csplit" command generates multiple targets
+CERT_PEMS := $(foreach i,$(call seq,1,$(CERT_COUNT)),\
+	       $(BIN)/.certificate.pem.$(i))
+$(subst .pem.,.%.,$(CERT_PEMS)) : $(BIN)/.certificates.%
+	$(Q)$(CSPLIT) -q -n 1 -f $(BIN)/.certificate.pem. $< \
+		'/BEGIN CERTIFICATE/' '{*}'
+
+CERT_DERS := $(subst .certificate.pem.,.certificate.der.,$(CERT_PEMS))
+$(BIN)/.certificate.der.% : $(BIN)/.certificate.pem.%
 	$(Q)$(OPENSSL) x509 -in $< -outform DER -out $@
 
-clientcert_DEPS += $(CERT_INC)
+CERT_ALL := $(foreach i,$(call seq,1,$(CERT_COUNT)),\
+	      CERT ( $(i), \"$(word $(i),$(CERT_DERS))\" ))
+
 endif
 
-CLEANUP += $(CERT_INC)
+certstore_DEPS += $(CERT_LIST) $(CERT_FILES) $(CERT_PEMS) $(CERT_DERS)
 
-clientcert_DEPS += $(CERT_LIST)
+CFLAGS_certstore += -DCERT_ALL="$(CERT_ALL)"
 
-CFLAGS_clientcert += $(if $(CERT),-DCERTIFICATE="\"$(CERT_INC)\"")
+CLEANUP += $(BIN)/.certificate.* $(BIN)/.certificates.*
 
-# (Single-element) list of client private keys
+# (Single-element) list of private keys
 #
 ifdef KEY
 PRIVKEY	:= $(KEY) # Maintain backwards compatibility
@@ -653,7 +672,7 @@ $(PRIVKEY_LIST) : $(MAKEDEPS)
 
 VERYCLEANUP += $(PRIVKEY_LIST)
 
-# Embedded client private key
+# Embedded private key
 #
 PRIVKEY_INC := $(BIN)/.private_key.der
 
@@ -661,21 +680,22 @@ ifdef PRIVKEY
 $(PRIVKEY_INC) : $(PRIVKEY) $(PRIVKEY_LIST)
 	$(Q)$(OPENSSL) rsa -in $< -outform DER -out $@
 
-clientcert_DEPS += $(PRIVKEY_INC)
+privkey_DEPS += $(PRIVKEY_INC)
 endif
 
-CLEANUP += $(PRIVKEY_INC)
+CLEANUP += $(BIN)/.private_key.*
 
-clientcert_DEPS += $(PRIVKEY_LIST)
+privkey_DEPS += $(PRIVKEY_LIST)
 
-CFLAGS_clientcert += $(if $(PRIVKEY),-DPRIVATE_KEY="\"$(PRIVKEY_INC)\"")
+CFLAGS_privkey += $(if $(PRIVKEY),-DPRIVATE_KEY="\"$(PRIVKEY_INC)\"")
 
 # These files use .incbin inline assembly to include a binary file.
 # Unfortunately ccache does not detect this dependency and caches
 # builds even when the binary file has changed.
 #
 $(BIN)/embedded.% : override CC := env CCACHE_DISABLE=1 $(CC)
-$(BIN)/clientcert.% : override CC := env CCACHE_DISABLE=1 $(CC)
+$(BIN)/certstore.% : override CC := env CCACHE_DISABLE=1 $(CC)
+$(BIN)/privkey.% : override CC := env CCACHE_DISABLE=1 $(CC)
 
 # Version number
 #
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 );
diff --git a/src/include/ipxe/certstore.h b/src/include/ipxe/certstore.h
new file mode 100644
index 00000000..7456db62
--- /dev/null
+++ b/src/include/ipxe/certstore.h
@@ -0,0 +1,21 @@
+#ifndef _IPXE_CERTSTORE_H
+#define _IPXE_CERTSTORE_H
+
+/** @file
+ *
+ * Certificate store
+ *
+ */
+
+FILE_LICENCE ( GPL2_OR_LATER );
+
+#include <ipxe/asn1.h>
+#include <ipxe/x509.h>
+
+extern struct x509_chain certstore;
+
+extern struct x509_certificate * certstore_find ( struct asn1_cursor *raw );
+extern struct x509_certificate * certstore_find_key ( struct asn1_cursor *key );
+extern void certstore_add ( struct x509_certificate *cert );
+
+#endif /* _IPXE_CERTSTORE_H */
diff --git a/src/include/ipxe/clientcert.h b/src/include/ipxe/clientcert.h
deleted file mode 100644
index 08f62eb7..00000000
--- a/src/include/ipxe/clientcert.h
+++ /dev/null
@@ -1,43 +0,0 @@
-#ifndef _IPXE_CLIENTCERT_H
-#define _IPXE_CLIENTCERT_H
-
-/** @file
- *
- * Client certificate store
- *
- */
-
-FILE_LICENCE ( GPL2_OR_LATER );
-
-#include <stdint.h>
-
-/** A client certificate */
-struct client_certificate {
-	/** Data */
-	const void *data;
-	/** Length */
-	size_t len;
-};
-
-/** A client private key */
-struct client_private_key {
-	/** Data */
-	const void *data;
-	/** Length */
-	size_t len;
-};
-
-extern struct client_certificate client_certificate;
-extern struct client_private_key client_private_key;
-
-/**
- * Check for presence of a client certificate
- *
- * @ret have_cert	We have a client certificate and private key
- */
-static inline int have_client_certificate ( void ) {
-	return ( ( client_certificate.len > 0 ) &&
-		 ( client_private_key.len > 0 ) );
-}
-
-#endif /* _IPXE_CLIENTCERT_H */
diff --git a/src/include/ipxe/cms.h b/src/include/ipxe/cms.h
index eadeca4b..e026ebd2 100644
--- a/src/include/ipxe/cms.h
+++ b/src/include/ipxe/cms.h
@@ -70,6 +70,7 @@ cms_put ( struct cms_signature *sig ) {
 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 );
+			const char *name, time_t time, struct x509_chain *store,
+			struct x509_root *root );
 
 #endif /* _IPXE_CMS_H */
diff --git a/src/include/ipxe/privkey.h b/src/include/ipxe/privkey.h
new file mode 100644
index 00000000..39049ac9
--- /dev/null
+++ b/src/include/ipxe/privkey.h
@@ -0,0 +1,16 @@
+#ifndef _IPXE_PRIVKEY_H
+#define _IPXE_PRIVKEY_H
+
+/** @file
+ *
+ * Private key
+ *
+ */
+
+FILE_LICENCE ( GPL2_OR_LATER );
+
+#include <ipxe/asn1.h>
+
+extern struct asn1_cursor private_key;
+
+#endif /* _IPXE_PRIVKEY_H */
diff --git a/src/include/ipxe/tls.h b/src/include/ipxe/tls.h
index f8a75409..586da26e 100644
--- a/src/include/ipxe/tls.h
+++ b/src/include/ipxe/tls.h
@@ -241,8 +241,8 @@ struct tls_session {
 	struct digest_algorithm *handshake_digest;
 	/** Digest algorithm context used for handshake verification */
 	uint8_t *handshake_ctx;
-	/** Public-key algorithm used for Certificate Verify (if sent) */
-	struct pubkey_algorithm *verify_pubkey;
+	/** Client certificate (if used) */
+	struct x509_certificate *cert;
 
 	/** Server certificate chain */
 	struct x509_chain *chain;
diff --git a/src/include/ipxe/x509.h b/src/include/ipxe/x509.h
index 483153bb..52302aea 100644
--- a/src/include/ipxe/x509.h
+++ b/src/include/ipxe/x509.h
@@ -156,12 +156,29 @@ struct x509_extensions {
 	struct x509_authority_info_access auth_info;
 };
 
+/** 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;
+};
+
 /** An X.509 certificate */
 struct x509_certificate {
 	/** Reference count */
 	struct refcnt refcnt;
-	/** List of certificates in cache */
-	struct list_head list;
+
+	/** Link in certificate store */
+	struct x509_link store;
 
 	/** Certificate has been validated */
 	int valid;
@@ -212,22 +229,6 @@ 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
  *
@@ -331,7 +332,8 @@ struct x509_root {
 };
 
 extern const char * x509_name ( struct x509_certificate *cert );
-
+extern int x509_parse ( struct x509_certificate *cert,
+			const struct asn1_cursor *raw );
 extern int x509_certificate ( const void *data, size_t len,
 			      struct x509_certificate **cert );
 extern int x509_validate ( struct x509_certificate *cert,
@@ -347,6 +349,7 @@ extern int x509_append_raw ( struct x509_chain *chain, const void *data,
 extern int x509_auto_append ( struct x509_chain *chain,
 			      struct x509_chain *certs );
 extern int x509_validate_chain ( struct x509_chain *chain, time_t time,
+				 struct x509_chain *store,
 				 struct x509_root *root );
 
 /* Functions exposed only for unit testing */
diff --git a/src/net/tls.c b/src/net/tls.c
index 742a7c0b..30ccc932 100644
--- a/src/net/tls.c
+++ b/src/net/tls.c
@@ -43,7 +43,8 @@ FILE_LICENCE ( GPL2_OR_LATER );
 #include <ipxe/xfer.h>
 #include <ipxe/open.h>
 #include <ipxe/x509.h>
-#include <ipxe/clientcert.h>
+#include <ipxe/privkey.h>
+#include <ipxe/certstore.h>
 #include <ipxe/rbg.h>
 #include <ipxe/validator.h>
 #include <ipxe/tls.h>
@@ -157,6 +158,10 @@ FILE_LICENCE ( GPL2_OR_LATER );
 #define EINFO_EPERM_VERIFY						\
 	__einfo_uniqify ( EINFO_EPERM, 0x02,				\
 			  "Handshake verification failed" )
+#define EPERM_CLIENT_CERT __einfo_error ( EINFO_EPERM_CLIENT_CERT )
+#define EINFO_EPERM_CLIENT_CERT						\
+	__einfo_uniqify ( EINFO_EPERM, 0x03,				\
+			  "No suitable client certificate available" )
 #define EPROTO_VERSION __einfo_error ( EINFO_EPROTO_VERSION )
 #define EINFO_EPROTO_VERSION						\
 	__einfo_uniqify ( EINFO_EPROTO, 0x01,				\
@@ -307,6 +312,7 @@ static void free_tls ( struct refcnt *refcnt ) {
 		list_del ( &iobuf->list );
 		free_iob ( iobuf );
 	}
+	x509_put ( tls->cert );
 	x509_chain_put ( tls->chain );
 
 	/* Free TLS structure itself */
@@ -1030,41 +1036,16 @@ static int tls_send_client_hello ( struct tls_session *tls ) {
  * @ret rc		Return status code
  */
 static int tls_send_certificate ( struct tls_session *tls ) {
-	int num_certificates = ( have_client_certificate() ? 1 : 0 );
 	struct {
 		uint32_t type_length;
 		uint8_t length[3];
 		struct {
 			uint8_t length[3];
-			uint8_t data[ client_certificate.len ];
-		} __attribute__ (( packed )) certificates[num_certificates];
+			uint8_t data[ tls->cert->raw.len ];
+		} __attribute__ (( packed )) certificates[1];
 	} __attribute__ (( packed )) *certificate;
-	struct x509_certificate *cert;
 	int rc;
 
-	/* If we have a certificate to send, determine the applicable
-	 * public-key algorithm and schedule transmission of
-	 * CertificateVerify.
-	 */
-	if ( num_certificates ) {
-
-		/* Parse certificate to determine public-key algorithm */
-		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;
-		x509_put ( cert );
-		cert = NULL;
-
-		/* Schedule CertificateVerify transmission */
-		tls->tx_pending |= TLS_TX_CERTIFICATE_VERIFY;
-		tls_tx_resume ( tls );
-	}
-
 	/* Allocate storage for Certificate record (which may be too
 	 * large for the stack).
 	 */
@@ -1079,13 +1060,11 @@ static int tls_send_certificate ( struct tls_session *tls ) {
 			  sizeof ( certificate->type_length ) ) );
 	tls_set_uint24 ( certificate->length,
 			 sizeof ( certificate->certificates ) );
-	if ( num_certificates ) {
-		tls_set_uint24 ( certificate->certificates[0].length,
-				 sizeof ( certificate->certificates[0].data ) );
-		memcpy ( certificate->certificates[0].data,
-			 client_certificate.data,
+	tls_set_uint24 ( certificate->certificates[0].length,
 			 sizeof ( certificate->certificates[0].data ) );
-	}
+	memcpy ( certificate->certificates[0].data,
+		 tls->cert->raw.data,
+		 sizeof ( certificate->certificates[0].data ) );
 
 	/* Transmit record */
 	rc = tls_send_handshake ( tls, certificate, sizeof ( *certificate ) );
@@ -1148,7 +1127,8 @@ static int tls_send_client_key_exchange ( struct tls_session *tls ) {
  */
 static int tls_send_certificate_verify ( struct tls_session *tls ) {
 	struct digest_algorithm *digest = tls->handshake_digest;
-	struct pubkey_algorithm *pubkey = tls->verify_pubkey;
+	struct x509_certificate *cert = tls->cert;
+	struct pubkey_algorithm *pubkey = cert->signature_algorithm->pubkey;
 	uint8_t digest_out[ digest->digestsize ];
 	uint8_t ctx[ pubkey->ctxsize ];
 	struct tls_signature_hash_algorithm *sig_hash = NULL;
@@ -1158,8 +1138,8 @@ static int tls_send_certificate_verify ( struct tls_session *tls ) {
 	tls_verify_handshake ( tls, digest_out );
 
 	/* Initialise public-key algorithm */
-	if ( ( rc = pubkey_init ( pubkey, ctx, client_private_key.data,
-				  client_private_key.len ) ) != 0 ) {
+	if ( ( rc = pubkey_init ( pubkey, ctx, private_key.data,
+				  private_key.len ) ) != 0 ) {
 		DBGC ( tls, "TLS %p could not initialise %s client private "
 		       "key: %s\n", tls, pubkey->name, strerror ( rc ) );
 		goto err_pubkey_init;
@@ -1541,9 +1521,19 @@ static int tls_new_certificate_request ( struct tls_session *tls,
 	 * in parsing the Certificate Request.
 	 */
 
-	/* Schedule Certificate transmission */
-	tls->tx_pending |= TLS_TX_CERTIFICATE;
-	tls_tx_resume ( tls );
+	/* Free any existing client certificate */
+	x509_put ( tls->cert );
+
+	/* Determine client certificate to be sent */
+	tls->cert = certstore_find_key ( &private_key );
+	if ( ! tls->cert ) {
+		DBGC ( tls, "TLS %p could not find certificate corresponding "
+		       "to private key\n", tls );
+		return -EPERM_CLIENT_CERT;
+	}
+	x509_get ( tls->cert );
+	DBGC ( tls, "TLS %p sending client certificate %s\n",
+	       tls, x509_name ( tls->cert ) );
 
 	return 0;
 }
@@ -2469,6 +2459,10 @@ static void tls_validator_done ( struct tls_session *tls, int rc ) {
 	tls->tx_pending |= ( TLS_TX_CLIENT_KEY_EXCHANGE |
 			     TLS_TX_CHANGE_CIPHER |
 			     TLS_TX_FINISHED );
+	if ( tls->cert ) {
+		tls->tx_pending |= ( TLS_TX_CERTIFICATE |
+				     TLS_TX_CERTIFICATE_VERIFY );
+	}
 	tls_tx_resume ( tls );
 
 	return;
diff --git a/src/net/validator.c b/src/net/validator.c
index 60c54046..74d70e31 100644
--- a/src/net/validator.c
+++ b/src/net/validator.c
@@ -458,7 +458,7 @@ static void validator_step ( struct validator *validator ) {
 	 * previously.
 	 */
 	now = time ( NULL );
-	if ( ( rc = x509_validate_chain ( validator->chain, now,
+	if ( ( rc = x509_validate_chain ( validator->chain, now, NULL,
 					  NULL ) ) == 0 ) {
 		validator_finished ( validator, 0 );
 		return;
diff --git a/src/tests/cms_test.c b/src/tests/cms_test.c
index 9899b06a..b96decfc 100644
--- a/src/tests/cms_test.c
+++ b/src/tests/cms_test.c
@@ -1305,7 +1305,13 @@ static uint8_t root_crt_fingerprint[] =
 		      0x96, 0xe7, 0xa8, 0x6d, 0x63, 0x2d, 0x32, 0x38,
 		      0xaf, 0x00, 0xc4, 0x1a, 0xfc, 0xd8, 0xac, 0xc3 );
 
-/** Certificate store containing the iPXE self-test root CA */
+/** Empty certificate store */
+static struct x509_chain empty_store = {
+	.refcnt = REF_INIT ( ref_no_free ),
+	.links = LIST_HEAD_INIT ( empty_store.links ),
+};
+
+/** Root certificate list containing the iPXE self-test root CA */
 static struct x509_root test_root = {
 	.digest = &cms_test_algorithm,
 	.count = 1,
@@ -1349,12 +1355,13 @@ static time_t test_expired = 1375573111ULL; /* Sat Aug  3 23:38:31 2013 */
  * @v code		Test signed code
  * @v name		Test verification name
  * @v time		Test verification time
- * @v root		Test root certificate store
+ * @v store		Test certificate store
+ * @v root		Test root certificate list
  */
-#define cms_verify_ok( sgn, code, name, time, root ) do {		\
+#define cms_verify_ok( sgn, code, name, time, store, root ) do {	\
 	x509_invalidate_chain ( (sgn)->sig->certificates );		\
 	ok ( cms_verify ( (sgn)->sig, virt_to_user ( (code)->data ),	\
-			  (code)->len, name, time, root ) == 0 );	\
+			  (code)->len, name, time, store, root ) == 0 );\
 	} while ( 0 )
 
 /**
@@ -1364,12 +1371,13 @@ static time_t test_expired = 1375573111ULL; /* Sat Aug  3 23:38:31 2013 */
  * @v code		Test signed code
  * @v name		Test verification name
  * @v time		Test verification time
- * @v root		Test root certificate store
+ * @v store		Test certificate store
+ * @v root		Test root certificate list
  */
-#define cms_verify_fail_ok( sgn, code, name, time, root ) do {		\
+#define cms_verify_fail_ok( sgn, code, name, time, store, root ) do {	\
 	x509_invalidate_chain ( (sgn)->sig->certificates );		\
 	ok ( cms_verify ( (sgn)->sig, virt_to_user ( (code)->data ),	\
-			  (code)->len, name, time, root ) != 0 );	\
+			  (code)->len, name, time, store, root ) != 0 );\
 	} while ( 0 )
 
 /**
@@ -1385,38 +1393,42 @@ static void cms_test_exec ( void ) {
 	cms_signature_ok ( &nonsigned_sig );
 
 	/* Check good signature */
+	cms_verify_ok ( &codesigned_sig, &test_code, "codesign.test.ipxe.org",
+			test_time, &empty_store, &test_root );
 	cms_verify_ok ( &codesigned_sig, &test_code,
-			"codesign.test.ipxe.org", test_time, &test_root );
-	cms_verify_ok ( &codesigned_sig, &test_code,
-			NULL, test_time, &test_root );
+			NULL, test_time, &empty_store, &test_root );
 
 	/* Check incorrect signer name */
 	cms_verify_fail_ok ( &codesigned_sig, &test_code,
-			     "wrongname.test.ipxe.org", test_time, &test_root );
+			     "wrongname.test.ipxe.org", test_time,
+			     &empty_store, &test_root );
 
 	/* Check non-code-signing certificate */
 	cms_verify_fail_ok ( &genericsigned_sig, &test_code,
-			     NULL, test_time, &test_root );
+			     NULL, test_time, &empty_store, &test_root );
 
 	/* Check non-signing certificate */
 	cms_verify_fail_ok ( &nonsigned_sig, &test_code,
-			     NULL, test_time, &test_root );
+			     NULL, test_time, &empty_store, &test_root );
 
 	/* Check broken chain */
 	cms_verify_fail_ok ( &brokenchain_sig, &test_code,
-			     NULL, test_time, &test_root );
+			     NULL, test_time, &empty_store, &test_root );
 
 	/* Check untrusted signature */
 	cms_verify_fail_ok ( &codesigned_sig, &test_code,
-			     NULL, test_time, &dummy_root );
+			     NULL, test_time, &empty_store, &dummy_root );
 
 	/* Check incorrect signed content */
 	cms_verify_fail_ok ( &codesigned_sig, &bad_code,
-			     NULL, test_time, &test_root );
+			     NULL, test_time, &empty_store, &test_root );
 
 	/* Check expired signature */
 	cms_verify_fail_ok ( &codesigned_sig, &test_code,
-			     NULL, test_expired, &test_root );
+			     NULL, test_expired, &empty_store, &test_root );
+
+	/* Sanity check */
+	assert ( list_empty ( &empty_store.links ) );
 
 	/* Drop signature references */
 	cms_put ( nonsigned_sig.sig );
diff --git a/src/tests/x509_test.c b/src/tests/x509_test.c
index c014bd2e..fbf9fb40 100644
--- a/src/tests/x509_test.c
+++ b/src/tests/x509_test.c
@@ -654,14 +654,20 @@ CHAIN ( useless_chain, &useless_crt, &leaf_crt,	&intermediate_crt, &root_crt );
 CHAIN ( bad_path_len_chain, &bad_path_len_crt, &useless_crt, &leaf_crt,
 	&intermediate_crt, &root_crt );
 
-/** Certificate store containing the iPXE self-test root CA */
+/** Empty certificate store */
+static struct x509_chain empty_store = {
+	.refcnt = REF_INIT ( ref_no_free ),
+	.links = LIST_HEAD_INIT ( empty_store.links ),
+};
+
+/** Root certificate list containing the iPXE self-test root CA */
 static struct x509_root test_root = {
 	.digest = &x509_test_algorithm,
 	.count = 1,
 	.fingerprints = root_crt_fingerprint,
 };
 
-/** Certificate store containing the iPXE self-test intermediate CA */
+/** Root certificate list containing the iPXE self-test intermediate CA */
 static struct x509_root intermediate_root = {
 	.digest = &x509_test_algorithm,
 	.count = 1,
@@ -813,12 +819,13 @@ static time_t test_ca_expired = 2205014905ULL; /* Wed Nov 16 00:08:25 2039 */
  *
  * @v chn		Test certificate chain
  * @v time		Test certificate validation time
- * @v root		Test root certificate store
+ * @v store		Test certificate store
+ * @v root		Test root certificate list
  */
-#define x509_validate_chain_ok( chn, time, root ) do {			\
+#define x509_validate_chain_ok( chn, time, store, root ) do {		\
 	x509_invalidate_chain ( (chn)->chain );				\
 	ok ( x509_validate_chain ( (chn)->chain, (time),		\
-				   (root) ) == 0 );			\
+				   (store), (root) ) == 0 );		\
 	} while ( 0 )
 
 /**
@@ -826,12 +833,13 @@ static time_t test_ca_expired = 2205014905ULL; /* Wed Nov 16 00:08:25 2039 */
  *
  * @v chn		Test certificate chain
  * @v time		Test certificate validation time
- * @v root		Test root certificate store
+ * @v store		Test certificate store
+ * @v root		Test root certificate list
  */
-#define x509_validate_chain_fail_ok( chn, time, root ) do {		\
+#define x509_validate_chain_fail_ok( chn, time, store, root ) do {	\
 	x509_invalidate_chain ( (chn)->chain );				\
 	ok ( x509_validate_chain ( (chn)->chain, (time),		\
-				   (root) ) != 0 );			\
+				   (store), (root) ) != 0 );		\
 	} while ( 0 )
 
 /**
@@ -898,25 +906,35 @@ static void x509_test_exec ( void ) {
 	x509_chain_ok ( &bad_path_len_chain );
 
 	/* Check certificate chains */
-	x509_validate_chain_ok ( &server_chain, test_time, &test_root );
-	x509_validate_chain_ok ( &server_chain, test_time, &intermediate_root );
-	x509_validate_chain_fail_ok ( &server_chain, test_time, &dummy_root );
+	x509_validate_chain_ok ( &server_chain, test_time,
+				 &empty_store, &test_root );
+	x509_validate_chain_ok ( &server_chain, test_time,
+				 &empty_store, &intermediate_root );
+	x509_validate_chain_fail_ok ( &server_chain, test_time,
+				      &empty_store, &dummy_root );
 	x509_validate_chain_fail_ok ( &broken_server_chain, test_time,
-				      &test_root );
+				      &empty_store, &test_root );
 	x509_validate_chain_fail_ok ( &incomplete_server_chain, test_time,
-				      &test_root );
+				      &empty_store, &test_root );
 	x509_validate_chain_ok ( &incomplete_server_chain, test_time,
-				 &intermediate_root );
-	x509_validate_chain_fail_ok ( &not_ca_chain, test_time, &test_root );
-	x509_validate_chain_ok ( &useless_chain, test_time, &test_root );
+				 &empty_store, &intermediate_root );
+	x509_validate_chain_fail_ok ( &not_ca_chain, test_time,
+				      &empty_store, &test_root );
+	x509_validate_chain_ok ( &useless_chain, test_time,
+				 &empty_store, &test_root );
 	x509_validate_chain_fail_ok ( &bad_path_len_chain, test_time,
-				      &test_root );
+				      &empty_store, &test_root );
 
 	/* Check certificate chain expiry times */
-	x509_validate_chain_fail_ok ( &server_chain, test_expired, &test_root );
-	x509_validate_chain_ok ( &useless_chain, test_expired, &test_root );
+	x509_validate_chain_fail_ok ( &server_chain, test_expired,
+				      &empty_store, &test_root );
+	x509_validate_chain_ok ( &useless_chain, test_expired,
+				 &empty_store, &test_root );
 	x509_validate_chain_fail_ok ( &useless_chain, test_ca_expired,
-				      &test_root );
+				      &empty_store, &test_root );
+
+	/* Sanity check */
+	assert ( list_empty ( &empty_store.links ) );
 
 	/* Drop chain references */
 	x509_chain_put ( bad_path_len_chain.chain );
diff --git a/src/usr/imgtrust.c b/src/usr/imgtrust.c
index c49eb7f2..da7ff2ef 100644
--- a/src/usr/imgtrust.c
+++ b/src/usr/imgtrust.c
@@ -84,7 +84,7 @@ int imgverify ( struct image *image, struct image *signature,
 	/* Use signature to verify image */
 	now = time ( NULL );
 	if ( ( rc = cms_verify ( sig, image->data, image->len,
-				 name, now, NULL ) ) != 0 )
+				 name, now, NULL, NULL ) ) != 0 )
 		goto err_verify;
 
 	/* Drop reference to signature */