# UNDF: (pending)
# bleach-MOADX-0001: BleachSanitizerFilter.sanitize_css — ReDoS O(2^N) on style attribute

## MOAD-0005 Candidate — The Hungry Regex

| Field | Value |
|-------|-------|
| ID | bleach-MOADX-0001 |
| Severity | HIGH |
| Ecosystem | bleach (Python HTML sanitizer) |
| File | `bleach/sanitizer.py` |
| Lines | 553–558 |
| Pattern | `^([-/:,#%.'"\sa-zA-Z0-9!]\|\w-\w\|'[\s\w]+'\s*\|"[\s\w]+"\|\([\d,%\.\s]+\))*$` |
| Trigger | `style="a-a-a-a-...-a-@"` — 71 chars causes ~12-second hang |
| Input vector | HTML `style` attribute value from user-submitted content |
| Input length limit | none |

## Defect

`bleach/sanitizer.py`, function `sanitize_css`, lines 553–558:

```python
parts = style.split(';')
gauntlet = re.compile(
    r"""^([-/:,#%.'"\sa-zA-Z0-9!]|\w-\w|'[\s\w]+'\s*|"[\s\w]+"|\([\d,%\.\s]+\))*$"""
)

for part in parts:
    if not gauntlet.match(part):
        return ''
```

The pattern `^(A|B|C|D|E)*$` where:
- `A` = `[-/:,#%.'"\sa-zA-Z0-9!]` — single char (broad set including `-`)
- `B` = `\w-\w` — three chars: word-hyphen-word

The alternation `A|B` creates exponential ambiguity: a string like `a-a-a-a-` can
be parsed as `[a][-][a][-]` (all via `A`) or `[a-a][-][a-]` (via `B` then `A`) or
countless other combinations. For each prefix position, the regex engine must
explore both interpretations.

When the input does NOT match (the trailing `$` fails), Python's NFA backtracks
through all O(2^N) parse trees, where N is the number of `a-` repetitions.

**Measurement (Python 3.x, bleach 3.0.0):**

| Input length | Time |
|---|---|
| 41 chars (`a-`×20 + `@`) | 0.011s |
| 51 chars (`a-`×25 + `@`) | 0.11s |
| 61 chars (`a-`×30 + `@`) | 0.97s |
| 71 chars (`a-`×35 + `@`) | 12.8s |

Growth factor: ~10× per 10 chars = O(2^N).

**Attack payload:**
```
style="a-a-a-a-a-a-a-a-a-a-a-a-a-a-a-a-a-a-a-a-a-a-a-a-a-a-a-a-a-a-a-a-a-a-a-@"
```
71-char style attribute causes a ~12-second Python thread hang.

Triggering characters for the non-matching terminal: `@`, `$`, `^`, `~`, `` ` ``,
`|`, `\`, `{`, `}`, `<`, `>` — all realistic HTML/CSS chars.

**Input path:** HTML user content → `bleach.clean()` → `BleachSanitizerFilter.sanitize_token()` →
`sanitize_css()` → `gauntlet.match(part)`.

## Fix

The ambiguity is between `A` matching `-` as a single character and `B` matching
`\w-\w` as a three-character sequence. Eliminating the single-char `-` from group
`A` and keeping it only in `B` removes the ambiguity, OR use atomic grouping
(Python 3.11+ via `re` module possessive `(?>...)`), OR replace with a proper
CSS tokenizer.

**Minimal fix — remove `-` from the single-char group:**
```python
gauntlet = re.compile(
    r"""^([-/:,#%.'"\sa-zA-Z0-9!]|(?<!\w)-(?!\w)|\w-\w|'[\s\w]+'\s*|"[\s\w]+"|\([\d,%\.\s]+\))*$"""
)
```

**Better fix — switch to a proper CSS tokenizer** (e.g., `tinycss2` or `cssutils`)
instead of regex-based validation. Bleach already depends on `html5lib`; a small
CSS tokenizer dependency is acceptable.

**Best fix — impose input length limit before matching:**
```python
MAX_STYLE_LEN = 1000
for part in parts[:100]:     # limit number of semicolon-separated parts
    part = part[:MAX_STYLE_LEN]
    if not gauntlet.match(part):
        return ''
```

The second pattern on line 561 (`^\s*([-\w]+\s*:[^:;]*(;\s*|$))*$`) does NOT
exhibit catastrophic backtracking — its character class `[^:;]*` is bounded by
the `:` and `;` delimiters.

## References

- bleach 3.0.0: `bleach/sanitizer.py` lines 540–575
- Pattern first introduced: commit history shows this predates 3.0.0
- Note: bleach has a history of ReDoS issues (CVE-2020-6802 linkifier, CVE-2021-23980 cleaner)
  but the CSS gauntlet pattern has not been separately reported.
