GHSA-G663-53R6-CJV5
Quadratic-time denial of service in pymdownx caret, tilde, and mark delimiter processing
Texto original en inglés · Ver en español
CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:L
Fuente: GitHub
Ciclo de vida de la vulnerabilidad
| Fecha | Fase | Evento | Detalle |
|---|---|---|---|
| Remediación | Parche 12.1.0 | pymdown-extensions · -45 d desde divulgación | |
| Divulgación | Publicada | GHSA-G663-53R6-CJV5 divulgada · CVSS 5.3 (GitHub) | |
| Monitoreo | Detectada | Ingresó al índice | |
| Monitoreo | Verificada | Última verificación contra las fuentes |
Summary
The rewritten delimiter engine in pymdown-extensions (introduced in the 12.0 release) processes emphasis-style delimiters with quadratic time complexity when given a long, uninterrupted run of a single delimiter character. Any service that renders untrusted Markdown with the `pymdownx.caret`, `pymdownx.tilde`, or `pymdownx.mark` extensions enabled can be driven into O(n^2) CPU consumption by an unauthenticated attacker who submits a body such as `"^" * n`, `"~" * n`, or `"=" * n`. No authentication, special configuration, or user interaction is required; a single request of tens of kilobytes pins a render worker for tens of seconds, and larger inputs scale quadratically.
Root Cause
The 12.0 rewrite replaced the old per-extension emphasis regexes with a hand-rolled scanner in `DelimiterProcessor`. Python-Markdown's inline treeprocessor dispatches `DelimiterProcessor.handleMatch` once per delimiter position. For a contiguous run of the same delimiter, no pair is ever formed, so `handleMatch` returns and advances a single character at a time, being re-entered once for each of the n positions. On every invocation it calls `get_match`, which runs a boundary regex (built by `Delimiter._build_patterns`) that greedily matches the entire remaining contiguous run, costing O(n minus start). Summing this whole-run re-scan over all n positions yields O(n^2) work. The engine never advances past an already-scanned run, so the same characters are re-matched again and again. For mixed or paired delimiter inputs the `search` method (called from the pairing loop) is a second re-scanning sink with the same growth. There is no input-size or complexity cap anywhere in the render path.
pymdownx/delimiterprocessor.py:
Delimiter._build_patterns (lines 116-222) builds etoken{1,}/{2}/{3,} boundary regexes that match the whole run
DelimiterProcessor.handleMatch (line 541) dispatched once per delimiter position; advances one char and re-enters
DelimiterProcessor.get_match (lines 489-496) runs d.boundary.match(data, start) over the entire remaining run
DelimiterProcessor.search (lines 498-509) co-sink for mixed/paired inputs; re-scans the remaining run per iterationImpact
An unauthenticated remote attacker who can submit Markdown to a service that renders with caret, tilde, or mark enabled (common in Material for MkDocs sites and in comment, wiki, or chat renderers) causes the rendering thread to consume CPU quadratically in the input length. This is a denial-of-service primitive: one render worker is pinned for the duration. Measured on Python 3.11 with markdown 3.10.2, a caret run scales cleanly as O(n^2) (approximately 4x time per doubling of input). A body of tens of kilobytes ties a worker up for tens of seconds; extrapolating the measured growth, a body on the order of a megabyte would pin a single worker for roughly hours. In multi-worker deployments the affected worker recovers when the request is killed, so the demonstrated impact is availability degradation of one worker per malicious request (plausibly a full outage in single-worker or synchronous-render deployments, though that stronger consequence was not the demonstrated baseline).
Proof of Concept
Dependencies: python 3.11, markdown 3.10.2, pymdown-extensions 12.0.1 (or 12.0).
Run against the published artifact; no configuration beyond enabling the extension.import time
import markdown
for n in (2000, 4000, 8000, 16000, 32000):
body = "^" * n
md = markdown.Markdown(extensions=["pymdownx.caret"])
start = time.time()
md.convert(body)
print(f"n={n} bytes={len(body)} time={time.time() - start:.3f}s")n=2000 bytes=2000 time=0.034s
n=4000 bytes=4000 time=0.124s
n=8000 bytes=8000 time=0.476s
n=16000 bytes=16000 time=1.880s
n=32000 bytes=32000 time=7.403sTime grows by roughly 4x for each doubling of input, confirming quadratic complexity. The same growth reproduces with `pymdownx.tilde` (`"~" * n`) and `pymdownx.mark` (`"=" * n`). Breaking the run with spaces (`"^ " * n`) collapses the cost to linear, confirming the driver is the attacker-supplied contiguous run and not general Markdown parsing. Stock python-markdown on a comparable emphasis run stays linear and is thousands of times cheaper.
Attack Chain
- Exposure: An unauthenticated attacker reaches a shipped endpoint that renders user-supplied Markdown with caret, tilde, or mark enabled, via the public `markdown.Markdown.convert()` API.
- Control: The attacker fully controls the request body and supplies a long uninterrupted run of the delimiter character (for example `"^" * n`). Nothing in the parser normalizes or shortens the run.
- Path: Python-Markdown's inline treeprocessor invokes `DelimiterProcessor.handleMatch` once per delimiter position; each invocation calls `get_match`, whose boundary regex matches the entire remaining run.
- Guard: None. There is no input-size cap, no complexity cap, and no mechanism that advances the scanner past an already-processed run.
- Primitive: A regex whole-run match executed O(n) times over O(n)-length data, producing O(n^2) CPU on the render thread.
- Result: The render worker is pinned proportionally to the square of the input length, denying service to other requests handled by that worker.
Bypass Evidence
No guard or prior fix protects this path. The seed advisory GHSA-gm37-52c6-37mw (CVE-2026-67422) addressed exponential-backtracking regexes in the pre-12.0 emphasis implementation and was fixed in 11.0.1; those regexes (`SUP2`, `SUB2`, `SMART_UNDER_EM2`) no longer exist and seed-style inputs are now linear. This quadratic lives in entirely new code: `pymdownx/delimiterprocessor.py` was first added in the 12.0 rewrite and is absent at 11.0. The following disproof attempts were made and each failed to invalidate the finding:
- "It is inherent Markdown cost": refuted. Stock python-markdown on a comparable run is linear and thousands of times cheaper; only the pymdownx delimiter scanner is quadratic.
- "There is a default input cap": refuted. A 64 KB pure-delimiter body is processed to completion; no length or complexity check exists in the convert path.
- "Only the unreleased development head is affected": refuted. The quadratic reproduces identically against git worktrees checked out at the published tags 12.0 and 12.0.1, and against the published 12.0.1 wheel whose `delimiterprocessor.py` is byte-identical to the 12.0.1 tag.
Affected Versions
- `Ecosystem: pip (PyPI)`
- `Package: pymdown-extensions`
- `Confirmed affected range: >= 12.0, <= 12.0.1`
- `Latest release checked: 12.0.1 (PyPI, uploaded 2026-09-15)`
- `Fix status: not fixed`
The quadratic scanner was introduced by the 12.0 delimiter rewrite; releases at or before 11.x use a different implementation and are not affected by this mechanism. The published 12.x line consists of {12.0, 12.0.1}, both vulnerable, and 12.0.1 is the current latest release (no 12.1 has been published). The vulnerable functions are unchanged across 12.0, 12.0.1, and the current development head, so no released fix exists; when a 12.1 release is published it will extend the affected range unless the scanner is corrected first.
Suggested Fix
Enforce that the delimiter scanner does not re-match characters it has already scanned: after a run is examined at a position, advance past the full length of that run instead of returning and being re-dispatched one character at a time, or bound the per-position boundary match so the aggregate work is linear in the input. As defense in depth, applications rendering untrusted Markdown should impose a maximum input size before calling `convert()`; a cap of a few kilobytes blunts this vector, though it is a mitigation rather than a code fix.
Reported by zx (GitHub: @manus-pi).
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 |
|---|---|---|---|---|
pypipymdown-extensions |
Corregida | 12.1.0 | -45 d | 13.1.0 no afectada |
12.1.0Arsenal público
Sin exploits, módulos ni PoC públicos conocidos a la fecha de verificación.
https://github.com/facelessuser/pymdown-extensions/security/advisories/GHSA-g663-53r6-cjv5Las referencias externas se muestran para copiar: cve.llama.ec no lo redirige a otros sitios.
