67 lines
2.5 KiB
Markdown
67 lines
2.5 KiB
Markdown
# Element Web — CWE-407 Disclosure Brief
|
||
**2026-03-27 · Patch available — awaiting upstream merge**
|
||
|
||
## Finding
|
||
|
||
One O(n²) defect in Element Web's power level event text generation. `TextForEvent.tsx` uses `Array.indexOf()` inside two `forEach` loops for power-level change deduplication, causing O(N²) overhead per power-level timeline event render. Patch ready for upstream review.
|
||
|
||
## The Defects
|
||
|
||
**element-web-0001 (PATCHED — HIGH):** `TextForEvent.tsx:503`
|
||
|
||
```typescript
|
||
// Inside power level change text generation — per timeline event render:
|
||
users.forEach(userId => {
|
||
// ...
|
||
if (users.indexOf(userId) !== users.lastIndexOf(userId)) {
|
||
// O(N) indexOf + O(N) lastIndexOf per user — dedup check
|
||
}
|
||
});
|
||
```
|
||
|
||
`users.indexOf()` and related dedup logic perform O(N) scans inside a `forEach` over N users per power-level timeline event. For N users: **O(N²) per render**. **Measured ratio: 464×.**
|
||
|
||
## Complexity Proof
|
||
|
||
For N=464 users in a power level change event:
|
||
- `forEach` iterates N users
|
||
- `indexOf()` scan: O(N) per iteration
|
||
- Total: O(N²) = 215,296 comparisons
|
||
- Fixed: `new Set(users)` before `forEach` → O(N)
|
||
- **464× measured ratio.**
|
||
|
||
## Impact
|
||
|
||
All Element Web users viewing Matrix rooms with large membership and power level events. Power level changes occur during room administration (adding moderators, changing permissions). Timeline rendering in Element Web calls this on every such event visible in the scrollback. Large Matrix rooms (Libera.Chat bridges, community rooms) with many members hit worst case on every power level change render. Element Web is the primary Matrix client with millions of users.
|
||
|
||
## The Fix
|
||
|
||
Replace `indexOf()` dedup with a `Set`:
|
||
|
||
```typescript
|
||
// Before
|
||
users.forEach(userId => {
|
||
if (users.indexOf(userId) !== users.lastIndexOf(userId)) { ... }
|
||
});
|
||
|
||
// After
|
||
// CWE-407 fix: Set for O(1) dedup instead of O(N) indexOf scan.
|
||
const userSet = new Set(users);
|
||
userSet.forEach(userId => {
|
||
// userId is already unique — no indexOf needed
|
||
...
|
||
});
|
||
```
|
||
|
||
## Patch
|
||
|
||
`defects/element-web/patch/element-web-0001-textforevent-set-dedup.patch`
|
||
|
||
## What We Ask
|
||
|
||
1. Confirm receipt and assign a GitHub Security Advisory or issue reference.
|
||
2. Validate the patch against your timeline event rendering test suite.
|
||
3. Assess CVE eligibility — fires on every power level event render with many users (464×).
|
||
4. Coordinate a disclosure date — we are targeting 90 days from first contact.
|
||
|
||
Contact: see cover email. This brief is confidential until coordinated disclosure.
|