# UNDF: UNDF-2026-000000489
# openssh-0002: CWE-407 O(N²) dedup in kex_names_cat via match_list inside loop

## Severity: MEDIUM

## Location
`kex-names.c` — `kex_names_cat()`, lines ~218–231

## Description

`kex_names_cat()` concatenates two comma-separated algorithm lists while
deduplicating. It iterates over all N entries of `b` and for each calls
`kex_has_any_alg(ret, p)`, where `ret` grows with each successful addition.

```c
char *
kex_names_cat(const char *a, const char *b)
{
    ...
    strlcpy(ret, a, len);               /* ret starts as copy of a (M entries) */
    for ((p = strsep(&cp, ",")); p && *p != '\0'; (p = strsep(&cp, ","))) {
        if (kex_has_any_alg(ret, p))    /* O(M+i) linear scan of growing ret */
            continue; /* Algorithm already present */
        strlcat(ret, ",", len);
        strlcat(ret, p, len);
    }
    ...
}
```

`kex_has_any_alg(ret, p)` calls `match_list(ret, p, NULL)` which splits `ret`
on commas and does a strcmp scan for `p`. If `a` has M entries and `b` has N
entries, the worst-case (no duplicates) cost is:

    sum_{i=0}^{N-1} (M + i) = N*M + N*(N-1)/2 = O(M*N + N²)

`kex_names_cat()` is called from:
- `kex_assemble_names()` (called during algorithm list assembly at connection setup)
- Various proposal-building paths

In a post-quantum migration scenario where algorithm lists are long (e.g., PQ
KEX algorithms added via `+` prefix in config), this is an O(N²) cost on
every connection.

## Complexity Before Fix
O(M×N + N²) where M = len(a), N = len(b).

## Fix

Pre-index `a` into a hash set, then iterate `b` with O(1) lookups:

```c
--- a/kex-names.c
+++ b/kex-names.c
@@ kex_names_cat
     strlcpy(ret, a, len);
-    for ((p = strsep(&cp, ",")); p && *p != '\0'; (p = strsep(&cp, ","))) {
-        if (kex_has_any_alg(ret, p))
-            continue; /* Algorithm already present */
+    /* Build a seen-set from a's tokens — O(M) */
+    /* (small stack hash table, 256 slots, sufficient for < 128 algs) */
+    const char *seen[256] = {0};
+    size_t smask = 255;
+    char *scan = xstrdup(a);
+    char *scp = scan, *sp;
+    for ((sp = strsep(&scp, ",")); sp && *sp; (sp = strsep(&scp, ","))) {
+        size_t h = djb2(sp) & smask;
+        for (size_t i = 0; i < smask+1; i++) {
+            size_t s = (h + i) & smask;
+            if (!seen[s]) { seen[s] = sp; break; }
+        }
+    }
+    for ((p = strsep(&cp, ",")); p && *p != '\0'; (p = strsep(&cp, ","))) {
+        /* O(1) hash set lookup instead of O(M+i) match_list scan */
+        size_t h = djb2(p) & smask, found = 0;
+        for (size_t i = 0; i < smask+1; i++) {
+            size_t s = (h + i) & smask;
+            if (!seen[s]) break;
+            if (strcmp(seen[s], p) == 0) { found = 1; break; }
+        }
+        if (found) continue;
+        /* Mark new entry in set */
+        size_t h2 = djb2(p) & smask;
+        for (size_t i = 0; i < smask+1; i++) {
+            size_t s = (h2 + i) & smask;
+            if (!seen[s]) { seen[s] = p; break; }
+        }
         strlcat(ret, ",", len);
         strlcat(ret, p, len);
     }
+    free(scan);
```

## Complexity After Fix
O(M + N) expected.

## Notes
- The two dedup defects (openssh-0001, openssh-0002) share the same root
  cause: `kex_has_any_alg()` / `match_list()` used as a "contains" check
  inside a growing-accumulator loop.
- Both sites should be fixed together. A shared `kex_alg_set_t` helper
  (init-from-string, O(1) contains, O(1) add) would eliminate both at once.
