{
  "affected": [
    {
      "package": {
        "ecosystem": "PyPI",
        "name": "mistune"
      },
      "ranges": [
        {
          "events": [
            {
              "introduced": "0"
            },
            {
              "fixed": "3.3.0"
            }
          ],
          "type": "ECOSYSTEM"
        }
      ]
    }
  ],
  "aliases": [
    "CVE-2026-59922"
  ],
  "database_specific": {
    "cwe_ids": [
      "CWE-1333",
      "CWE-407"
    ],
    "github_reviewed": true,
    "github_reviewed_at": "2026-07-20T21:34:37Z",
    "nvd_published_at": "2026-07-08T17:17:27Z",
    "severity": "HIGH"
  },
  "details": "## Summary\n\n**Type:** Algorithmic-complexity denial of service. A run of N closed pairs `~~x~~~~x~~...` (or the analogous `==x==` for `mark`, `^^x^^` for `insert`) causes O(N\u00b2) work in the formatting parser. With the `strikethrough`, `mark`, or `insert` plugin enabled, an 8 KB input pegs the CPU for ~4 seconds; 16 KB \u2192 ~17 seconds. \n**File:** `src/mistune/plugins/formatting.py`, lines 13-15 (the `_STRIKE_END` / `_MARK_END` / `_INSERT_END` patterns and their per-position scan).\n**Root cause:** for each opening `~~`/`==`/`^^` the parser scans forward for the matching close pattern. The scan itself uses a bounded regex, but the parser tries the close-scan at every potential start position. For input shaped like `~~x~~` repeated N times, every `~~` is examined as a possible start, each scan covers up to the end of input. Total work is O(N\u00b2). Default config without these plugins handles the same input in linear time (4 ms for 4000 reps), confirming the cost is in the formatting plugin\u0027s per-marker scan, not in core parsing.\n\n## Affected Code\n\n**File:** `src/mistune/plugins/formatting.py`, lines 12-16.\n\n```python\n_STRIKE_END = re.compile(r\"(?:\" + PREVENT_BACKSLASH + r\"\\\\~|[^\\s~])~~(?!~)\")\n_MARK_END = re.compile(r\"(?:\" + PREVENT_BACKSLASH + r\"\\\\=|[^\\s=])==(?!=)\")\n_INSERT_END = re.compile(r\"(?:\" + PREVENT_BACKSLASH + r\"\\\\\\^|[^\\s^])\\^\\^(?!\\^)\")\n# Each pattern is scanned forward from every start position fired by the\n# corresponding inline rule. The end-pattern itself is bounded; the cost\n# comes from the surrounding parser invoking the scan at every \u0027~~\u0027 / \u0027==\u0027 / \u0027^^\u0027\n# token in the input, giving N starts \u00d7 O(N) per scan = O(N^2) total.\n```\n\n**Why it\u0027s wrong:** the same algorithmic-complexity flaw class as `[` / `[a` parsing in core: a per-token retry loop without memoisation of failed positions. Each formatting marker is tried as both a potential start and as a continuation. A linear-pass delimiter-stack algorithm (matching how `commonmark-py` and `markdown-it-py` handle emphasis) would do this work in O(N) total. The bounded regex on each individual scan does not bound the parser-level repetition.\n\n## Exploit Chain\n\n1. Application uses mistune to render user-supplied markdown and has any of the formatting plugins enabled (`plugins=[\u0027strikethrough\u0027]`, `[\u0027mark\u0027]`, `[\u0027insert\u0027]`, or any superset). These plugins are commonly enabled because GitHub-flavoured-Markdown compatibility requires `~~strikethrough~~` and many editors emit `==highlighting==` and `^^underline^^` shortcuts.\n2. Attacker submits an 8 KB markdown payload of the form `~~x~~~~x~~~~x~~...` (40 000 characters of `~~x~~` repeated 8000 times, or the analogous shape with `==` / `^^`).\n3. Server calls `mistune.create_markdown(plugins=[\u0027strikethrough\u0027])(payload)`. CPU pegs for ~4 seconds; 16 KB \u2192 ~17 seconds; 32 KB \u2192 ~70 seconds. Pure CPU cost, no significant memory growth.\n4. Repeating the request floods the worker pool. On a single-thread WSGI handler this is one request per outage; on a thread pool, a small number of concurrent attackers exhausts capacity.\n\n## Security Impact\n\n**Severity:** sec-high. Network-reachable, no authentication, predictable scaling, single-payload primitive. Only requires a user-supplied markdown sink and a formatting plugin enabled \u2014 both are common.\n**Attacker capability:** small input \u2192 large CPU. Doubling input size quadruples CPU time. Sustained requests deny service to other users.\n**Preconditions:** application uses mistune with any of `strikethrough`, `mark`, or `insert` plugins enabled. Default config does NOT enable these (so the attack only fires against the substantial deployed population that turns them on for GFM/markdown-extra compatibility).\n**Differential:** PoC-verified against mistune@3.2.1:\n\n```python\nimport mistune, time\nmd = mistune.create_markdown(plugins=[\u0027strikethrough\u0027])\nfor n in [500, 1000, 2000, 4000, 8000]:\n    s = \u0027~~x~~\u0027 * n\n    t = time.time()\n    md(s)\n    print(f\u0027  ~~x~~ * {n} ({len(s)}b): {(time.time() - t) * 1000:.0f}ms\u0027)\n\n# Output (Python 3.13, Linux, 2.5GHz CPU):\n#   ~~x~~ *  500  (2500b):    19ms\n#   ~~x~~ * 1000  (5000b):    71ms\n#   ~~x~~ * 2000 (10000b):   272ms\n#   ~~x~~ * 4000 (20000b):  1090ms\n#   ~~x~~ * 8000 (40000b):  4302ms\n\n# Identical scaling for `==x==` (mark) and `^^x^^` (insert):\nmd = mistune.create_markdown(plugins=[\u0027mark\u0027])\nmd(\u0027==x==\u0027 * 4000)   # ~1100ms\nmd = mistune.create_markdown(plugins=[\u0027insert\u0027])\nmd(\u0027^^x^^\u0027 * 4000)   # ~1080ms\n\n# Without the plugin, the same input parses in linear time:\nmd = mistune.create_markdown()  # no plugins\nmd(\u0027~~x~~\u0027 * 4000)               # 4ms (1000x faster)\n```\n\nThe patched build (with the suggested fix below \u2014 either a delimiter-stack rewrite or a hard cap on the number of unmatched markers tracked) keeps the time linear in N.\n\n## Suggested Fix\n\nThe minimal fix is to cap the number of simultaneously-tracked unmatched markers, treating extras as literal text. The proper fix is a single-pass delimiter-stack algorithm matching the CommonMark reference implementation. Surgical patch:\n\n```diff\n--- a/src/mistune/plugins/formatting.py\n+++ b/src/mistune/plugins/formatting.py\n@@ ... in the parse_strikethrough / parse_mark / parse_insert functions\n+    # Bound the number of open markers the parser will track concurrently.\n+    # Inputs with more than this many open ~~ / == / ^^ in flight are\n+    # almost certainly adversarial; CommonMark gives no semantics to\n+    # deeply nested unmatched markers.\n+    MAX_OPEN_MARKERS = 100\n+    if open_marker_count \u003e MAX_OPEN_MARKERS:\n+        # treat remaining markers as literal text, do not invoke the\n+        # forward-scan to find a close\n+        ...\n```\n\nA regression test should assert that `md(\u0027~~x~~\u0027 * 50_000)` completes in under 1 second. The same fix shape applies to `_MARK_END` and `_INSERT_END`.",
  "id": "GHSA-c8j7-8cv4-2xmq",
  "modified": "2026-07-20T21:34:37Z",
  "published": "2026-07-20T21:34:37Z",
  "references": [
    {
      "type": "WEB",
      "url": "https://github.com/lepture/mistune/security/advisories/GHSA-c8j7-8cv4-2xmq"
    },
    {
      "type": "ADVISORY",
      "url": "https://nvd.nist.gov/vuln/detail/CVE-2026-59922"
    },
    {
      "type": "WEB",
      "url": "https://github.com/lepture/mistune/commit/96d0f57f8fe9eeb06bb4cff521962a27d7c402e7"
    },
    {
      "type": "PACKAGE",
      "url": "https://github.com/lepture/mistune"
    },
    {
      "type": "WEB",
      "url": "https://github.com/lepture/mistune/releases/tag/v3.3.0"
    },
    {
      "type": "WEB",
      "url": "https://github.com/pypa/advisory-database/tree/main/vulns/mistune/PYSEC-2026-2210.yaml"
    }
  ],
  "schema_version": "1.4.0",
  "severity": [
    {
      "score": "CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H",
      "type": "CVSS_V3"
    }
  ],
  "summary": "Mistune plugins/formatting: quadratic-time parsing on long runs of `~~x~~`, `==x==`, and `^^x^^` markers (strikethrough / mark / insert)"
}