GHSA-QP42-R9J6-83G9
Quadratic-time DoS in _process_emphasis_delimiters index-fixup loop
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 |
|---|---|---|---|
| Remediación | Parche 3.3.4 | mistune · -89 d desde divulgación | |
| Divulgación | Publicada | GHSA-QP42-R9J6-83G9 divulgada · CVSS 7.5 (GitHub) | |
| Monitoreo | Detectada | Ingresó al índice | |
| Monitoreo | Verificada | Última verificación contra las fuentes |
Resolution
Fixed in Mistune 3.3.4. Upgrade to 3.3.4 or later.
- Affected versions: `>= 3.3.0, < 3.3.4`
- First patched version: `3.3.4`
- Fix: https://github.com/lepture/mistune/commit/b4dd3284e52ec741ed9a227db29ade9017828e90
The reported payload was reproduced against the 3.3.3 release tag and verified to scale approximately linearly against the 3.3.4 release tag.
Original report
The following report describes the issue before the fix.
## Summary
After inline tokenization, `_process_emphasis_delimiters` runs an index-fixup loop over the entire delimiter list on every emphasis match with `removed>0`. With O(n) matches this is O(n²). A small default-renderer document like `"*a_b" * N` triggers it with no plugins.
## Root Cause
`_process_emphasis_delimiters` (inline_parser.py:655) matches emphasis pairs and, on each match with `removed>0`, runs `for delimiter in delimiters:` (:725) over the whole delimiter list to fix stored indices. CommonMark's reference implementation uses a linked list (O(1) removal); the array rewrite reintroduced the cost. Line 725 executes ~n²/2 times.
## Impact
A single unauthenticated request pins a worker. Measured, default renderer, no plugins: `*a_b`*n -> 8KB->0.15s, 16KB->0.55s, 32KB->2.1s, 64KB->8.2s; `*a**b`*n worse (80KB->20.9s).
Proof of Concept
import mistune
md = mistune.create_markdown() # default, no plugins
md("*a_b" * 16000)## Attack Chain
1. Entry: rendered markdown -> `"*a_b" * N` (no plugins). Guard: none on input size. Bypass proof: no global cap.
2. Check: `max_emphasis_depth` at inline_parser.py:709 (`_emphasis_depth(children) >= max_depth`). Guard: a depth cap. Bypass proof: it caps produced-node depth, checked AFTER the fixup work; measured flat across depth 0..100 — it does not reduce match count.
3. Processing: each emphasis match with `removed>0` runs the line-725 fixup loop over all delimiters.
4. Sink: O(n) matches x O(n) loop -> O(n²) (measured line-725 count: 125,250 @ n=500 -> 500,500 @ n=1000 -> 2,001,000 @ n=2000).
5. Impact: 64KB -> ~8s worker stall.
## Bypass Evidence
- CVE-2026-59925 (`x`/`*x*` emphasis pairs, fixed 3.3.0) payloads are LINEAR on HEAD (2.1x per 2x) and hit line 725 zero / ~n times; the `*a_b` payload hits it ~n²/2 times (3.90x per 2x).
- `git log -S` / git archaeology: the fixup loop was only ever introduced by refactor `5de41fb`; NO DoS fix has touched it. `max_emphasis_depth` (`0938fb7`) is a depth cap, not a match-count bound.
## Affected Versions
`<= 3.3.3` (present on latest release tag v3.3.3 and HEAD).
## Suggested Fix
Replace the array + O(n) index-fixup with a linked-list delimiter stack (as in the CommonMark reference), giving O(1) removal and eliminating the per-match fixup scan.
---
Reported by zx (Jace) — GitHub: @manus-use
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.4 | -89 d | 3.4.0 no afectada |
3.3.4Arsenal 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-qp42-r9j6-83g9Las referencias externas se muestran para copiar: cve.llama.ec no lo redirige a otros sitios.
