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

-- 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

-- 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

-- 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:

-- 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

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

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

2.8 KiB Raw Permalink Blame History Unescape Escape