java-topology/defects/strongswan/patch/strongswan-0001-proposal-select-nested-linear-scan.md

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:

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:

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:

--- 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.