# UNDF: UNDF-2026-000000491
# openssl-0004: CWE-407 O(N²) CA name dedup in SSL_add_store_cert_subjects_to_stack

## Severity: MEDIUM

## Location
`ssl/ssl_cert.c` — `add_uris_recursive()` called from `SSL_add_store_cert_subjects_to_stack()`

## Description

`SSL_add_store_cert_subjects_to_stack()` loads CA subject names from a URI store
(e.g., a PKCS#11 token or directory) and deduplicates them into a
`STACK_OF(X509_NAME)`.  It calls `add_uris_recursive()` for the actual loading.

`add_uris_recursive()` contains this pattern:

```c
while (!OSSL_STORE_eof(ctx) && !OSSL_STORE_error(ctx)) {
    ...
    if (sk_X509_NAME_find(stack, xn) >= 0) {   /* O(N) linear scan */
        /* Duplicate */
        X509_NAME_free(xn);
    } else if (!sk_X509_NAME_push(stack, xn)) {
        ...
    }
}
```

`sk_X509_NAME_find()` calls `internal_find()`.  When the stack is **unsorted**
(which it is here — `add_uris_recursive` never calls `sk_X509_NAME_sort()`),
`internal_find()` falls through to a linear scan:

```c
if (!st->sorted) {
    for (i = 0; i < st->num; i++) {
        cmp_ret = cmp_with_thunk(st, &data, st->data + i);
        if (cmp_ret == 0) { ... return i; }
    }
    return -1;
}
```

Each call is O(N).  Loading N certificates from the store requires N such calls,
giving **O(N²)** total comparisons.

By contrast, both `SSL_add_file_cert_subjects_to_stack` and
`SSL_add_dir_cert_subjects_to_stack` received an explicit LHASH fix (visible in
the same file) that pre-populates an `LHASH_OF(X509_NAME)` for O(1) duplicate
detection.  `SSL_add_store_cert_subjects_to_stack` was left behind.

## Complexity Before Fix

| N (CA certs in store) | Comparisons (O(N²)) |
|-----------------------|---------------------|
| 100                   | ~5,050              |
| 500                   | ~125,250            |
| 1,000                 | ~500,500            |
| 5,000                 | ~12,502,500         |

Each comparison calls `xname_sk_cmp → X509_NAME_cmp → X509_NAME_cmp_ex`
which allocates and DER-encodes the name — making each O(N) scan carry
non-trivial constant work beyond the raw count.

## Fix

Pass an `LHASH_OF(X509_NAME)` into `add_uris_recursive()` just as
`SSL_add_dir_cert_subjects_to_stack` does for the per-file helper, replacing
`sk_X509_NAME_find()` with `lh_X509_NAME_retrieve()`.

```diff
--- a/ssl/ssl_cert.c
+++ b/ssl/ssl_cert.c
@@ -1022,7 +1022,8 @@ static int add_uris_recursive(STACK_OF(X509_NAME) *stack,
-static int add_uris_recursive(STACK_OF(X509_NAME) *stack,
-    const char *uri, int depth)
+static int add_uris_recursive(STACK_OF(X509_NAME) *stack,
+    LHASH_OF(X509_NAME) *name_hash,
+    const char *uri, int depth)
 {
     ...
     if (infotype == OSSL_STORE_INFO_NAME) {
         if (depth > 0)
-            ok = add_uris_recursive(stack, OSSL_STORE_INFO_get0_NAME(info),
-                depth - 1);
+            ok = add_uris_recursive(stack, name_hash,
+                OSSL_STORE_INFO_get0_NAME(info), depth - 1);
     } else if (infotype == OSSL_STORE_INFO_CERT) {
         ...
-        if (sk_X509_NAME_find(stack, xn) >= 0) {
+        if (lh_X509_NAME_retrieve(name_hash, xn) != NULL) {
             /* Duplicate. */
             X509_NAME_free(xn);
         } else if (!sk_X509_NAME_push(stack, xn)) {
             ...
+        } else {
+            lh_X509_NAME_insert(name_hash, xn);
         }
     }
     ...
 }

 int SSL_add_store_cert_subjects_to_stack(STACK_OF(X509_NAME) *stack,
     const char *store)
 {
     int (*oldcmp)(const X509_NAME *const *a, const X509_NAME *const *b)
         = sk_X509_NAME_set_cmp_func(stack, xname_sk_cmp);
+    LHASH_OF(X509_NAME) *name_hash = lh_X509_NAME_new(xname_hash, xname_cmp);
+    int ret;
+    X509_NAME *xn;
+    int idx, num;
+
+    if (name_hash == NULL) {
+        (void)sk_X509_NAME_set_cmp_func(stack, oldcmp);
+        return 0;
+    }
+
+    /* Pre-populate lhash with names already on the stack */
+    num = sk_X509_NAME_num(stack);
+    for (idx = 0; idx < num; idx++) {
+        xn = sk_X509_NAME_value(stack, idx);
+        lh_X509_NAME_insert(name_hash, xn);
+    }
+
-    int ret = add_uris_recursive(stack, store, 1);
+    ret = add_uris_recursive(stack, name_hash, store, 1);
+    lh_X509_NAME_free(name_hash);
     (void)sk_X509_NAME_set_cmp_func(stack, oldcmp);
     return ret;
 }
```

## Complexity After Fix

O(N) total — each name is hashed once (O(1) amortized) during insertion.
`lh_X509_NAME_retrieve` is O(1) amortized.

## Speedup

| N   | Before (comparisons) | After (hash ops) | Ratio |
|-----|---------------------|------------------|-------|
| 100 | 5,050               | ~100             | ~50x  |
| 500 | 125,250             | ~500             | ~250x |
| 1000| 500,500             | ~1,000           | ~500x |

## References
- CWE-407: Inefficient Algorithmic Complexity
- `ssl/ssl_cert.c` — `SSL_add_dir_cert_subjects_to_stack()` (already fixed, same file)
- `crypto/stack/stack.c` — `internal_find()` linear path when `!st->sorted`
