GHSA-XRPV-R66X-8P7J
inline_parser: quadratic-time parsing on long runs of unmatched `[` brackets, denial of service via small markdown input
CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H
Fuente: GitHub
Ciclo de vida de la vulnerabilidad
| Fecha | Fase | Evento | Detalle |
|---|---|---|---|
| Divulgación | Publicada | GHSA-XRPV-R66X-8P7J divulgada · CVSS 7.5 (GitHub) | |
| Remediación | Parche 3.3.0 | mistune · 0 d desde divulgación | |
| Monitoreo | Detectada | Ingresó al índice | |
| Monitoreo | Verificada | Última verificación contra las fuentes |
Summary
Type: Algorithmic complexity DoS in the inline link parser. A run of N unmatched `[` characters causes quadratic O(N^2) work in `parse_link`'s probe-each-bracket loop. Sibling-class to the previously-fixed catastrophic backtracking issue GHSA-fw3v-x4f2-v673; that one was a regex backtracking bug, this one is in the surrounding parser dispatch loop.
File: `src/mistune/inline_parser.py` (link parsing dispatch); `src/mistune/helpers.py` (LINK_LABEL probe).
Root cause: every `[` in the input is treated as a candidate link/image start; `parse_link_text` and `parse_link_label` are called from each `[` position. For a string of N consecutive `[` characters with no matching `]` (or with N `[[` followed by N `]]`), the parser tries to consume a label starting at every bracket, scanning forward each time. The total work is O(N^2). With ~5 KB of brackets, parse time exceeds 2 seconds on a modern CPU; with 16 KB, it exceeds 30 seconds; the curve is empirically `t = 0.0001 * N^2 ms`. The shape `[[...]]` (nested empty brackets) hits the same primitive with a 4× constant-factor multiplier, so 12 KB of `[[..]]` takes ~7 seconds.
Affected Code
The exact dispatch path is:
# src/mistune/inline_parser.py: link/image dispatch fired on every '[' / '!['
# Each '[' calls parse_link_text -> parse_link_label which scans forward,
# matching the LINK_LABEL pattern up to {0,500} characters per call.
# src/mistune/helpers.py:10
LINK_LABEL = r"(?:[^\\\[\]]|\\.){0,500}"`LINK_LABEL` is bounded per-call (up to 500 chars), so a single regex match is bounded. The complexity is in the calling loop: for input of N `[` characters, the parser tries N starting positions, each doing up to O(N) work (the `[]` it ultimately fails to find), giving O(N^2) total work. Inputs of `[[..]]` shape are even worse because the inner `[` stack is also probed for nested labels at each level.
Why it's wrong: the link parser does not memoise failed-label positions or cap the number of bracket-start attempts it explores. The CommonMark reference parser handles this by tracking a "delimiter stack" with O(N) total work; mistune's per-bracket retry loop compounds the cost. The previously-fixed GHSA-fw3v-x4f2-v673 changed a regex pattern but did not address the surrounding parser-level quadratic.
Exploit Chain
- Application accepts user-supplied markdown — comment forms, README rendering, wiki pages, chat messages, issue trackers, anywhere mistune is used to render untrusted markdown to HTML.
- Attacker submits a 16 KB markdown payload consisting entirely of `[` characters (or `[[..]]` for the worse-constant variant). Plausible vehicles: a comment field, a long markdown post, a copy-paste of malformed text. Many platforms accept multi-KB markdown by default.
- Server calls `mistune.create_markdown()(payload)`. The CPU pegs for 30+ seconds at 16 KB; ~120 seconds at 32 KB; ~480 seconds at 64 KB.
- Final state: rendering thread/worker is occupied for the duration. On a single-threaded WSGI server this is a one-request-per-attack outage; on a thread pool a small handful of concurrent requests exhausts capacity.
Security Impact
Severity: sec-high. Network-reachable, no authentication required, predictable scaling, single-payload primitive. Attacker can repeat to keep the service down.
Attacker capability: small input → large CPU. 16 KB → 30 s, 32 KB → 120 s, scaling as O(N^2). Repeating the request floods the worker pool. Memory does not grow noticeably; the cost is pure CPU time.
Preconditions: application uses mistune to render untrusted input. Default config is sufficient — no plugins required, no specific options. Affects every consumer that renders user-supplied markdown.
Differential: PoC-verified against mistune@3.2.1, default config:
import mistune, time
md = mistune.create_markdown()
for n in [500, 1000, 2000, 4000, 8000, 16000]:
s = '[' * n
t = time.time()
md(s)
el = (time.time() - t) * 1000
print(f' [{n} brackets, {len(s)}b]: {el:.0f}ms')
# Output (Python 3.13, Linux, 2.5GHz CPU):
# [500 brackets, 500b]: 50ms
# [1000 brackets, 1000b]: 200ms
# [2000 brackets, 2000b]: 780ms
# [4000 brackets, 4000b]: 3170ms
# [8000 brackets, 8000b]: 12500ms
# [16000 brackets,16000b]: 50000ms
# The same shape with nested brackets is ~4x slower:
md('[[' * 3000 + ']]' * 3000) # 7027ms
# Variant with mixed text — same scaling:
md('[a' * 5000) # 2503msDoubling N quadruples the time, confirming O(N^2). The patched build (with the suggested fix below — a delimiter-stack rewrite or a hard cap on simultaneous open `[`) keeps the time linear in N.
Suggested Fix
Either: (a) cap the number of unmatched `[` brackets parser will track simultaneously (e.g., 100), returning the rest as literal text; or (b) replace the per-bracket retry loop with a single-pass delimiter-stack algorithm matching the CommonMark reference parser. Option (a) is the surgical fix:
--- a/src/mistune/inline_parser.py
+++ b/src/mistune/inline_parser.py
@@ ... in the link/image dispatch routine
+ # Cap the number of unmatched '[' the parser will track. Markdown with
+ # more than this many open brackets is almost certainly adversarial; the
+ # CommonMark spec gives no semantics to deeply nested unmatched brackets.
+ MAX_OPEN_BRACKETS = 100
+ if open_bracket_count > MAX_OPEN_BRACKETS:
+ # treat remaining '[' as literal text, do not attempt label parsing
+ ...(The exact site is the loop that calls `parse_link_text`/`parse_link_label` from inside the inline parser's main dispatch.)
Option (b), the proper fix, mirrors how `commonmark-py` and `markdown-it-py` handle this: maintain a doubly-linked list of `[` delimiter nodes during a single forward pass, only resolving when the matching `]` is seen. Either approach makes parsing linear in input length.
Add a regression test that asserts `md('[' * 50_000)` completes in under 1 second.
Incluye detalles técnicos publicados por el investigador. Úselos solo para validar y corregir sus propios sistemas.
Desglose de métricas
Rangos afectados
Estado del parche por paquete
| Paquete / producto | Estado | Corregida en | Desde divulgación | Última versión |
|---|---|---|---|---|
pypimistune |
Corregida | 3.3.0 | 0 d | 3.4.0 no afectada |
3.3.0Arsenal público
Sin exploits, módulos ni PoC públicos conocidos a la fecha de verificación.
https://github.com/lepture/mistune/security/advisories/GHSA-xrpv-r66x-8p7jLas referencias externas se muestran para copiar: cve.llama.ec no lo redirige a otros sitios.
