# UNDF: UNDF-2026-000000488
# openssh-0001: CWE-407 O(N²) dedup in kex_assemble_server_sig_algs via match_list inside loop

## Severity: MEDIUM

## Location
`kex.c` — `kex_assemble_server_sig_algs()`, lines ~276–284

Also called indirectly via `kex-names.c:kex_has_any_alg()` → `match.c:match_list()`

## Description

`kex_assemble_server_sig_algs()` builds the server's `server_sig_algs` string
by iterating over `allowed_algs` (a comma-separated list of N algorithm names)
and deduplicating against the accumulator string as it grows.

```c
for ((alg = strsep(&algs, ",")); alg != NULL && *alg != '\0';
    (alg = strsep(&algs, ","))) {
    if ((sigalg = sshkey_sigalg_by_name(alg)) == NULL)
        continue;
    if (!kex_has_any_alg(sigalg, sigalgs))          /* O(S) scan */
        continue;
    /* Don't add an algorithm twice. */
    if (ssh->kex->server_sig_algs != NULL &&
        kex_has_any_alg(sigalg, ssh->kex->server_sig_algs))  /* O(i) */
        continue;
    xextendf(&ssh->kex->server_sig_algs, ",", "%s", sigalg);
}
```

`kex_has_any_alg(sigalg, ssh->kex->server_sig_algs)` calls `match_list()`,
which splits the second argument on commas and scans every token with
`strcmp`. At iteration i, `server_sig_algs` contains i tokens, so the check
costs O(i). Over N iterations the total work is:

    0 + 1 + 2 + ... + (N-1) = O(N²)

For a server configured with N signature algorithms, every new SSH connection
triggers a rebuild of `server_sig_algs` during EXT_INFO negotiation.

OpenSSH ships with ~30 default signature algorithms. A compile-time or
runtime configuration with a long algorithm list amplifies the cost. The
function is called once per accepted connection (in `kex_compose_ext_info_server`),
making this an O(N²) cost proportional to configuration size, evaluated
per-connection.

## Complexity Before Fix
O(N²) where N = number of entries in `allowed_algs` (signature algorithm list).

## Fix

Collect results into a `HashSet<String>` equivalent (a small string set)
before building the output string. In C, a stack-allocated open-addressing
hash table over short algorithm names achieves O(1) lookup.

Alternatively, since the algorithm lists are short (< 64 entries), a single
pre-pass can build a sorted array of `sigalg` pointers from `allowed_algs`
filtered by `sigalgs`, then deduplicate in O(N log N) with bsearch.

```c
--- a/kex.c
+++ b/kex.c
@@ -264,6 +264,7 @@ kex_assemble_server_sig_algs(struct ssh *ssh, const char *allowed_algs)
     const char *sigalg;

     if ((sigalgs = sshkey_alg_list(0, 1, 1, ',')) == NULL)
         fatal_f("sshkey_alg_list failed");
     oalgs = algs = xstrdup(allowed_algs);
     free(ssh->kex->server_sig_algs);
     ssh->kex->server_sig_algs = NULL;
+    /* seen_set: small open-addressing hash set, avoids O(N²) dedup scan */
+    char *seen[128] = {0};  /* 128 slots, load ≤ 50% for N ≤ 64 algs */
+    size_t seen_mask = 127;
+    /* djb2 hash on null-terminated string */
+#define SEEN_HASH(s) ({ \
+    unsigned long _h = 5381; \
+    const unsigned char *_p = (const unsigned char*)(s); \
+    while (*_p) _h = ((_h << 5) + _h) ^ *_p++; \
+    (size_t)(_h & seen_mask); \
+})
     for ((alg = strsep(&algs, ",")); alg != NULL && *alg != '\0';
         (alg = strsep(&algs, ","))) {
         if ((sigalg = sshkey_sigalg_by_name(alg)) == NULL)
             continue;
         if (!kex_has_any_alg(sigalg, sigalgs))
             continue;
-        /* Don't add an algorithm twice. */
-        if (ssh->kex->server_sig_algs != NULL &&
-            kex_has_any_alg(sigalg, ssh->kex->server_sig_algs))
-            continue;
+        /* O(1) duplicate check via open-addressing hash set */
+        size_t _slot = SEEN_HASH(sigalg);
+        bool _dup = false;
+        for (size_t _i = 0; _i < seen_mask + 1; _i++) {
+            size_t _s = (_slot + _i) & seen_mask;
+            if (seen[_s] == NULL) { seen[_s] = (char*)sigalg; break; }
+            if (strcmp(seen[_s], sigalg) == 0) { _dup = true; break; }
+        }
+        if (_dup) continue;
         xextendf(&ssh->kex->server_sig_algs, ",", "%s", sigalg);
     }
```

## Complexity After Fix
O(N) expected — one pass over allowed_algs, O(1) hash-set lookup per entry.

## Notes
- `allowed_algs` is typically 20–35 algorithms in practice; the defect is
  low-severity at current scale but O(N²) is an architectural property that
  will worsen as algorithm lists grow (post-quantum additions, etc.).
- The same pattern appears in `kex_names_cat()` (see openssh-0002).
