rpki-client: use partial chains in certificate validation

The generally rather poor quality RFC 3779 code in libcrypto also performs
abysmally. Flame graphs show that nearly 20% of the parser process is spent
in addr_contains() alone. There is room for improvement in addr_contains()
itself - the containment check for prefixes could be optimized quite a bit.
We can avoid a lot of the most expensive work for certificates with tons of
resources close to the TA by using the verifier's partial chains flag.

More precisely, in the tree of already validated certs look for the first
one that has no inherited RFC 3779 resources and use that as 'trust anchor'
for our chains via the X509_V_FLAG_PARTIAL_CHAIN flag. This way we can be
sure that a leaf's delegated resources are properly covered and at the same
time significantly shorten most paths validated.

Job's and my testing indicates that this avoids 30-50% of overhead and works
equally well with LibreSSL and OpenSSL >= 1.1. The main bottlenecks in the
parser process now appear to be SHA-2 and RSA/BIGNUM, two well-known pain
points in libcrypto.

This is based on a hint by beck and was discussed extensively with beck,
claudio and job during and after m2k23.

ok claudio job

1 files changed, 2 insertions, 1 deletions

diff --git a/usr.sbin/rpki-client/cert.c b/usr.sbin/rpki-client/cert.c
index 0ed702044d1..f8f7c42b912 100644
--- a/usr.sbin/rpki-client/cert.c
+++ b/usr.sbin/rpki-client/cert.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: cert.c,v 1.107 2023/04/15 00:39:08 job Exp $ */
+/*	$OpenBSD: cert.c,v 1.108 2023/05/09 10:34:32 tb Exp $ */
 /*
  * Copyright (c) 2022 Theo Buehler <tb@openbsd.org>
  * Copyright (c) 2021 Job Snijders <job@openbsd.org>
@@ -1092,6 +1092,7 @@ auth_insert(struct auth_tree *auths, struct cert *cert, struct auth *parent)
 
 	na->parent = parent;
 	na->cert = cert;
+	na->any_inherits = x509_any_inherits(cert->x509);
 
 	if (RB_INSERT(auth_tree, auths, na) != NULL)
 		err(1, "auth tree corrupted");