Add issuer cache, to be used by upcoming changes to validation code.

ok tb@ jsing@

3 files changed, 216 insertions, 1 deletions

diff --git a/lib/libcrypto/Makefile b/lib/libcrypto/Makefile
index 9207b93f321..2e778a5b232 100644
--- a/lib/libcrypto/Makefile
+++ b/lib/libcrypto/Makefile
@@ -1,4 +1,4 @@
-# $OpenBSD: Makefile,v 1.42 2020/06/09 16:53:52 deraadt Exp $
+# $OpenBSD: Makefile,v 1.43 2020/09/11 14:30:51 beck Exp $
 
 LIB=	crypto
 LIBREBUILD=y
@@ -277,6 +277,7 @@ SRCS+= x509_bcons.c x509_bitst.c x509_conf.c x509_extku.c x509_ia5.c x509_lib.c
 SRCS+= x509_prn.c x509_utl.c x509_genn.c x509_alt.c x509_skey.c x509_akey.c x509_pku.c
 SRCS+= x509_int.c x509_enum.c x509_sxnet.c x509_cpols.c x509_crld.c x509_purp.c x509_info.c
 SRCS+= x509_ocsp.c x509_akeya.c x509_pmaps.c x509_pcons.c x509_ncons.c x509_pcia.c x509_pci.c
+SRCS+= x509_issuer_cache.c
 SRCS+= pcy_cache.c pcy_node.c pcy_data.c pcy_map.c pcy_tree.c pcy_lib.c
 
 .PATH:	${.CURDIR}/arch/${MACHINE_CPU} \
