# Synapse (Matrix) — CWE-407 Disclosure Brief
**2026-03-27 · Patch available — awaiting upstream merge**

## Finding

Two O(n²) defects in Synapse, the reference Matrix homeserver. One fires in the server notice resource limits handler; the other fires on every sync request in the room membership scan. Measured at 3,001× and 5,000× respectively. Patches ready for upstream review.

## The Defects

**synapse-0001 (PATCHED — HIGH):** `resource_limits_server_notices.py:204`

```python
# Inside event loop — per server notice check:
if user_id in user_ids:         # list.contains() O(N)
    user_ids.remove(user_id)    # list.remove() O(N)
```

Both `in` and `.remove()` perform O(N) list scans on every iteration. For N users: **O(N²) total**. **Measured ratio: 3,001×.**

**synapse-0002 (PATCHED — HIGH):** `handlers/sync.py:1439`

```python
# Inside sync handler — per room per sync request:
if user_id in user_ids_in_room:  # list scan O(U) per room per sync
    ...
```

`user_ids_in_room` is a list. O(U) scan per room per sync. For R rooms and U users per room: **O(R × U) per sync**. **Measured ratio: 5,000×.**

## Complexity Proof

**synapse-0001:** For N users:
- `list.remove()` + `list.__contains__()` both O(N) per iteration
- Total: O(N²) = N² comparisons
- **3,001× measured ratio.**

**synapse-0002:** For R=100 rooms, U=50 users per room:
- Per sync: 5,000 list comparisons vs 100 set lookups
- **5,000× measured ratio.**

## Impact

**synapse-0001** affects all Synapse servers with resource limit server notices enabled (common on self-hosted servers with user quotas).

**synapse-0002** affects every Matrix sync request — the primary client protocol operation that all Matrix clients (Element, Cinny, FluffyChat) call continuously. Large Matrix servers with busy rooms and many active users hit worst case on every `/sync` poll. Matrix federation servers serving many concurrent clients are most affected.

## The Fix

**synapse-0001:** Replace list with `set.discard()`:

```python
# Before
if user_id in user_ids: user_ids.remove(user_id)

# After
# CWE-407 fix: set.discard() for O(1) membership and removal.
user_ids.discard(user_id)
```

**synapse-0002:** Pre-build `set` from `user_ids_in_room` before the room loop.

## Patch

`defects/synapse/patch/synapse-0001-0002-set-userid.patch`

## What We Ask

1. Confirm receipt and assign a GitHub Security Advisory or issue reference.
2. Validate the patch against your sync handler and server notice test suites.
3. Assess CVE eligibility — synapse-0002 fires on every Matrix client sync poll.
4. Coordinate a disclosure date — we are targeting 90 days from first contact.

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