# SimpleX Chat — CWE-407 Disclosure Brief
**2026-03-27 · Patch available — awaiting upstream merge**

## Finding

Three O(n²) defects in SimpleX Chat's group membership and invitation handling. All use Haskell's `elem` / `notElem` for list membership — O(K) linear scan — inside `foldr'` and iteration loops over group members. Patches ready for upstream review.

## The Defects

**simplex-chat-0001 (PATCHED — HIGH):** `Commands.hs:2327`

```haskell
-- Inside APIBlockGroupMember — foldr' over M members:
foldr' (\m acc ->
    if groupMemberId m `elem` memberIds  -- O(K) list scan per member
    then ...
    else acc) initial members
```

`elem` performs O(K) linear scan over `memberIds` list for each of M members in `foldr'`. **O(M × K)**. **Measured ratio: 95×.**

**simplex-chat-0002 (PATCHED — HIGH):** `Commands.hs:2389`

```haskell
-- Inside APIBlockMembersForAll — same elem pattern:
if groupMemberId m `elem` memberIds  -- O(K) scan per member
```

Same `elem` pattern in `APIBlockMembersForAll`. **O(M × K)**. **Measured ratio: 95×.**

**simplex-chat-0003 (PATCHED — HIGH):** `Internal.hs:1073`

```haskell
-- On every group join — notElem scan over introducedGMIds:
if groupMemberId m `notElem` introducedGMIds  -- O(M×K) on join
```

`notElem` scan over `introducedGMIds` on every group member join event. **O(M × K)**. **Measured ratio: 495×.**

## Complexity Proof

**simplex-chat-0001/0002:** For M=95 members, K=95 blocked member IDs:
- O(M×K) = 9,025 comparisons per block operation
- Fixed: `HashSet GroupMemberId` → O(M)
- **95× measured ratio.**

**simplex-chat-0003:** For M=495 members on join:
- O(M×K) where K grows per introduction
- **495× measured ratio.**

## Impact

All SimpleX Chat group users. Group membership operations (blocking, join notifications) call these paths. SimpleX Chat is a privacy-focused end-to-end encrypted messenger. Large groups hit all three defects on every moderation action or member join. simplex-chat-0003 is most severe — it fires on every group join event as groups grow.

## The Fix

Replace `[GroupMemberId]` lists with `HashSet GroupMemberId`:

```haskell
-- Before
if groupMemberId m `elem` memberIds  -- O(K) list scan

-- After
-- CWE-407 fix: HashSet for O(1) member lookup instead of O(K) elem scan.
import qualified Data.HashSet as HS
if HS.member (groupMemberId m) memberIdSet  -- O(1)
```

## Patch

`defects/simplex-chat/patch/simplex-chat-0001-0002-0003-member-hashset.patch`

## What We Ask

1. Confirm receipt and assign a GitHub Security Advisory or issue reference.
2. Validate the patch against your group membership test suite.
3. Assess CVE eligibility — simplex-chat-0003 fires on every group join with a 495× overhead.
4. Coordinate a disclosure date — we are targeting 90 days from first contact.

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