The diff below is based on a hint by beck and was discussed extensively
with beck, claudio and job during and after m2k23. It results in a quite
significant reduction of the runtime of an ordinary rpki-client run as
usually done from cron.
One problem we're facing with the generally rather poor quality RFC 3779
code in libcrypto is that its performance is abysmal. Flame graphs show
a lot of time spent in addr_contains(). While there is some room for
improvement in that function itself (the containment check for prefixes
could be optimized quite a bit), we can avoid a lot of the most expensive
checking of certificates with tons of resources close to the TA by using
the 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 the trust
anchor for our chains via the X509_V_FLAG_PARTIAL_CHAIN flag for the
verifier. 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. There is no downside to doing this since we have already
validated the path from all certs in the auth tree to the root.
In my testing, this avoids 30-50% of overhead and works equally well
with LibreSSL and OpenSSL 1.1.
I currently hang any_inherits off struct auth. It may be worthwhile to
move that to struct cert and populate it in cert_parse_pre() in a later
step.
Index: cert.c
===================================================================
RCS file: /cvs/src/usr.sbin/rpki-client/cert.c,v
retrieving revision 1.107
diff -u -p -r1.107 cert.c
--- cert.c 15 Apr 2023 00:39:08 -0000 1.107
+++ cert.c 8 May 2023 11:04:30 -0000
@@ -1092,6 +1092,7 @@ auth_insert(struct auth_tree *auths, str
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");
Index: extern.h
===================================================================
RCS file: /cvs/src/usr.sbin/rpki-client/extern.h,v
retrieving revision 1.180
diff -u -p -r1.180 extern.h
--- extern.h 27 Apr 2023 08:37:53 -0000 1.180
+++ extern.h 8 May 2023 11:04:30 -0000
@@ -454,6 +454,7 @@ struct auth {
RB_ENTRY(auth) entry;
struct cert *cert; /* owner information */
struct auth *parent; /* pointer to parent or NULL for TA cert */
+ int any_inherits;
};
/*
* Tree of auth sorted by ski
Index: validate.c
===================================================================
RCS file: /cvs/src/usr.sbin/rpki-client/validate.c,v
retrieving revision 1.59
diff -u -p -r1.59 validate.c
--- validate.c 27 Apr 2023 08:37:53 -0000 1.59
+++ validate.c 8 May 2023 11:29:56 -0000
@@ -332,25 +332,37 @@ valid_origin(const char *uri, const char
}
/*
- * Walk the certificate tree to the root and build a certificate
- * chain from cert->x509. All certs in the tree are validated and
- * can be loaded as trusted stack into the validator.
+ * Walk the tree of known valid CA certificates until we find a certificate
that
+ * doesn't inherit. Build a chain of intermediates and use the non-inheriting
+ * certificate as a trusted root by virtue of X509_V_FLAG_PARTIAL_CHAIN. The
+ * RFC 3779 path validation needs a non-inheriting trust root to ensure that
+ * all delegated resources are covered.
*/
static void
-build_chain(const struct auth *a, STACK_OF(X509) **chain)
+build_chain(const struct auth *a, STACK_OF(X509) **intermediates,
+ STACK_OF(X509) **root)
{
- *chain = NULL;
+ *intermediates = NULL;
+ *root = NULL;
if (a == NULL)
return;
- if ((*chain = sk_X509_new_null()) == NULL)
+ if ((*intermediates = sk_X509_new_null()) == NULL)
+ err(1, "sk_X509_new_null");
+ if ((*root = sk_X509_new_null()) == NULL)
err(1, "sk_X509_new_null");
for (; a != NULL; a = a->parent) {
assert(a->cert->x509 != NULL);
- if (!sk_X509_push(*chain, a->cert->x509))
+ if (!a->any_inherits) {
+ if (!sk_X509_push(*root, a->cert->x509))
+ errx(1, "sk_X509_push");
+ break;
+ }
+ if (!sk_X509_push(*intermediates, a->cert->x509))
errx(1, "sk_X509_push");
}
+ assert(sk_X509_num(*root) == 1);
}
/*
@@ -381,13 +393,13 @@ valid_x509(char *file, X509_STORE_CTX *s
{
X509_VERIFY_PARAM *params;
ASN1_OBJECT *cp_oid;
- STACK_OF(X509) *chain;
+ STACK_OF(X509) *intermediates, *root;
STACK_OF(X509_CRL) *crls = NULL;
unsigned long flags;
int error;
*errstr = NULL;
- build_chain(a, &chain);
+ build_chain(a, &intermediates, &root);
build_crls(crl, &crls);
assert(store_ctx != NULL);
@@ -404,25 +416,33 @@ valid_x509(char *file, X509_STORE_CTX *s
X509_VERIFY_PARAM_set_time(params, evaluation_time);
flags = X509_V_FLAG_CRL_CHECK;
+ flags |= X509_V_FLAG_PARTIAL_CHAIN;
flags |= X509_V_FLAG_POLICY_CHECK;
flags |= X509_V_FLAG_EXPLICIT_POLICY;
flags |= X509_V_FLAG_INHIBIT_MAP;
X509_STORE_CTX_set_flags(store_ctx, flags);
X509_STORE_CTX_set_depth(store_ctx, MAX_CERT_DEPTH);
- X509_STORE_CTX_set0_trusted_stack(store_ctx, chain);
+ /*
+ * See the comment above build_chain() for details on what's happening
+ * here. The nomenclature in this API is dubious and poorly documented.
+ */
+ X509_STORE_CTX_set0_untrusted(store_ctx, intermediates);
+ X509_STORE_CTX_set0_trusted_stack(store_ctx, root);
X509_STORE_CTX_set0_crls(store_ctx, crls);
if (X509_verify_cert(store_ctx) <= 0) {
error = X509_STORE_CTX_get_error(store_ctx);
*errstr = X509_verify_cert_error_string(error);
X509_STORE_CTX_cleanup(store_ctx);
- sk_X509_free(chain);
+ sk_X509_free(intermediates);
+ sk_X509_free(root);
sk_X509_CRL_free(crls);
return 0;
}
X509_STORE_CTX_cleanup(store_ctx);
- sk_X509_free(chain);
+ sk_X509_free(intermediates);
+ sk_X509_free(root);
sk_X509_CRL_free(crls);
return 1;
}
