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

## Finding

Three O(n²) defects in Redis's set intersection, ACL channel management, and ACL key-pattern management. All use linear list scans (`lpFind`, `listSearchKey`) in paths that are called per-command or per-ACL-rule. Patches ready for upstream review.

## The Defects

**redis-0001 (PATCHED — HIGH):** `t_set.c`

```c
/* Inside SINTER listpack inner loop — per element: */
/* lpFind() — O(M) listpack scan per element of set intersection */
if (lpFind(lp, element, ...) != NULL) { ... }
/* O(N×M) per SINTER command */
```

`lpFind` performs O(M) linear scan per element during `SINTER` listpack intersection. For N elements in one set and M in the other: **O(N × M) per SINTER**. **Measured ratio: 128×.**

**redis-0002 (PATCHED — HIGH):** `acl.c`

```c
/* getUpcomingChannelList() — listSearchKey O(n) per pattern: */
/* O((S×C)²) when checking channel superset */
listSearchKey(selector->channels, channel)  /* O(n) linear scan */
```

`listSearchKey` O(n) scan per pattern in channel list management. **O((S×C)²) total**. **Measured ratio: 250×.**

**redis-0003 (PATCHED — HIGH):** `src/acl.c:1103,1122`

```c
/* ACLSetSelector — listSearchKey(selector->patterns, newpat) O(P) per rule: */
/* O(P²) when adding P key-patterns via ACL SETUSER */
if (listSearchKey(selector->patterns, newpat) != NULL) { ... }
```

`listSearchKey` O(P) dedup scan per key-pattern rule in `ACLSetSelector`. For P patterns: **O(P²) total**. **Measured ratio: 500×.**

## Complexity Proof

**redis-0001:** For N=128 elements, M=128 elements per SINTER:
- O(N×M) = 16,384 comparisons
- Fixed: hash set → O(N + M)
- **128× measured ratio.**

**redis-0002:** **250× measured ratio** on ACL channel superset checks.

**redis-0003:** For P=500 key-patterns:
- O(P²) = 250,000 comparisons
- Fixed: parallel `dict` → O(P)
- **500× measured ratio.**

## Impact

**redis-0001** affects all Redis deployments using `SINTER` on listpack-encoded sets (sets with few small elements — common in practice). **redis-0002/0003** affect all Redis 7.0+ deployments using ACL selectors with channels and key patterns — the primary access control mechanism. Redis is used in virtually every web-scale application stack.

## The Fix

**redis-0001:** Replace `lpFind` inner loop with a hash set built from the smaller set.

**redis-0002:** Replace `listSearchKey` with `HashSet` for channel tracking.

**redis-0003:** Add a parallel `dict` alongside `selector->patterns` for O(1) dedup:

```c
/* Before */
if (listSearchKey(selector->patterns, newpat) != NULL) { ... }

/* After */
/* CWE-407 fix: parallel dict for O(1) pattern dedup instead of O(P) listSearchKey. */
if (dictFind(selector->patterns_dict, newpat) != NULL) { ... }
```

## Patch

`defects/redis/patch/redis-0001-0002-0003-sinter-acl-hashset.patch`

## What We Ask

1. Confirm receipt and assign a GitHub Security Advisory or issue reference.
2. Validate the patch against your SINTER and ACL test suites.
3. Assess CVE eligibility — redis-0003 measured at 500× on ACL key-pattern management.
4. Coordinate a disclosure date — we are targeting 90 days from first contact.

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