On Mon, May 08, 2023 at 02:01:52PM +0200, Theo Buehler wrote:
> 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.
OK claudio@
> 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;
> }
>
--
:wq Claudio
