{"id":"GHSA-ffq3-xpv3-j92q","summary":"Mistune block_parser: quadratic-time parsing on long lists of repeated reference-link definitions","details":"## Summary\n\n**Type:** Algorithmic-complexity DoS in reference-link definition handling. A markdown document with N reference-link definitions of the same key (or many distinct keys) takes O(N²) parser time. 5000 repeated `[a]: u\\n` definitions take ~1.1 second; 10000 → ~4.5 seconds.\n**File:** `src/mistune/block_parser.py` (reference-link def parsing) and the surrounding `ref_links` env-dictionary handling.\n**Root cause:** every reference definition is parsed by scanning forward from each candidate position. The `unikey` normalisation runs per-def, the dictionary insert is per-def, and the lookup-by-label-then-iterate-defs path is linear in the number of stored defs. For input with N defs, the total work is O(N²).\n\n## Affected Code\n\n`src/mistune/block_parser.py` — reference-definition rule fires on every line that matches `[label]: url`. For each one:\n- `unikey(label)` is called (linear scan of the label).\n- The def is appended to `state.env['ref_links']`.\n- Later inline-link resolution looks up by `unikey(label)` in the dict (O(1)) but the surrounding parser revisits the def list for paragraph-vs-def disambiguation.\n\nThe cumulative parse time grows as the square of the number of defs.\n\n**Why it's wrong:** the parser does not amortise the def-list scan. A single forward pass with a hash-keyed dict (already in place) plus a per-line classifier should make this O(N).\n\n## Exploit Chain\n\n1. Application uses mistune to render attacker-supplied markdown. No plugins required.\n2. Attacker submits a 35 KB document of `[a]: u\\n` repeated 5000 times followed by `[click][a]`.\n3. CPU pegs for ~1.1 seconds. 10000 defs → ~4.5 s. 20000 → ~18 s. Doubling input quadruples time.\n\n## Security Impact\n\n**Attacker capability:** small input → large CPU. Predictable scaling. Can be repeated.\n**Preconditions:** application uses `mistune.create_markdown()` (default config) on attacker-supplied markdown. Worth noting: the `ref_links` dictionary persists for the lifetime of the parse, so a long document with many defs builds up memory; with N defs of attacker-chosen length, the per-def normalisation cost compounds.\n**Differential:** PoC-verified against mistune@3.2.1, default config:\n\n```python\nimport mistune, time\nmd = mistune.create_markdown()\nfor n in [1000, 2000, 5000, 10000]:\n    s = '[a]: u\\n' * n + '[click][a]'\n    t = time.time()\n    md(s)\n    print(f'  ref defs * {n} ({len(s)}b): {(time.time() - t) * 1000:.0f}ms')\n\n# Output (Python 3.13, Linux, 2.5GHz CPU):\n#   ref defs *  1000  ( 7012b):    46ms\n#   ref defs *  2000 (14012b):   186ms\n#   ref defs *  5000 (35012b):  1121ms\n#   ref defs * 10000 (70012b):  4400ms\n```\n\nThe patched build (with the surrounding parser amortised to O(N)) keeps the time linear.\n\n## Suggested Fix\n\nReplace the per-def re-scan with a single forward pass that classifies each line into `ref_def | paragraph | other` once and only inserts into `ref_links` once per def. The dict already exists; the wasted work is in the surrounding scan loop, not in the dict operations.\n\nA regression test asserting that `md('[a]: u\\n' * 50_000 + '[click][a]')` completes in under 1 second would catch any regression.","aliases":["CVE-2026-59928","PYSEC-2026-2216"],"modified":"2026-07-20T21:30:35.940183904Z","published":"2026-07-20T21:24:18Z","database_specific":{"nvd_published_at":"2026-07-08T17:17:28Z","cwe_ids":["CWE-1333","CWE-407"],"severity":"HIGH","github_reviewed":true,"github_reviewed_at":"2026-07-20T21:24:18Z"},"references":[{"type":"WEB","url":"https://github.com/lepture/mistune/security/advisories/GHSA-ffq3-xpv3-j92q"},{"type":"ADVISORY","url":"https://nvd.nist.gov/vuln/detail/CVE-2026-59928"},{"type":"WEB","url":"https://github.com/lepture/mistune/commit/2b04d7ba341c16ac78fe82d3076bdd5c3de87c69"},{"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-2216.yaml"}],"affected":[{"package":{"name":"mistune","ecosystem":"PyPI","purl":"pkg:pypi/mistune"},"ranges":[{"type":"ECOSYSTEM","events":[{"introduced":"0"},{"fixed":"3.3.0"}]}],"versions":["0.1.0","0.2.0","0.3.0","0.3.1","0.4","0.4.1","0.5","0.5.1","0.6","0.7","0.7.1","0.7.2","0.7.3","0.7.4","0.8","0.8.1","0.8.2","0.8.3","0.8.4","2.0.0","2.0.0a1","2.0.0a2","2.0.0a3","2.0.0a4","2.0.0a5","2.0.0a6","2.0.0rc1","2.0.1","2.0.2","2.0.3","2.0.4","2.0.5","2.1.0","3.0.0","3.0.0a1","3.0.0a2","3.0.0a3","3.0.0rc1","3.0.0rc2","3.0.0rc3","3.0.0rc4","3.0.0rc5","3.0.1","3.0.2","3.1.0","3.1.1","3.1.2","3.1.3","3.1.4","3.2.0","3.2.1"],"database_specific":{"source":"https://github.com/github/advisory-database/blob/main/advisories/github-reviewed/2026/07/GHSA-ffq3-xpv3-j92q/GHSA-ffq3-xpv3-j92q.json"}}],"schema_version":"1.9.0","severity":[{"type":"CVSS_V3","score":"CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H"}]}