{"id":"GHSA-c8j7-8cv4-2xmq","summary":"Mistune plugins/formatting: quadratic-time parsing on long runs of `~~x~~`, `==x==`, and `^^x^^` markers (strikethrough / mark / insert)","details":"## Summary\n\n**Type:** Algorithmic-complexity denial of service. A run of N closed pairs `~~x~~~~x~~...` (or the analogous `==x==` for `mark`, `^^x^^` for `insert`) causes O(N²) work in the formatting parser. With the `strikethrough`, `mark`, or `insert` plugin enabled, an 8 KB input pegs the CPU for ~4 seconds; 16 KB → ~17 seconds. \n**File:** `src/mistune/plugins/formatting.py`, lines 13-15 (the `_STRIKE_END` / `_MARK_END` / `_INSERT_END` patterns and their per-position scan).\n**Root cause:** for each opening `~~`/`==`/`^^` the parser scans forward for the matching close pattern. The scan itself uses a bounded regex, but the parser tries the close-scan at every potential start position. For input shaped like `~~x~~` repeated N times, every `~~` is examined as a possible start, each scan covers up to the end of input. Total work is O(N²). Default config without these plugins handles the same input in linear time (4 ms for 4000 reps), confirming the cost is in the formatting plugin's per-marker scan, not in core parsing.\n\n## Affected Code\n\n**File:** `src/mistune/plugins/formatting.py`, lines 12-16.\n\n```python\n_STRIKE_END = re.compile(r\"(?:\" + PREVENT_BACKSLASH + r\"\\\\~|[^\\s~])~~(?!~)\")\n_MARK_END = re.compile(r\"(?:\" + PREVENT_BACKSLASH + r\"\\\\=|[^\\s=])==(?!=)\")\n_INSERT_END = re.compile(r\"(?:\" + PREVENT_BACKSLASH + r\"\\\\\\^|[^\\s^])\\^\\^(?!\\^)\")\n# Each pattern is scanned forward from every start position fired by the\n# corresponding inline rule. The end-pattern itself is bounded; the cost\n# comes from the surrounding parser invoking the scan at every '~~' / '==' / '^^'\n# token in the input, giving N starts × O(N) per scan = O(N^2) total.\n```\n\n**Why it's wrong:** the same algorithmic-complexity flaw class as `[` / `[a` parsing in core: a per-token retry loop without memoisation of failed positions. Each formatting marker is tried as both a potential start and as a continuation. A linear-pass delimiter-stack algorithm (matching how `commonmark-py` and `markdown-it-py` handle emphasis) would do this work in O(N) total. The bounded regex on each individual scan does not bound the parser-level repetition.\n\n## Exploit Chain\n\n1. Application uses mistune to render user-supplied markdown and has any of the formatting plugins enabled (`plugins=['strikethrough']`, `['mark']`, `['insert']`, or any superset). These plugins are commonly enabled because GitHub-flavoured-Markdown compatibility requires `~~strikethrough~~` and many editors emit `==highlighting==` and `^^underline^^` shortcuts.\n2. Attacker submits an 8 KB markdown payload of the form `~~x~~~~x~~~~x~~...` (40 000 characters of `~~x~~` repeated 8000 times, or the analogous shape with `==` / `^^`).\n3. Server calls `mistune.create_markdown(plugins=['strikethrough'])(payload)`. CPU pegs for ~4 seconds; 16 KB → ~17 seconds; 32 KB → ~70 seconds. Pure CPU cost, no significant memory growth.\n4. Repeating the request floods the worker pool. On a single-thread WSGI handler this is one request per outage; on a thread pool, a small number of concurrent attackers exhausts capacity.\n\n## Security Impact\n\n**Severity:** sec-high. Network-reachable, no authentication, predictable scaling, single-payload primitive. Only requires a user-supplied markdown sink and a formatting plugin enabled — both are common.\n**Attacker capability:** small input → large CPU. Doubling input size quadruples CPU time. Sustained requests deny service to other users.\n**Preconditions:** application uses mistune with any of `strikethrough`, `mark`, or `insert` plugins enabled. Default config does NOT enable these (so the attack only fires against the substantial deployed population that turns them on for GFM/markdown-extra compatibility).\n**Differential:** PoC-verified against mistune@3.2.1:\n\n```python\nimport mistune, time\nmd = mistune.create_markdown(plugins=['strikethrough'])\nfor n in [500, 1000, 2000, 4000, 8000]:\n    s = '~~x~~' * n\n    t = time.time()\n    md(s)\n    print(f'  ~~x~~ * {n} ({len(s)}b): {(time.time() - t) * 1000:.0f}ms')\n\n# Output (Python 3.13, Linux, 2.5GHz CPU):\n#   ~~x~~ *  500  (2500b):    19ms\n#   ~~x~~ * 1000  (5000b):    71ms\n#   ~~x~~ * 2000 (10000b):   272ms\n#   ~~x~~ * 4000 (20000b):  1090ms\n#   ~~x~~ * 8000 (40000b):  4302ms\n\n# Identical scaling for `==x==` (mark) and `^^x^^` (insert):\nmd = mistune.create_markdown(plugins=['mark'])\nmd('==x==' * 4000)   # ~1100ms\nmd = mistune.create_markdown(plugins=['insert'])\nmd('^^x^^' * 4000)   # ~1080ms\n\n# Without the plugin, the same input parses in linear time:\nmd = mistune.create_markdown()  # no plugins\nmd('~~x~~' * 4000)               # 4ms (1000x faster)\n```\n\nThe patched build (with the suggested fix below — either a delimiter-stack rewrite or a hard cap on the number of unmatched markers tracked) keeps the time linear in N.\n\n## Suggested Fix\n\nThe minimal fix is to cap the number of simultaneously-tracked unmatched markers, treating extras as literal text. The proper fix is a single-pass delimiter-stack algorithm matching the CommonMark reference implementation. Surgical patch:\n\n```diff\n--- a/src/mistune/plugins/formatting.py\n+++ b/src/mistune/plugins/formatting.py\n@@ ... in the parse_strikethrough / parse_mark / parse_insert functions\n+    # Bound the number of open markers the parser will track concurrently.\n+    # Inputs with more than this many open ~~ / == / ^^ in flight are\n+    # almost certainly adversarial; CommonMark gives no semantics to\n+    # deeply nested unmatched markers.\n+    MAX_OPEN_MARKERS = 100\n+    if open_marker_count \u003e MAX_OPEN_MARKERS:\n+        # treat remaining markers as literal text, do not invoke the\n+        # forward-scan to find a close\n+        ...\n```\n\nA regression test should assert that `md('~~x~~' * 50_000)` completes in under 1 second. The same fix shape applies to `_MARK_END` and `_INSERT_END`.","aliases":["CVE-2026-59922","PYSEC-2026-2210"],"modified":"2026-07-20T21:46:40.410208712Z","published":"2026-07-20T21:34:37Z","database_specific":{"severity":"HIGH","github_reviewed":true,"github_reviewed_at":"2026-07-20T21:34:37Z","nvd_published_at":"2026-07-08T17:17:27Z","cwe_ids":["CWE-1333","CWE-407"]},"references":[{"type":"WEB","url":"https://github.com/lepture/mistune/security/advisories/GHSA-c8j7-8cv4-2xmq"},{"type":"ADVISORY","url":"https://nvd.nist.gov/vuln/detail/CVE-2026-59922"},{"type":"WEB","url":"https://github.com/lepture/mistune/commit/96d0f57f8fe9eeb06bb4cff521962a27d7c402e7"},{"type":"PACKAGE","url":"https://github.com/lepture/mistune"},{"type":"WEB","url":"https://github.com/lepture/mistune/releases/tag/v3.3.0"},{"type":"WEB","url":"https://github.com/pypa/advisory-database/tree/main/vulns/mistune/PYSEC-2026-2210.yaml"}],"affected":[{"package":{"name":"mistune","ecosystem":"PyPI","purl":"pkg:pypi/mistune"},"ranges":[{"type":"ECOSYSTEM","events":[{"introduced":"0"},{"fixed":"3.3.0"}]}],"versions":["0.1.0","0.2.0","0.3.0","0.3.1","0.4","0.4.1","0.5","0.5.1","0.6","0.7","0.7.1","0.7.2","0.7.3","0.7.4","0.8","0.8.1","0.8.2","0.8.3","0.8.4","2.0.0","2.0.0a1","2.0.0a2","2.0.0a3","2.0.0a4","2.0.0a5","2.0.0a6","2.0.0rc1","2.0.1","2.0.2","2.0.3","2.0.4","2.0.5","2.1.0","3.0.0","3.0.0a1","3.0.0a2","3.0.0a3","3.0.0rc1","3.0.0rc2","3.0.0rc3","3.0.0rc4","3.0.0rc5","3.0.1","3.0.2","3.1.0","3.1.1","3.1.2","3.1.3","3.1.4","3.2.0","3.2.1"],"database_specific":{"source":"https://github.com/github/advisory-database/blob/main/advisories/github-reviewed/2026/07/GHSA-c8j7-8cv4-2xmq/GHSA-c8j7-8cv4-2xmq.json"}}],"schema_version":"1.9.0","severity":[{"type":"CVSS_V3","score":"CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H"}]}