russell@unturf.com
0a580b313d
Authors: russell@unturf.com · brackishbert@gmail.com · foxhop.net · TimeHexOn.com Patches, unit tests, benchmarks, whitepaper, and outreach briefs. Public domain — no copyright claimed. Use freely.
75 lines
4 KiB
Markdown
75 lines
4 KiB
Markdown
# 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.
|