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

```c
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)

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