CVE-2026-59928

Summary

Type: Algorithmic-complexity DoS in reference-link definition handling. A markdown document with N reference-link definitions of the same key (or many distinct keys) takes O(N²) parser time. 5000 repeated [a]: u\n definitions take ~1.1 second; 10000 → ~4.5 seconds. File: src/mistune/block_parser.py (reference-link def parsing) and the surrounding ref_links env-dictionary handling. Root cause: every reference definition is parsed by scanning forward from each candidate position. The unikey normalisation runs per-def, the dictionary insert is per-def, and the lookup-by-label-then-iterate-defs path is linear in the number of stored defs. For input with N defs, the total work is O(N²).

Affected Code

src/mistune/block_parser.py — reference-definition rule fires on every line that matches [label]: url. For each one:

• unikey(label) is called (linear scan of the label).
• The def is appended to state.env['ref_links'].
• Later inline-link resolution looks up by unikey(label) in the dict (O(1)) but the surrounding parser revisits the def list for paragraph-vs-def disambiguation.

The cumulative parse time grows as the square of the number of defs.

Why it's wrong: the parser does not amortise the def-list scan. A single forward pass with a hash-keyed dict (already in place) plus a per-line classifier should make this O(N).

Exploit Chain

1. Application uses mistune to render attacker-supplied markdown. No plugins required.
2. Attacker submits a 35 KB document of [a]: u\n repeated 5000 times followed by [click][a].
3. CPU pegs for ~1.1 seconds. 10000 defs → ~4.5 s. 20000 → ~18 s. Doubling input quadruples time.

Security Impact

Attacker capability: small input → large CPU. Predictable scaling. Can be repeated. Preconditions: application uses mistune.create_markdown() (default config) on attacker-supplied markdown. Worth noting: the ref_links dictionary persists for the lifetime of the parse, so a long document with many defs builds up memory; with N defs of attacker-chosen length, the per-def normalisation cost compounds. Differential: PoC-verified against [email protected], default config:

import mistune, time
md = mistune.create_markdown()
for n in [1000, 2000, 5000, 10000]:
    s = '[a]: u\n' * n + '[click][a]'
    t = time.time()
    md(s)
    print(f'  ref defs * {n} ({len(s)}b): {(time.time() - t) * 1000:.0f}ms')

# Output (Python 3.13, Linux, 2.5GHz CPU):
#   ref defs *  1000  ( 7012b):    46ms
#   ref defs *  2000 (14012b):   186ms
#   ref defs *  5000 (35012b):  1121ms
#   ref defs * 10000 (70012b):  4400ms

The patched build (with the surrounding parser amortised to O(N)) keeps the time linear.

Suggested Fix

Replace the per-def re-scan with a single forward pass that classifies each line into ref_def | paragraph | other once and only inserts into ref_links once per def. The dict already exists; the wasted work is in the surrounding scan loop, not in the dict operations.

A regression test asserting that md('[a]: u\n' * 50_000 + '[click][a]') completes in under 1 second would catch any regression.

Mistune is a Python Markdown parser with renderers and plugins. Prior to 3.3.0, a Markdown document containing many repeated or distinct reference-link definitions causes quadratic work in src/mistune/block_parser.py and the ref_links environment dictionary handling, 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 Markdown document containing many repeated or distinct reference-link definitions causes quadratic work in src/mistune/block_parser.py and the ref_links environment dictionary handling, 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 Markdown document containing many repeated or distinct reference-link definitions causes quadratic work in src/mistune/block_parser.py and the ref_links environment dictionary handling, 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).