CVE-2026-59922

Summary

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. File: src/mistune/plugins/formatting.py, lines 13-15 (the _STRIKE_END / _MARK_END / _INSERT_END patterns and their per-position scan). 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.

Affected Code

File: src/mistune/plugins/formatting.py, lines 12-16.

_STRIKE_END = re.compile(r"(?:" + PREVENT_BACKSLASH + r"\\~|[^\s~])~~(?!~)")
_MARK_END = re.compile(r"(?:" + PREVENT_BACKSLASH + r"\\=|[^\s=])==(?!=)")
_INSERT_END = re.compile(r"(?:" + PREVENT_BACKSLASH + r"\\\^|[^\s^])\^\^(?!\^)")
# Each pattern is scanned forward from every start position fired by the
# corresponding inline rule. The end-pattern itself is bounded; the cost
# comes from the surrounding parser invoking the scan at every '~~' / '==' / '^^'
# token in the input, giving N starts × O(N) per scan = O(N^2) total.

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.

Exploit Chain

1. 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.
2. 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 == / ^^).
3. 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.
4. 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.

Security Impact

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. Attacker capability: small input → large CPU. Doubling input size quadruples CPU time. Sustained requests deny service to other users. 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). Differential: PoC-verified against [email protected]:

import mistune, time
md = mistune.create_markdown(plugins=['strikethrough'])
for n in [500, 1000, 2000, 4000, 8000]:
    s = '~~x~~' * n
    t = time.time()
    md(s)
    print(f'  ~~x~~ * {n} ({len(s)}b): {(time.time()…

Mistune is a Python Markdown parser with renderers and plugins. Prior to 3.3.0, a run of closed tilde, equals-sign, or caret marker pairs around a character causes quadratic work in src/mistune/plugins/formatting.py when the strikethrough, mark, or insert plugin scans for matching markers from each possible start position, allowing denial of service through CPU exhaustion. This issue is fixed in version 3.3.0.

Mistune is a Python Markdown parser with renderers and plugins. Prior to 3.3.0, a run of closed tilde, equals-sign, or caret marker pairs around a character causes quadratic work in src/mistune/plugins/formatting.py when the strikethrough, mark, or insert plugin scans for matching markers from each possible start position, allowing denial of service through CPU exhaustion. This issue is fixed in version 3.3.0.

Mistune is a Python Markdown parser with renderers and plugins. Prior to 3.3.0, a run of closed tilde, equals-sign, or caret marker pairs around a character causes quadratic work in src/mistune/plugins/formatting.py when the strikethrough, mark, or insert plugin scans for matching markers from each possible start position, allowing denial of service through CPU exhaustion. This issue is fixed in version 3.3.0.

This update for python-mistune fixes the following issues

• CVE-2026-59922: quadratic-time parsing on long runs of some markers in formatting.py can lead to DoS (bsc#1271117).
• CVE-2026-59923: HTMLRenderer.safe_url() does not block percent-encoded javascript URIs and allows for XSS (bsc#1271119).
• CVE-2026-59924: improper processing of user-supplied include paths in Include.parse() can lead to path traversal and arbitrary file reads (bsc#1271121).
• CVE-2026-59925: quadratic-time parsing on long runs of some emphasis pairs in inline_parser can lead to DoS (bsc#1271125).
• CVE-2026-59926: improper escaping in render_admonition() can lead to atribute injection and XSS (bsc#1271127).
• CVE-2026-59927: uncontrolled recursion when processing two markdown files that include each other can lead to a DoS (bsc#1271128).
• CVE-2026-59928: quadratic-time parsing on long lists of repeated reference-link definitions in block_parser can lead to DoS (bsc#1271131).
• CVE-2026-59929: HARMFUL_PROTOCOLS list misses legacy and chained schemes and allow arbitrary script execution in user agents (bsc#1271132).
• CVE-2026-59930: the toc plugin and TableOfContents directive generate heading IDs with predictable values and allow for collisions with attacker-controlled id="toc_N" content (bsc#1271082).

This update for python-mistune fixes the following issues

• CVE-2026-59922: quadratic-time parsing on long runs of some markers in formatting.py can lead to DoS (bsc#1271117).
• CVE-2026-59923: HTMLRenderer.safe_url() does not block percent-encoded javascript URIs and allows for XSS (bsc#1271119).
• CVE-2026-59924: improper processing of user-supplied include paths in Include.parse() can lead to path traversal and arbitrary file reads (bsc#1271121).
• CVE-2026-59925: quadratic-time parsing on long runs of some emphasis pairs in inline_parser can lead to DoS (bsc#1271125).
• CVE-2026-59926: improper escaping in render_admonition() can lead to atribute injection and XSS (bsc#1271127).
• CVE-2026-59927: uncontrolled recursion when processing two markdown files that include each other can lead to a DoS (bsc#1271128).
• CVE-2026-59928: quadratic-time parsing on long lists of repeated reference-link definitions in block_parser can lead to DoS (bsc#1271131).
• CVE-2026-59929: HARMFUL_PROTOCOLS list misses legacy and chained schemes and allow arbitrary script execution in user agents (bsc#1271132).
• CVE-2026-59930: the toc plugin and TableOfContents directive generate heading IDs with predictable values and allow for collisions with attacker-controlled id="toc_N" content (bsc#1271082).