UNDF: UNDF-2026-000000199

openbsd-0001 — `pf_osfp`: O(N²) validation scan in `pf_osfp_validate`

Status

PATCHED

Severity

MEDIUM (N=246 fingerprints in default pf.os; O(N²) = ~60K iterations per pfctl -F rules + pfctl -f pf.conf reload)

Location

sys/net/pf_osfp.c, function pf_osfp_validate() (~line 582)

Description

pf_osfp_validate is called after fingerprint loading (pf_osfp_add, via DIOCOSFPADD ioctl) to confirm every loaded fingerprint is uniquely reachable by pf_osfp_find.

SLIST_FOREACH(f, &pf_osfp_list, fp_next) {          // O(N) — outer loop
    memcpy(&find, f, sizeof(find));
    ...percolate fp_mss/fp_wsize...
    if (f != (f2 = pf_osfp_find(&find, 0))) {        // O(N) — inner linear scan
        ...log conflict...
        return (f);
    }
}

pf_osfp_find itself is a SLIST_FOREACH over pf_osfp_list (O(N) per call). With 246 entries in the default /etc/pf.os, validation performs 246 × 246 = 60,516 fingerprint comparisons on every ruleset reload.

The same pf_osfp_find is also called per-packet for OS fingerprinting (pf_osfp_fingerprint → pf_osfp_find): each new TCP SYN triggers an O(N=246) linear scan of pf_osfp_list. Under SYN flood conditions this becomes a sustained O(N) linear scan per packet.

Complexity

pf_osfp_validate: O(N²) — outer N × inner pf_osfp_find O(N)
pf_osfp_find (packet path): O(N) per TCP SYN
N = 246 (default pf.os); custom rulesets can add more

Fix

pf_osfp_validate

Replace the deferred pf_osfp_find re-scan with an O(1) check during insertion: pf_osfp_insert already has an XXX comment ("need to go semi tree based. can key on tcp options"). Index pf_osfp_list by fp_tcpopts using a hash table (RB_TREE or SLIST per bucket keyed on fp_tcpopts). Validation becomes O(N) — one hash lookup per entry.

pf_osfp_find (packet path)

Same fix: hash pf_osfp_list by fp_tcpopts (always the first discriminator checked). Expected bucket size shrinks from 246 to ~5–10. The XXX comment in pf_osfp_insert explicitly calls this out as needed.

Patch (conceptual — C)

/* In pf_osfp_insert: maintain a hash bucket SLIST per fp_tcpopts value */
/* Use a fixed-size array of SLIST_HEADs keyed by (fp_tcpopts % OSFP_BUCKETS) */
#define OSFP_BUCKETS 64
static SLIST_HEAD(pf_osfp_bucket, pf_os_fingerprint) pf_osfp_hash[OSFP_BUCKETS];

/* pf_osfp_find becomes:
 * 1. hash = fp_tcpopts % OSFP_BUCKETS
 * 2. SLIST_FOREACH only within pf_osfp_hash[hash]
 * Expected O(N/64) per lookup instead of O(N)
 */

/* pf_osfp_validate becomes O(N) since each lookup now hits a small bucket */

Patch file

See openbsd-0001-pf-osfp-validate-quadratic.patch

2.7 KiB Raw Permalink Blame History Unescape Escape