GHSA-4j32-57v6-6g45

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...