x509: sort stacks before finds

x509_trust.c, x509_vpm.c and v3_lib.c don't have a lock for their sorts.
This is no worse than the existing code which sorted silently without locks.

Addition is quadratic time in by_dir.c and v3_purp.c.  However, this
is an improvement over the older O(n^2 log n) code where each find also
sorted the stack.  Also note that v3_purp.c is limited to a maximum of
10 items, so quadratic behaviour isn't terrible.

Reviewed-by: Tomas Mraz <tomas@openssl.org>
Reviewed-by: Todd Short <todd.short@me.com>
(Merged from https://github.com/openssl/openssl/pull/20842)

7 files changed, 24 insertions, 0 deletions

diff --git a/crypto/x509/by_dir.c b/crypto/x509/by_dir.c
index 3fc52be474..3c7f67b5a1 100644
--- a/crypto/x509/by_dir.c
+++ b/crypto/x509/by_dir.c
@@ -348,6 +348,9 @@ static int get_cert_by_subject_ex(X509_LOOKUP *xl, X509_LOOKUP_TYPE type,
 
         /*
          * we have added it to the cache so now pull it out again
+         *
+         * Note: quadratic time find here since the objects won't generally be
+         *       sorted and sorting the would result in O(n^2 log n) complexity.
          */
         X509_STORE_lock(xl->store_ctx);
         j = sk_X509_OBJECT_find(xl->store_ctx->objs, &stmp);
@@ -417,6 +420,13 @@ static int get_cert_by_subject_ex(X509_LOOKUP *xl, X509_LOOKUP_TYPE type,
         }
     }
  finish:
+    /* If we changed anything, resort the objects for faster lookup */
+    if (!sk_X509_OBJECT_is_sorted(xl->store_ctx->objs)) {
+        X509_STORE_lock(xl->store_ctx);
+        sk_X509_OBJECT_sort(xl->store_ctx->objs);
+        X509_STORE_unlock(xl->store_ctx);
+    }
+
     BUF_MEM_free(b);
     return ok;
 }
diff --git a/crypto/x509/pcy_cache.c b/crypto/x509/pcy_cache.c
index e9f45a80bb..b5bb49d437 100644
--- a/crypto/x509/pcy_cache.c
+++ b/crypto/x509/pcy_cache.c
@@ -63,6 +63,8 @@ static int policy_cache_create(X509 *x,
         }
         data = NULL;
     }
+    /* Sort so we can find more quickly */
+    sk_X509_POLICY_DATA_sort(cache->data);
     ret = 1;
 
  bad_policy:
diff --git a/crypto/x509/pcy_tree.c b/crypto/x509/pcy_tree.c
index 95fb46f4ec..15dfbfca2e 100644
--- a/crypto/x509/pcy_tree.c
+++ b/crypto/x509/pcy_tree.c
@@ -689,6 +689,7 @@ int X509_policy_check(X509_POLICY_TREE **ptree, int *pexplicit_policy,
 
     if ((calc_ret = tree_calculate_authority_set(tree, &auth_nodes)) == 0)
         goto error;
+    sk_X509_POLICY_NODE_sort(auth_nodes);
     ret = tree_calculate_user_set(tree, policy_oids, auth_nodes);
     if (calc_ret == TREE_CALC_OK_DOFREE)
         sk_X509_POLICY_NODE_free(auth_nodes);
diff --git a/crypto/x509/v3_addr.c b/crypto/x509/v3_addr.c
index 0ab202400e..221acd09b0 100644
--- a/crypto/x509/v3_addr.c
+++ b/crypto/x509/v3_addr.c
@@ -1176,6 +1176,8 @@ int X509v3_addr_subset(IPAddrBlocks *a, IPAddrBlocks *b)
     if (b == NULL || X509v3_addr_inherits(a) || X509v3_addr_inherits(b))
         return 0;
     (void)sk_IPAddressFamily_set_cmp_func(b, IPAddressFamily_cmp);
+    sk_IPAddressFamily_sort(b);
+    /* Could sort a here too and get O(|a|) running time instead of O(|a| ln |b|) */
     for (i = 0; i < sk_IPAddressFamily_num(a); i++) {
         IPAddressFamily *fa = sk_IPAddressFamily_value(a, i);
         int j = sk_IPAddressFamily_find(b, fa);
@@ -1257,6 +1259,7 @@ static int addr_validate_path_internal(X509_STORE_CTX *ctx,
             ctx->error = X509_V_ERR_OUT_OF_MEM;
         goto done;
     }
+    sk_IPAddressFamily_sort(child);
 
     /*
      * Now walk up the chain.  No cert may list resources that its
@@ -1282,6 +1285,7 @@ static int addr_validate_path_internal(X509_STORE_CTX *ctx,
         }
         (void)sk_IPAddressFamily_set_cmp_func(x->rfc3779_addr,
                                               IPAddressFamily_cmp);
+        sk_IPAddressFamily_sort(x->rfc3779_addr);
         for (j = 0; j < sk_IPAddressFamily_num(child); j++) {
             IPAddressFamily *fc = sk_IPAddressFamily_value(child, j);
             int k = sk_IPAddressFamily_find(x->rfc3779_addr, fc);
diff --git a/crypto/x509/v3_lib.c b/crypto/x509/v3_lib.c
index ced105adfa..3f933ee8b9 100644
--- a/crypto/x509/v3_lib.c
+++ b/crypto/x509/v3_lib.c
@@ -63,7 +63,10 @@ const X509V3_EXT_METHOD *X509V3_EXT_get_nid(int nid)
         return *ret;
     if (!ext_list)
         return NULL;
+    /* Ideally, this would be done under a lock */
+    sk_X509V3_EXT_METHOD_sort(ext_list);
     idx = sk_X509V3_EXT_METHOD_find(ext_list, &tmp);
+    /* A failure to locate the item is handled by the value method */
     return sk_X509V3_EXT_METHOD_value(ext_list, idx);
 }
 
diff --git a/crypto/x509/x509_trust.c b/crypto/x509/x509_trust.c
index 656b3b8440..d85b775f5e 100644
--- a/crypto/x509/x509_trust.c
+++ b/crypto/x509/x509_trust.c
@@ -105,6 +105,8 @@ int X509_TRUST_get_by_id(int id)
     if (trtable == NULL)
         return -1;
     tmp.trust = id;
+    /* Ideally, this would be done under lock */
+    sk_X509_TRUST_sort(trtable);
     idx = sk_X509_TRUST_find(trtable, &tmp);
     if (idx < 0)
         return -1;
diff --git a/crypto/x509/x509_vpm.c b/crypto/x509/x509_vpm.c
index 28d11dedfa..8dd1199814 100644
--- a/crypto/x509/x509_vpm.c
+++ b/crypto/x509/x509_vpm.c
@@ -635,6 +635,8 @@ const X509_VERIFY_PARAM *X509_VERIFY_PARAM_lookup(const char *name)
 
     pm.name = (char *)name;
     if (param_table != NULL) {
+        /* Ideally, this would be done under a lock */
+        sk_X509_VERIFY_PARAM_sort(param_table);
         idx = sk_X509_VERIFY_PARAM_find(param_table, &pm);
         if (idx >= 0)
             return sk_X509_VERIFY_PARAM_value(param_table, idx);