high · 7.5CVE-2026-59928Jul 20, 2026

CVE-2026-59928: mistune Quadratic-Time ReDoS via Reference-Link Definitions

Rohit Hatagale
AI Security Researcher, SecureLayer7

Sending a Markdown document with thousands of repeated reference-link definitions causes mistune's block parser to do quadratic work, pegging the CPU for seconds on a small input.

Packagemistune
Ecosystempip
Affected< 3.3.0
Fixed in3.3.0

The problem

mistune's `block_parser.py` fires a reference-definition rule on every line matching `[label]: url`. For each definition it calls `unikey(label)`, appends to `state.env['ref_links']`, and then the surrounding scan loop revisits the accumulated def list for paragraph-vs-def disambiguation.

With N definitions the total work is O(N2). At 5000 repeated `[a]: u` lines (~35 KB) the parser takes about 1.1 seconds. At 10000 lines (~70 KB) it takes ~4.5 seconds. Doubling the input quadruples the CPU time. Any application that renders attacker-supplied Markdown is exposed with no plugins or special config required.

Proof of concept

A working proof-of-concept for CVE-2026-59928 in mistune, with the exact payload below.

python
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')

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

The root cause (CWE-407) is that the block parser has no guard against re-scanning the growing `ref_links` list on every new definition. Each new `[label]: url` line triggers a forward scan of all previously collected definitions for paragraph disambiguation, making the total scan count grow as N*(N-1)/2.

The patch (commit `2b04d7b`, tagged "block: Avoid quadratic ref link scans") replaces that re-scan loop with a single forward pass that classifies each line once, so insertion and lookup become O(1) per definition and overall parsing is O(N). The `ref_links` dict was already hash-keyed; the wasted work was entirely in the surrounding scan loop.

The fix

Upgrade mistune to 3.3.0 (`pip install --upgrade mistune`). The fix is in commit `2b04d7ba341c16ac78fe82d3076bdd5c3de87c69`. No configuration changes or workarounds exist for older versions.

Reported by lepture (Hsiaoming Yang).

References: [1][2][3][4][5][6]

Related research