diff --git a/lib/libcrypto/x509/x509_issuer_cache.c b/lib/libcrypto/x509/x509_issuer_cache.c
new file mode 100644
index 00000000000..6831c18986c
--- /dev/null
+++ b/lib/libcrypto/x509/x509_issuer_cache.c
@@ -0,0 +1,167 @@
+/* $OpenBSD: x509_issuer_cache.c,v 1.1 2020/09/11 14:30:51 beck Exp $ */
+/*
+ * Copyright (c) 2020 Bob Beck <beck@openbsd.org>
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+/* x509_issuer_cache */
+
+/*
+ * The issuer cache is a cache of parent and child x509 certificate
+ * hashes with a signature validation result.
+ *
+ * Entries should only be added to the cache with a validation result
+ * from checking the public key math that "parent" signed "child".
+ *
+ * Finding an entry in the cache gets us the result of a previously
+ * performed validation of the signature of "parent" signing for the
+ * validity of "child". It allows us to skip doing the public key math
+ * when validating a certificate chain. It does not allow us to skip
+ * any other steps of validation (times, names, key usage, etc.)
+ */
+
+#include <pthread.h>
+#include <string.h>
+
+#include "x509_issuer_cache.h"
+
+static int
+x509_issuer_cmp(struct x509_issuer *x1, struct x509_issuer *x2)
+{
+	int pcmp;
+	if ((pcmp = memcmp(x1->parent_md, x2->parent_md, EVP_MAX_MD_SIZE)) != 0)
+		return pcmp;
+	return memcmp(x1->child_md, x2->child_md, EVP_MAX_MD_SIZE);
+}
+
+static size_t x509_issuer_cache_count;
+static size_t x509_issuer_cache_max = X509_ISSUER_CACHE_MAX;
+static RB_HEAD(x509_issuer_tree, x509_issuer) x509_issuer_cache =
+    RB_INITIALIZER(&x509_issuer_cache);
+static TAILQ_HEAD(lruqueue, x509_issuer) x509_issuer_lru =
+    TAILQ_HEAD_INITIALIZER(x509_issuer_lru);
+static pthread_mutex_t x509_issuer_tree_mutex = PTHREAD_MUTEX_INITIALIZER;
+
+RB_PROTOTYPE(x509_issuer_tree, x509_issuer, entry, x509_issuer_cmp);
+RB_GENERATE(x509_issuer_tree, x509_issuer, entry, x509_issuer_cmp);
+
+/*
+ * Set the maximum number of cached entries. On additions to the cache
+ * the least recently used entries will be discarded so that the cache
+ * stays under the maximum number of entries.  Setting a maximum of 0
+ * disables the cache.
+ */
+int
+x509_issuer_cache_set_max(size_t max)
+{
+	if (pthread_mutex_lock(&x509_issuer_tree_mutex) != 0)
+		return 0;
+	x509_issuer_cache_max = max;
+	(void) pthread_mutex_unlock(&x509_issuer_tree_mutex);
+
+	return 1;
+}
+
+/*
+ * Find a previous result of checking if parent signed child
+ *
+ * Returns:
+ * 	-1 : No entry exists in the cache. signature must be checked.
+ * 	0 : The signature of parent signing child is invalid.
+ * 	1 : The signature of parent signing child is valid.
+ */
+int
+x509_issuer_cache_find(unsigned char *parent_md, unsigned char *child_md)
+{
+	struct x509_issuer candidate, *found;
+	int ret = -1;
+
+	memset(&candidate, 0, sizeof(candidate));
+	candidate.parent_md = parent_md;
+	candidate.child_md = child_md;
+
+	if (x509_issuer_cache_max == 0)
+		return -1;
+
+	if (pthread_mutex_lock(&x509_issuer_tree_mutex) != 0)
+		return -1;
+	if ((found = RB_FIND(x509_issuer_tree, &x509_issuer_cache,
+	    &candidate)) != NULL) {
+	 	TAILQ_REMOVE(&x509_issuer_lru, found, queue);
+		TAILQ_INSERT_HEAD(&x509_issuer_lru, found, queue);
+		ret = found->valid;
+	}
+	(void) pthread_mutex_unlock(&x509_issuer_tree_mutex);
+
+	return ret;
+}
+
+/*
+ * Attempt to add a validation result to the cache.
+ *
+ * valid must be:
+ * 	0: The signature of parent signing child is invalid.
+ *	1: The signature of parent signing child is valid.
+ *
+ * Previously added entries for the same parent and child are *not* replaced.
+ */
+void
+x509_issuer_cache_add(unsigned char *parent_md, unsigned char *child_md,
+    int valid)
+{
+	struct x509_issuer *new;
+
+	if (x509_issuer_cache_max == 0)
+		return;
+	if (valid != 0 && valid != 1)
+		return;
+
+	if ((new = calloc(1, sizeof(struct x509_issuer))) == NULL)
+		return;
+	if ((new->parent_md = calloc(1, EVP_MAX_MD_SIZE)) == NULL)
+		goto err;
+	memcpy(new->parent_md, parent_md, EVP_MAX_MD_SIZE);
+	if ((new->child_md = calloc(1, EVP_MAX_MD_SIZE)) == NULL)
+		goto err;
+	memcpy(new->child_md, child_md, EVP_MAX_MD_SIZE);
+
+	new->valid = valid;
+
+	if (pthread_mutex_lock(&x509_issuer_tree_mutex) != 0)
+		goto err;
+	while (x509_issuer_cache_count >= x509_issuer_cache_max) {
+		struct x509_issuer *old;
+		if ((old = TAILQ_LAST(&x509_issuer_lru, lruqueue)) == NULL)
+			goto err;
+		TAILQ_REMOVE(&x509_issuer_lru, old, queue);
+		RB_REMOVE(x509_issuer_tree, &x509_issuer_cache, old);
+		free(old->parent_md);
+		free(old->child_md);
+		free(old);
+		x509_issuer_cache_count--;
+	}
+	if (RB_INSERT(x509_issuer_tree, &x509_issuer_cache, new) == NULL) {
+		TAILQ_INSERT_HEAD(&x509_issuer_lru, new, queue);
+		x509_issuer_cache_count++;
+		new = NULL;
+	}
+ err:
+	(void) pthread_mutex_unlock(&x509_issuer_tree_mutex);
+	if (new != NULL) {
+		free(new->parent_md);
+		free(new->child_md);
+	}
+	free(new);
+	return;
+}
diff --git a/lib/libcrypto/x509/x509_issuer_cache.h b/lib/libcrypto/x509/x509_issuer_cache.h
new file mode 100644
index 00000000000..6dedde75f1f
--- /dev/null
+++ b/lib/libcrypto/x509/x509_issuer_cache.h
@@ -0,0 +1,47 @@
+/* $OpenBSD: x509_issuer_cache.h,v 1.1 2020/09/11 14:30:51 beck Exp $ */
+/*
+ * Copyright (c) 2020 Bob Beck <beck@openbsd.org>
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+/* x509_issuer_cache */
+#ifndef HEADER_X509_ISSUER_CACHE_H
+#define HEADER_X509_ISSUER_CACHE_H
+
+#include <sys/tree.h>
+#include <sys/queue.h>
+
+#include <openssl/x509.h>
+
+__BEGIN_HIDDEN_DECLS
+
+struct x509_issuer {
+	RB_ENTRY(x509_issuer) entry;
+	TAILQ_ENTRY(x509_issuer) queue;	/* LRU of entries */
+	/* parent_md and child_md must point to EVP_MAX_MD_SIZE of memory */
+	unsigned char *parent_md;
+	unsigned char *child_md;
+	int valid;			/* Result of signature validation. */
+};
+
+#define X509_ISSUER_CACHE_MAX 40000	/* Approx 7.5 MB, entries 200 bytes */
+
+int x509_issuer_cache_set_max(size_t max);
+int x509_issuer_cache_find(unsigned char *parent_md, unsigned char *child_md);
+void x509_issuer_cache_add(unsigned char *parent_md, unsigned char *child_md,
+    int valid);
+
+__END_HIDDEN_DECLS
+
+#endif