Sort various X.509 global lists sooner

These functions need a lot more work, documentation, warnings
that using them isn't a good idea, and really we should just remove them
entirely.

But, for now, this is a minimal fix to the most egregious of issues: not
only are the functions themselves not thread-safe (i.e. you must call it
in some program-global initialization), but using them puts you in a
state where future uses of the X.509 library are not thread-safe! Fix
the latter by sorting the list at the point we're already mutating
things.

Re-sorting a list after every addition is not a particularly sensible
implementation, but we can assume these lists will only ever contain
O(1) entries.

(The sort calls date to
https://boringssl-review.googlesource.com/c/boringssl/+/27304, but the
issue was there before. Prior to that CL, sk_FOO_find implicitly sorted
the list. That CL made sk_FOO_find itself a const operation, necessary
for this, and just added explicit sk_FOO_sort calls to preserve the
existing behavior, initially.)

Change-Id: I063b8e708eaf17dfe66c5a3e8d33733adb3297e9
Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/58385
Auto-Submit: David Benjamin <davidben@google.com>
Reviewed-by: Bob Beck <bbe@google.com>
Commit-Queue: Bob Beck <bbe@google.com>

crypto/x509/x509_trs.c

diff --git a/crypto/x509/x509_trs.c b/crypto/x509/x509_trs.c
index 1329a9f..553a0ae 100644
--- a/crypto/x509/x509_trs.c
+++ b/crypto/x509/x509_trs.c
@@ -152,7 +152,6 @@
   if (!trtable) {
     return -1;
   }
-  sk_X509_TRUST_sort(trtable);
   if (!sk_X509_TRUST_find(trtable, &idx, &tmp)) {
     return -1;
   }
@@ -216,6 +215,10 @@
 
   // If its a new entry manage the dynamic table
   if (idx == -1) {
+    // TODO(davidben): This should be locked. Alternatively, remove the dynamic
+    // registration mechanism entirely. The trouble is there no way to pass in
+    // the various parameters into an |X509_VERIFY_PARAM| directly. You can only
+    // register it in the global table and get an ID.
     if (!trtable && !(trtable = sk_X509_TRUST_new(tr_cmp))) {
       trtable_free(trtmp);
       return 0;
@@ -224,6 +227,7 @@
       trtable_free(trtmp);
       return 0;
     }
+    sk_X509_TRUST_sort(trtable);
   }
   return 1;
 }

crypto/x509/x509_vpm.c

diff --git a/crypto/x509/x509_vpm.c b/crypto/x509/x509_vpm.c
index d985cb7..f14a531 100644
--- a/crypto/x509/x509_vpm.c
+++ b/crypto/x509/x509_vpm.c
@@ -554,6 +554,8 @@
 }
 
 int X509_VERIFY_PARAM_add0_table(X509_VERIFY_PARAM *param) {
+  // TODO(davidben): This should be locked. Alternatively, remove the dynamic
+  // registration mechanism entirely.
   X509_VERIFY_PARAM *ptmp;
   if (!param_table) {
     param_table = sk_X509_VERIFY_PARAM_new(param_cmp);
@@ -562,8 +564,6 @@
     }
   } else {
     size_t idx;
-
-    sk_X509_VERIFY_PARAM_sort(param_table);
     if (sk_X509_VERIFY_PARAM_find(param_table, &idx, param)) {
       ptmp = sk_X509_VERIFY_PARAM_value(param_table, idx);
       X509_VERIFY_PARAM_free(ptmp);
@@ -573,6 +573,7 @@
   if (!sk_X509_VERIFY_PARAM_push(param_table, param)) {
     return 0;
   }
+  sk_X509_VERIFY_PARAM_sort(param_table);
   return 1;
 }
 
@@ -599,7 +600,6 @@
   pm.name = (char *)name;
   if (param_table) {
     size_t idx;
-    sk_X509_VERIFY_PARAM_sort(param_table);
     if (sk_X509_VERIFY_PARAM_find(param_table, &idx, &pm)) {
       return sk_X509_VERIFY_PARAM_value(param_table, idx);
     }

crypto/x509v3/v3_lib.c

diff --git a/crypto/x509v3/v3_lib.c b/crypto/x509v3/v3_lib.c
index d006a5e..5a3c3e8 100644
--- a/crypto/x509v3/v3_lib.c
+++ b/crypto/x509v3/v3_lib.c
@@ -78,6 +78,7 @@
 }
 
 int X509V3_EXT_add(X509V3_EXT_METHOD *ext) {
+  // TODO(davidben): This should be locked. Also check for duplicates.
   if (!ext_list && !(ext_list = sk_X509V3_EXT_METHOD_new(ext_stack_cmp))) {
     ext_list_free(ext);
     return 0;
@@ -86,6 +87,7 @@
     ext_list_free(ext);
     return 0;
   }
+  sk_X509V3_EXT_METHOD_sort(ext_list);
   return 1;
 }
 
@@ -113,7 +115,6 @@
     return NULL;
   }
 
-  sk_X509V3_EXT_METHOD_sort(ext_list);
   if (!sk_X509V3_EXT_METHOD_find(ext_list, &idx, &tmp)) {
     return NULL;
   }

crypto/x509v3/v3_purp.c

diff --git a/crypto/x509v3/v3_purp.c b/crypto/x509v3/v3_purp.c
index 71b2c6d..8c254e8 100644
--- a/crypto/x509v3/v3_purp.c
+++ b/crypto/x509v3/v3_purp.c
@@ -201,7 +201,6 @@
     return -1;
   }
 
-  sk_X509_PURPOSE_sort(xptable);
   if (!sk_X509_PURPOSE_find(xptable, &idx, &tmp)) {
     return -1;
   }
@@ -267,6 +266,10 @@
 
   // If its a new entry manage the dynamic table
   if (idx == -1) {
+    // TODO(davidben): This should be locked. Alternatively, remove the dynamic
+    // registration mechanism entirely. The trouble is there no way to pass in
+    // the various parameters into an |X509_VERIFY_PARAM| directly. You can only
+    // register it in the global table and get an ID.
     if (!xptable && !(xptable = sk_X509_PURPOSE_new(xp_cmp))) {
       xptable_free(ptmp);
       return 0;
@@ -275,6 +278,7 @@
       xptable_free(ptmp);
       return 0;
     }
+    sk_X509_PURPOSE_sort(xptable);
   }
   return 1;
 }