# UNDF: UNDF-2026-000000544
# strongswan-0001: CWE-407 O(P²×T×A²) nested linear scans in proposal_select / select_algo

## Severity: HIGH

## Location
`src/libstrongswan/crypto/proposal/proposal.c`
- `proposal_select()` lines ~1424–1475 (outer P_c × P_s loop)
- `select_algo()` lines ~319–490 (inner A₁ × A₂ nested enumerator loop)

## Description

IKE SA negotiation selects a proposal from two linked lists:
- `configured` — the local IKE configuration list (P_c proposals)
- `supplied` — proposals received from the remote peer (P_s proposals)

### Level 1: O(P_c × P_s) in proposal_select

`proposal_select()` iterates every configured proposal against every supplied
proposal until a match is found:

```c
while (prefer_enum->enumerate(prefer_enum, &proposal))
{
    while (match_enum->enumerate(match_enum, &match))
    {
        selected = proposal->select(proposal, match, flags);  /* inner */
        if (selected) break;
    }
    if (selected) break;
}
```

This is O(P_c × P_s) in the worst case (no match until the end).

### Level 2: O(T × A₁ × A₂) in select_algos / select_algo

Each `proposal->select()` call reaches `select_algos()`, which iterates over
all T transform types and calls `select_algo()` per type. `select_algo()` has
a nested enumerator loop:

```c
e1 = create_enumerator(this, type);   /* A₁ algorithms from local proposal */
while (!found && e1->enumerate(e1, &alg1, &ks1))
{
    e2->destroy(e2);
    e2 = other->create_enumerator(other, type);  /* reset inner each outer step */
    while (e2->enumerate(e2, &alg2, &ks2))
    {
        if (alg1 == alg2 && ks1 == ks2)
        {
            found = TRUE;
            break;
        }
    }
}
```

Cost per transform type: O(A₁ × A₂).

### Combined cost

    O(P_c × P_s × T × A₁ × A₂)

In practice:
- An IKE config may have P_c = 10–30 proposals (e.g., supporting multiple
  cipher suites for interoperability with legacy and modern peers).
- A peer may send P_s = 10–30 proposals.
- T ≈ 4–7 transform types per proposal (encryption, integrity, PRF, DH, KE).
- A₁, A₂ ≈ 4–8 algorithms per type in each proposal.

Even at P=10, T=5, A=4: 10 × 10 × 5 × 4 × 4 = 8,000 comparisons per
IKE_SA_INIT message. At P=30, T=7, A=8: 30 × 30 × 7 × 8 × 8 = 403,200
comparisons per handshake.

An attacker sending IKE_SA_INIT with P_s = 100 crafted proposals (all
guaranteed not to match) forces:
    100 × P_c × T × A² comparisons per handshake

This is a pre-authentication denial-of-service amplifier.

## Complexity Before Fix
O(P_c × P_s × T × A₁ × A₂) per IKE handshake.

## Fix

### Fix for select_algo (inner loop)

Build a `hashtable_t` (already available in strongSwan as `hashtable_create`)
from the remote proposal's algorithms for the given transform type before the
outer loop. Lookup is then O(1) per outer step:

```c
--- a/src/libstrongswan/crypto/proposal/proposal.c
+++ b/src/libstrongswan/crypto/proposal/proposal.c
@@ select_algo
+    /* Index the "other" side's algorithms into a hashtable for O(1) lookup */
+    hashtable_t *alg_set = hashtable_create(hash_alg_ks, equals_alg_ks, 16);
+    uint32_t packed;
     e2 = other->create_enumerator(other, type);
+    while (e2->enumerate(e2, &alg2, &ks2))
+    {
+        packed = ((uint32_t)alg2 << 16) | ks2;
+        alg_set->put(alg_set, (void*)(uintptr_t)packed,
+                               (void*)(uintptr_t)packed);
+    }
+    e2->destroy(e2);

     e1 = create_enumerator(this, type);
     while (!found && e1->enumerate(e1, &alg1, &ks1))
     {
-        e2->destroy(e2);
-        e2 = other->create_enumerator(other, type);
-        while (e2->enumerate(e2, &alg2, &ks2))
-        {
-            if (alg1 == alg2 && ks1 == ks2)
-            {
-                found = TRUE;
-                break;
-            }
-        }
+        packed = ((uint32_t)alg1 << 16) | ks1;
+        if (alg_set->get(alg_set, (void*)(uintptr_t)packed))
+        {
+            *alg = alg1;
+            *ks = ks1;
+            found = TRUE;
+        }
     }
     e1->destroy(e1);
-    e2->destroy(e2);
+    alg_set->destroy(alg_set);
```

### Fix for proposal_select (outer loop)

Pre-index all supplied proposals' algorithm sets before the outer loop, so
each `proposal->select()` only costs O(T × A) not O(T × A²):

With the inner fix in place, `proposal_select()` becomes O(P_c × P_s × T × A)
which is already acceptable. For further improvement, index supplied proposals
by (protocol, first_encryption_alg) to skip non-matching proposals in O(1).

## Complexity After Fix
- `select_algo`: O(A₁ + A₂) per transform type (build set + linear scan)
- `proposal_select`: O(P_c × P_s × T × (A₁ + A₂))
- At P=30, T=7, A=8: 30 × 30 × 7 × 16 = 100,800 → ~4× improvement,
  but more critically, the A² exponent is eliminated, which dominates for
  proposals with many algorithms.

## Notes
- The `hashtable_t` type is already used in `select_algo` itself for KE
  dedup (the `kes` hashtable), so the infrastructure is present.
- A 32-bit packed key `(alg << 16 | key_size)` fits cleanly since both
  fields are `uint16_t` per the strongSwan source.
- This defect affects both IKEv1 and IKEv2 code paths; both call
  `proposal_select()` from their respective task implementations.
