llamaCVEVulnerability Intelligence
/
Advisory · GitHub · PyPI · mistune

GHSA-XRPV-R66X-8P7J

inline_parser: quadratic-time parsing on long runs of unmatched `[` brackets, denial of service via small markdown input

Parche disponible
Descargar PNG JSON
CVSS 3.1
7.5
Alta
CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H Fuente: GitHub
ExplotaciónSin evidenciaNo figura en CISA KEV
Exploits públicos0Ninguno conocido
Parche1 versiónPrimer parche el mismo día de la divulgación
Exposición151 dDesde la divulgación, 21 jun 2026, 8:25 a. m.
Detección150 dDesde la divulgación hasta su ingreso al índice
Timeline

Ciclo de vida de la vulnerabilidad

Hoy
Divulgación
Publicada
Explotación
Remediación
Parche 3.3.0
Monitoreo
Detectada +1
21 jun 26
19 nov 26
21 jun 26
29 jul 26
5 sept 26
12 oct 26
19 nov 26
FechaFaseEventoDetalle
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
Resumen
Descripción del advisory
Texto original · GitHub · en inglés

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

  1. 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.
  2. 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.
  3. 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.
  4. 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)                  # 2503ms

Doubling 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.

Vector CVSS 3.1

Desglose de métricas

Opción resaltada = valor del vector · izquierda = peor caso · GitHub
Vector de ataqueAV:N
RedAdyacenteLocalFísica
ComplejidadAC:L
BajaAlta
PrivilegiosPR:N
NingunoBajosAltos
InteracciónUI:N
NingunaRequerida
AlcanceS:U
CambiadoSin cambio
ConfidencialidadC:N
AltoBajoNinguno
IntegridadI:N
AltoBajoNinguno
DisponibilidadA:H
AltoBajoNinguno
Versiones

Rangos afectados

Afectada Corregida Última
mistune≤ 3.2.1
3.2.1
3.4.0
Remediación

Estado del parche por paquete

Paquete / productoEstadoCorregida enDesde divulgaciónÚltima versión
pypimistune
Corregida 3.3.0 0 d 3.4.0 no afectada
Versiones corregidas3.3.0
Explotación

Arsenal público

Sin exploits, módulos ni PoC públicos conocidos a la fecha de verificación.

Referencias
Advisoryhttps://github.com/lepture/mistune/security/advisories/GHSA-xrpv-r66x-8p7j

Las referencias externas se muestran para copiar: cve.llama.ec no lo redirige a otros sitios.