From 967224c858b984834d6cb029d03fff826959fbfc Mon Sep 17 00:00:00 2001 From: tb Date: Tue, 9 May 2023 10:34:32 +0000 Subject: [PATCH] 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 --- usr.sbin/rpki-client/cert.c | 3 ++- usr.sbin/rpki-client/extern.h | 3 ++- usr.sbin/rpki-client/validate.c | 46 +++++++++++++++++++++++---------- 3 files changed, 37 insertions(+), 15 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 * Copyright (c) 2021 Job Snijders @@ -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"); diff --git a/usr.sbin/rpki-client/extern.h b/usr.sbin/rpki-client/extern.h index 4c1217aa975..68d724de2cc 100644 --- a/usr.sbin/rpki-client/extern.h +++ b/usr.sbin/rpki-client/extern.h @@ -1,4 +1,4 @@ -/* $OpenBSD: extern.h,v 1.180 2023/04/27 08:37:53 beck Exp $ */ +/* $OpenBSD: extern.h,v 1.181 2023/05/09 10:34:32 tb Exp $ */ /* * Copyright (c) 2019 Kristaps Dzonsons * @@ -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 diff --git a/usr.sbin/rpki-client/validate.c b/usr.sbin/rpki-client/validate.c index b21ff004c64..7a8af6ef2b8 100644 --- a/usr.sbin/rpki-client/validate.c +++ b/usr.sbin/rpki-client/validate.c @@ -1,4 +1,4 @@ -/* $OpenBSD: validate.c,v 1.59 2023/04/27 08:37:53 beck Exp $ */ +/* $OpenBSD: validate.c,v 1.60 2023/05/09 10:34:32 tb Exp $ */ /* * Copyright (c) 2019 Kristaps Dzonsons * @@ -332,25 +332,37 @@ valid_origin(const char *uri, const char *proto) } /* - * 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 *store_ctx, X509 *x509, struct auth *a, { 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 *store_ctx, X509 *x509, struct auth *a, 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; } -- 2.20.1