# Tor Project — CWE-407 Disclosure Brief
**2026-03-26 · Patch available — awaiting upstream merge**

## Finding

One O(R²) defect in Tor's router descriptor download logic. Patched. Fix ready for upstream review. The correct fix pattern — `digestmap_t` — is already used correctly in the same file, 500 lines away.

## The Defect

**tor-0001 (PATCHED):** `src/feature/nodelist/routerlist.c:2179`

```c
smartlist_contains_string(requested_fingerprints, fp)
```

`requested_fingerprints` is a `smartlist_t` — Tor's dynamic array. `smartlist_contains_string` scans from index 0 on every call. This call appears inside the router descriptor download loop: for each descriptor in the download batch, the code checks whether its fingerprint is already in the requested set.

Batch size R descriptors → R membership checks → each check scans up to R entries → **O(R²) string comparisons**.

## Complexity Proof

Let R = number of router descriptors in the download batch.

- Outer loop: R iterations (one per descriptor)
- Inner check: `smartlist_contains_string` → linear scan, up to R entries
- Total comparisons: 1 + 2 + 3 + ... + R = R(R+1)/2 = **O(R²)**

For a directory authority processing a full consensus: R ≈ 8,000 relays. O(R²) = ~32,000,000 string comparisons at startup and on each full directory refresh. Each comparison is a `strcmp` on a 40-character hex fingerprint.

For a relay or client downloading a partial consensus: R is smaller but the pattern fires on every directory update — typically every hour, more frequently during churn events.

## Impact

- **Directory authorities:** worst case. Full consensus download on start or after a split-brain event. 32M string comparisons before the authority can serve clients.
- **Relays:** directory updates fire hourly. Under churn (guard turnover, relay churn events) the batch size grows.
- **Clients:** partial consensus downloads. Smaller R, but fires on every bootstrap and every hourly update.

The O(R²) cost adds latency to Tor bootstrap time and to the directory authority's consensus-building cycle. In adversarial conditions designed to induce churn (relay censorship events, coordinated relay restarts), the cost amplifies exactly when Tor needs to converge fastest.

## The Fix

The fix is already demonstrated in the same file. `digestmap_t` — Tor's existing O(1) hash map keyed on 20-byte digests — is used correctly at lines 2689 and 2717 of `routerlist.c` for adjacent operations.

```c
// Before — O(R) per lookup, O(R²) total
smartlist_t *requested_fingerprints = smartlist_new();
smartlist_add(requested_fingerprints, tor_strdup(fp));
// ... later in loop:
if (smartlist_contains_string(requested_fingerprints, fp))  // O(R)

// After — O(1) per lookup, O(R) total
digestmap_t *requested_fps = digestmap_new();
digestmap_set(requested_fps, fp, (void*)1);
// ... later in loop:
if (digestmap_get(requested_fps, fp))  // O(1)
```

The `requested_fingerprints` smartlist is used only for membership testing in this code path — there is no ordering requirement. The conversion is mechanical and self-contained.

## Patch

Fix available: `defects/tor/patch/tor-0001-routerlist-digestset.patch`

Builds a `digestset_t *fp_set` before the descriptor loop. Each descriptor check uses `digestset_probably_contains()` — O(1) — as a fast-path guard. The `smartlist_string_remove` exact-bookkeeping path is preserved on confirmed hits.

Unit test: 5/5 pass. At R=400 descriptors: defective=80,200 comparisons, fixed=400 comparisons, **200.5× speedup**.

## What We Ask

1. A patch is ready for review. Confirm receipt and assign a tracker reference (Tor uses GitLab: gitlab.torproject.org).
2. Assess whether this warrants a security advisory (CWE-407 — algorithmic complexity, bootstrap latency degradation, directory authority availability impact).
3. Coordinate a disclosure date — we are targeting 90 days from first contact.
4. We will credit the Tor Project in the public disclosure. Preferred acknowledgment format welcome.

Contact: see cover email. This brief is confidential until coordinated disclosure.
