Action not permitted
Modal body text goes here.
Modal Title
Modal Body
GHSA-FFQ3-XPV3-J92Q
Vulnerability from github – Published: 2026-07-20 21:24 – Updated: 2026-07-20 21:24Summary
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.
File: src/mistune/block_parser.py (reference-link def parsing) and the surrounding ref_links env-dictionary handling.
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²).
Affected Code
src/mistune/block_parser.py — reference-definition rule fires on every line that matches [label]: url. For each one:
- unikey(label) is called (linear scan of the label).
- The def is appended to state.env['ref_links'].
- 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.
The cumulative parse time grows as the square of the number of defs.
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).
Exploit Chain
- Application uses mistune to render attacker-supplied markdown. No plugins required.
- Attacker submits a 35 KB document of
[a]: u\nrepeated 5000 times followed by[click][a]. - CPU pegs for ~1.1 seconds. 10000 defs → ~4.5 s. 20000 → ~18 s. Doubling input quadruples time.
Security Impact
Attacker capability: small input → large CPU. Predictable scaling. Can be repeated.
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.
Differential: PoC-verified against mistune@3.2.1, default config:
import mistune, time
md = mistune.create_markdown()
for n in [1000, 2000, 5000, 10000]:
s = '[a]: u\n' * n + '[click][a]'
t = time.time()
md(s)
print(f' ref defs * {n} ({len(s)}b): {(time.time() - t) * 1000:.0f}ms')
# Output (Python 3.13, Linux, 2.5GHz CPU):
# ref defs * 1000 ( 7012b): 46ms
# ref defs * 2000 (14012b): 186ms
# ref defs * 5000 (35012b): 1121ms
# ref defs * 10000 (70012b): 4400ms
The patched build (with the surrounding parser amortised to O(N)) keeps the time linear.
Suggested Fix
Replace 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.
A regression test asserting that md('[a]: u\n' * 50_000 + '[click][a]') completes in under 1 second would catch any regression.
{
"affected": [
{
"package": {
"ecosystem": "PyPI",
"name": "mistune"
},
"ranges": [
{
"events": [
{
"introduced": "0"
},
{
"fixed": "3.3.0"
}
],
"type": "ECOSYSTEM"
}
]
}
],
"aliases": [
"CVE-2026-59928"
],
"database_specific": {
"cwe_ids": [
"CWE-1333",
"CWE-407"
],
"github_reviewed": true,
"github_reviewed_at": "2026-07-20T21:24:18Z",
"nvd_published_at": "2026-07-08T17:17:28Z",
"severity": "HIGH"
},
"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\u00b2) parser time. 5000 repeated `[a]: u\\n` definitions take ~1.1 second; 10000 \u2192 ~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\u00b2).\n\n## Affected Code\n\n`src/mistune/block_parser.py` \u2014 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[\u0027ref_links\u0027]`.\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\u0027s 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 \u2192 ~4.5 s. 20000 \u2192 ~18 s. Doubling input quadruples time.\n\n## Security Impact\n\n**Attacker capability:** small input \u2192 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 = \u0027[a]: u\\n\u0027 * n + \u0027[click][a]\u0027\n t = time.time()\n md(s)\n print(f\u0027 ref defs * {n} ({len(s)}b): {(time.time() - t) * 1000:.0f}ms\u0027)\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(\u0027[a]: u\\n\u0027 * 50_000 + \u0027[click][a]\u0027)` completes in under 1 second would catch any regression.",
"id": "GHSA-ffq3-xpv3-j92q",
"modified": "2026-07-20T21:24:18Z",
"published": "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"
}
],
"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 block_parser: quadratic-time parsing on long lists of repeated reference-link definitions"
}
BREW-ADR-VIEWER-CVE-2026-59928 (GHSA-FFQ3-XPV3-J92Q)
Vulnerability from osv_homebrew – Published: 2026-08-13 16:35 – Updated: 2026-09-17 19:58 – Source websiteSummary
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.
File: src/mistune/block_parser.py (reference-link def parsing) and the surrounding ref_links env-dictionary handling.
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²).
Affected Code
src/mistune/block_parser.py — reference-definition rule fires on every line that matches [label]: url. For each one:
- unikey(label) is called (linear scan of the label).
- The def is appended to state.env['ref_links'].
- 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.
The cumulative parse time grows as the square of the number of defs.
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).
Exploit Chain
- Application uses mistune to render attacker-supplied markdown. No plugins required.
- Attacker submits a 35 KB document of
[a]: u\nrepeated 5000 times followed by[click][a]. - CPU pegs for ~1.1 seconds. 10000 defs → ~4.5 s. 20000 → ~18 s. Doubling input quadruples time.
Security Impact
Attacker capability: small input → large CPU. Predictable scaling. Can be repeated.
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.
Differential: PoC-verified against mistune@3.2.1, default config:
import mistune, time
md = mistune.create_markdown()
for n in [1000, 2000, 5000, 10000]:
s = '[a]: u\n' * n + '[click][a]'
t = time.time()
md(s)
print(f' ref defs * {n} ({len(s)}b): {(time.time() - t) * 1000:.0f}ms')
# Output (Python 3.13, Linux, 2.5GHz CPU):
# ref defs * 1000 ( 7012b): 46ms
# ref defs * 2000 (14012b): 186ms
# ref defs * 5000 (35012b): 1121ms
# ref defs * 10000 (70012b): 4400ms
The patched build (with the surrounding parser amortised to O(N)) keeps the time linear.
Suggested Fix
Replace 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.
A regression test asserting that md('[a]: u\n' * 50_000 + '[click][a]') completes in under 1 second would catch any regression.
{
"affected": [
{
"ecosystem_specific": {
"fix": "bump",
"range_state": "fixed",
"resource": "mistune",
"resource_purl": "pkg:pypi/mistune@3.3.3",
"upstream_fixed_in": "3.3.0"
},
"package": {
"ecosystem": "Homebrew",
"name": "adr-viewer",
"purl": "pkg:brew/adr-viewer"
},
"ranges": [
{
"events": [
{
"introduced": "1.3.0"
},
{
"fixed": "1.4.0_6"
}
],
"type": "ECOSYSTEM"
}
]
}
],
"database_specific": {
"confidence": "high",
"source": "matched",
"strategy": "registry",
"upstream_evidence": [
{
"ecosystem": "PyPI",
"key": "pkg:pypi/mistune@3.3.3",
"name": "mistune",
"resource": "mistune",
"strategy": "registry",
"subject_version": "3.3.3"
}
]
},
"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\u00b2) parser time. 5000 repeated `[a]: u\\n` definitions take ~1.1 second; 10000 \u2192 ~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\u00b2).\n\n## Affected Code\n\n`src/mistune/block_parser.py` \u2014 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[\u0027ref_links\u0027]`.\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\u0027s 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 \u2192 ~4.5 s. 20000 \u2192 ~18 s. Doubling input quadruples time.\n\n## Security Impact\n\n**Attacker capability:** small input \u2192 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 = \u0027[a]: u\\n\u0027 * n + \u0027[click][a]\u0027\n t = time.time()\n md(s)\n print(f\u0027 ref defs * {n} ({len(s)}b): {(time.time() - t) * 1000:.0f}ms\u0027)\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(\u0027[a]: u\\n\u0027 * 50_000 + \u0027[click][a]\u0027)` completes in under 1 second would catch any regression.",
"id": "BREW-adr-viewer-CVE-2026-59928",
"modified": "2026-09-17T19:58:23Z",
"published": "2026-08-13T16:35:11Z",
"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"
}
],
"schema_version": "1.7.3",
"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 block_parser: quadratic-time parsing on long lists of repeated reference-link definitions",
"upstream": [
"GHSA-ffq3-xpv3-j92q",
"CVE-2026-59928",
"PYSEC-2026-2216"
]
}
BREW-BUKU-CVE-2026-59928 (GHSA-FFQ3-XPV3-J92Q)
Vulnerability from osv_homebrew – Published: 2026-08-13 16:38 – Updated: 2026-09-17 17:30 – Source websiteSummary
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.
File: src/mistune/block_parser.py (reference-link def parsing) and the surrounding ref_links env-dictionary handling.
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²).
Affected Code
src/mistune/block_parser.py — reference-definition rule fires on every line that matches [label]: url. For each one:
- unikey(label) is called (linear scan of the label).
- The def is appended to state.env['ref_links'].
- 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.
The cumulative parse time grows as the square of the number of defs.
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).
Exploit Chain
- Application uses mistune to render attacker-supplied markdown. No plugins required.
- Attacker submits a 35 KB document of
[a]: u\nrepeated 5000 times followed by[click][a]. - CPU pegs for ~1.1 seconds. 10000 defs → ~4.5 s. 20000 → ~18 s. Doubling input quadruples time.
Security Impact
Attacker capability: small input → large CPU. Predictable scaling. Can be repeated.
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.
Differential: PoC-verified against mistune@3.2.1, default config:
import mistune, time
md = mistune.create_markdown()
for n in [1000, 2000, 5000, 10000]:
s = '[a]: u\n' * n + '[click][a]'
t = time.time()
md(s)
print(f' ref defs * {n} ({len(s)}b): {(time.time() - t) * 1000:.0f}ms')
# Output (Python 3.13, Linux, 2.5GHz CPU):
# ref defs * 1000 ( 7012b): 46ms
# ref defs * 2000 (14012b): 186ms
# ref defs * 5000 (35012b): 1121ms
# ref defs * 10000 (70012b): 4400ms
The patched build (with the surrounding parser amortised to O(N)) keeps the time linear.
Suggested Fix
Replace 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.
A regression test asserting that md('[a]: u\n' * 50_000 + '[click][a]') completes in under 1 second would catch any regression.
| URL | Type | |||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
||||||||||||||||||||
{
"affected": [
{
"ecosystem_specific": {
"fix": "bump",
"range_state": "fixed",
"resource": "mistune",
"resource_purl": "pkg:pypi/mistune@3.3.3",
"upstream_fixed_in": "3.3.0"
},
"package": {
"ecosystem": "Homebrew",
"name": "buku",
"purl": "pkg:brew/buku"
},
"ranges": [
{
"events": [
{
"introduced": "5.1"
},
{
"fixed": "5.1_6"
}
],
"type": "ECOSYSTEM"
}
]
}
],
"database_specific": {
"confidence": "high",
"source": "matched",
"strategy": "registry",
"upstream_evidence": [
{
"ecosystem": "PyPI",
"key": "pkg:pypi/mistune@3.3.3",
"name": "mistune",
"resource": "mistune",
"strategy": "registry",
"subject_version": "3.3.3"
}
]
},
"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\u00b2) parser time. 5000 repeated `[a]: u\\n` definitions take ~1.1 second; 10000 \u2192 ~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\u00b2).\n\n## Affected Code\n\n`src/mistune/block_parser.py` \u2014 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[\u0027ref_links\u0027]`.\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\u0027s 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 \u2192 ~4.5 s. 20000 \u2192 ~18 s. Doubling input quadruples time.\n\n## Security Impact\n\n**Attacker capability:** small input \u2192 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 = \u0027[a]: u\\n\u0027 * n + \u0027[click][a]\u0027\n t = time.time()\n md(s)\n print(f\u0027 ref defs * {n} ({len(s)}b): {(time.time() - t) * 1000:.0f}ms\u0027)\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(\u0027[a]: u\\n\u0027 * 50_000 + \u0027[click][a]\u0027)` completes in under 1 second would catch any regression.",
"id": "BREW-buku-CVE-2026-59928",
"modified": "2026-09-17T17:30:49Z",
"published": "2026-08-13T16:38:25Z",
"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"
}
],
"schema_version": "1.7.3",
"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 block_parser: quadratic-time parsing on long lists of repeated reference-link definitions",
"upstream": [
"GHSA-ffq3-xpv3-j92q",
"CVE-2026-59928",
"PYSEC-2026-2216"
]
}
BREW-IREDIS-CVE-2026-59928 (GHSA-FFQ3-XPV3-J92Q)
Vulnerability from osv_homebrew – Published: 2026-08-13 17:00 – Updated: 2026-09-17 17:45 – Source websiteSummary
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.
File: src/mistune/block_parser.py (reference-link def parsing) and the surrounding ref_links env-dictionary handling.
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²).
Affected Code
src/mistune/block_parser.py — reference-definition rule fires on every line that matches [label]: url. For each one:
- unikey(label) is called (linear scan of the label).
- The def is appended to state.env['ref_links'].
- 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.
The cumulative parse time grows as the square of the number of defs.
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).
Exploit Chain
- Application uses mistune to render attacker-supplied markdown. No plugins required.
- Attacker submits a 35 KB document of
[a]: u\nrepeated 5000 times followed by[click][a]. - CPU pegs for ~1.1 seconds. 10000 defs → ~4.5 s. 20000 → ~18 s. Doubling input quadruples time.
Security Impact
Attacker capability: small input → large CPU. Predictable scaling. Can be repeated.
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.
Differential: PoC-verified against mistune@3.2.1, default config:
import mistune, time
md = mistune.create_markdown()
for n in [1000, 2000, 5000, 10000]:
s = '[a]: u\n' * n + '[click][a]'
t = time.time()
md(s)
print(f' ref defs * {n} ({len(s)}b): {(time.time() - t) * 1000:.0f}ms')
# Output (Python 3.13, Linux, 2.5GHz CPU):
# ref defs * 1000 ( 7012b): 46ms
# ref defs * 2000 (14012b): 186ms
# ref defs * 5000 (35012b): 1121ms
# ref defs * 10000 (70012b): 4400ms
The patched build (with the surrounding parser amortised to O(N)) keeps the time linear.
Suggested Fix
Replace 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.
A regression test asserting that md('[a]: u\n' * 50_000 + '[click][a]') completes in under 1 second would catch any regression.
| URL | Type | |||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
||||||||||||||||||||
{
"affected": [
{
"ecosystem_specific": {
"fix": "bump",
"range_state": "fixed",
"resource": "mistune",
"resource_purl": "pkg:pypi/mistune@3.3.3",
"upstream_fixed_in": "3.3.0"
},
"package": {
"ecosystem": "Homebrew",
"name": "iredis",
"purl": "pkg:brew/iredis"
},
"ranges": [
{
"events": [
{
"introduced": "1.9.4"
},
{
"fixed": "1.16.1_3"
}
],
"type": "ECOSYSTEM"
}
]
}
],
"database_specific": {
"confidence": "high",
"source": "matched",
"strategy": "registry",
"upstream_evidence": [
{
"ecosystem": "PyPI",
"key": "pkg:pypi/mistune@3.3.3",
"name": "mistune",
"resource": "mistune",
"strategy": "registry",
"subject_version": "3.3.3"
}
]
},
"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\u00b2) parser time. 5000 repeated `[a]: u\\n` definitions take ~1.1 second; 10000 \u2192 ~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\u00b2).\n\n## Affected Code\n\n`src/mistune/block_parser.py` \u2014 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[\u0027ref_links\u0027]`.\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\u0027s 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 \u2192 ~4.5 s. 20000 \u2192 ~18 s. Doubling input quadruples time.\n\n## Security Impact\n\n**Attacker capability:** small input \u2192 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 = \u0027[a]: u\\n\u0027 * n + \u0027[click][a]\u0027\n t = time.time()\n md(s)\n print(f\u0027 ref defs * {n} ({len(s)}b): {(time.time() - t) * 1000:.0f}ms\u0027)\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(\u0027[a]: u\\n\u0027 * 50_000 + \u0027[click][a]\u0027)` completes in under 1 second would catch any regression.",
"id": "BREW-iredis-CVE-2026-59928",
"modified": "2026-09-17T17:45:16Z",
"published": "2026-08-13T17:00:03Z",
"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"
}
],
"schema_version": "1.7.3",
"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 block_parser: quadratic-time parsing on long lists of repeated reference-link definitions",
"upstream": [
"GHSA-ffq3-xpv3-j92q",
"CVE-2026-59928",
"PYSEC-2026-2216"
]
}
BREW-JIRATUI-CVE-2026-59928 (GHSA-FFQ3-XPV3-J92Q)
Vulnerability from osv_homebrew – Published: 2026-08-13 17:00 – Updated: 2026-09-17 18:51 – Source websiteSummary
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.
File: src/mistune/block_parser.py (reference-link def parsing) and the surrounding ref_links env-dictionary handling.
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²).
Affected Code
src/mistune/block_parser.py — reference-definition rule fires on every line that matches [label]: url. For each one:
- unikey(label) is called (linear scan of the label).
- The def is appended to state.env['ref_links'].
- 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.
The cumulative parse time grows as the square of the number of defs.
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).
Exploit Chain
- Application uses mistune to render attacker-supplied markdown. No plugins required.
- Attacker submits a 35 KB document of
[a]: u\nrepeated 5000 times followed by[click][a]. - CPU pegs for ~1.1 seconds. 10000 defs → ~4.5 s. 20000 → ~18 s. Doubling input quadruples time.
Security Impact
Attacker capability: small input → large CPU. Predictable scaling. Can be repeated.
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.
Differential: PoC-verified against mistune@3.2.1, default config:
import mistune, time
md = mistune.create_markdown()
for n in [1000, 2000, 5000, 10000]:
s = '[a]: u\n' * n + '[click][a]'
t = time.time()
md(s)
print(f' ref defs * {n} ({len(s)}b): {(time.time() - t) * 1000:.0f}ms')
# Output (Python 3.13, Linux, 2.5GHz CPU):
# ref defs * 1000 ( 7012b): 46ms
# ref defs * 2000 (14012b): 186ms
# ref defs * 5000 (35012b): 1121ms
# ref defs * 10000 (70012b): 4400ms
The patched build (with the surrounding parser amortised to O(N)) keeps the time linear.
Suggested Fix
Replace 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.
A regression test asserting that md('[a]: u\n' * 50_000 + '[click][a]') completes in under 1 second would catch any regression.
| URL | Type | |||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
||||||||||||||||||||
{
"affected": [
{
"ecosystem_specific": {
"fix": "bump",
"range_state": "fixed",
"resource": "mistune",
"resource_purl": "pkg:pypi/mistune@3.3.4",
"upstream_fixed_in": "3.3.0"
},
"package": {
"ecosystem": "Homebrew",
"name": "jiratui",
"purl": "pkg:brew/jiratui"
},
"ranges": [
{
"events": [
{
"introduced": "1.8.0"
},
{
"fixed": "1.10.1"
}
],
"type": "ECOSYSTEM"
}
]
}
],
"database_specific": {
"confidence": "high",
"source": "matched",
"strategy": "registry",
"upstream_evidence": [
{
"ecosystem": "PyPI",
"key": "pkg:pypi/mistune@3.3.4",
"name": "mistune",
"resource": "mistune",
"strategy": "registry",
"subject_version": "3.3.4"
}
]
},
"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\u00b2) parser time. 5000 repeated `[a]: u\\n` definitions take ~1.1 second; 10000 \u2192 ~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\u00b2).\n\n## Affected Code\n\n`src/mistune/block_parser.py` \u2014 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[\u0027ref_links\u0027]`.\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\u0027s 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 \u2192 ~4.5 s. 20000 \u2192 ~18 s. Doubling input quadruples time.\n\n## Security Impact\n\n**Attacker capability:** small input \u2192 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 = \u0027[a]: u\\n\u0027 * n + \u0027[click][a]\u0027\n t = time.time()\n md(s)\n print(f\u0027 ref defs * {n} ({len(s)}b): {(time.time() - t) * 1000:.0f}ms\u0027)\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(\u0027[a]: u\\n\u0027 * 50_000 + \u0027[click][a]\u0027)` completes in under 1 second would catch any regression.",
"id": "BREW-jiratui-CVE-2026-59928",
"modified": "2026-09-17T18:51:24Z",
"published": "2026-08-13T17:00:58Z",
"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"
}
],
"schema_version": "1.7.3",
"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 block_parser: quadratic-time parsing on long lists of repeated reference-link definitions",
"upstream": [
"GHSA-ffq3-xpv3-j92q",
"CVE-2026-59928",
"PYSEC-2026-2216"
]
}
BREW-JUPYTERLAB-CVE-2026-59928 (GHSA-FFQ3-XPV3-J92Q)
Vulnerability from osv_homebrew – Published: 2026-08-13 17:01 – Updated: 2026-09-17 19:02 – Source websiteSummary
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.
File: src/mistune/block_parser.py (reference-link def parsing) and the surrounding ref_links env-dictionary handling.
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²).
Affected Code
src/mistune/block_parser.py — reference-definition rule fires on every line that matches [label]: url. For each one:
- unikey(label) is called (linear scan of the label).
- The def is appended to state.env['ref_links'].
- 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.
The cumulative parse time grows as the square of the number of defs.
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).
Exploit Chain
- Application uses mistune to render attacker-supplied markdown. No plugins required.
- Attacker submits a 35 KB document of
[a]: u\nrepeated 5000 times followed by[click][a]. - CPU pegs for ~1.1 seconds. 10000 defs → ~4.5 s. 20000 → ~18 s. Doubling input quadruples time.
Security Impact
Attacker capability: small input → large CPU. Predictable scaling. Can be repeated.
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.
Differential: PoC-verified against mistune@3.2.1, default config:
import mistune, time
md = mistune.create_markdown()
for n in [1000, 2000, 5000, 10000]:
s = '[a]: u\n' * n + '[click][a]'
t = time.time()
md(s)
print(f' ref defs * {n} ({len(s)}b): {(time.time() - t) * 1000:.0f}ms')
# Output (Python 3.13, Linux, 2.5GHz CPU):
# ref defs * 1000 ( 7012b): 46ms
# ref defs * 2000 (14012b): 186ms
# ref defs * 5000 (35012b): 1121ms
# ref defs * 10000 (70012b): 4400ms
The patched build (with the surrounding parser amortised to O(N)) keeps the time linear.
Suggested Fix
Replace 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.
A regression test asserting that md('[a]: u\n' * 50_000 + '[click][a]') completes in under 1 second would catch any regression.
| URL | Type | |||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
||||||||||||||||||||
{
"affected": [
{
"ecosystem_specific": {
"fix": "bump",
"range_state": "fixed",
"resource": "mistune",
"resource_purl": "pkg:pypi/mistune@3.3.4",
"upstream_fixed_in": "3.3.0"
},
"package": {
"ecosystem": "Homebrew",
"name": "jupyterlab",
"purl": "pkg:brew/jupyterlab"
},
"ranges": [
{
"events": [
{
"introduced": "1.2.0"
},
{
"fixed": "4.6.1"
}
],
"type": "ECOSYSTEM"
}
]
}
],
"database_specific": {
"confidence": "high",
"source": "matched",
"strategy": "registry",
"upstream_evidence": [
{
"ecosystem": "PyPI",
"key": "pkg:pypi/mistune@3.3.4",
"name": "mistune",
"resource": "mistune",
"strategy": "registry",
"subject_version": "3.3.4"
}
]
},
"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\u00b2) parser time. 5000 repeated `[a]: u\\n` definitions take ~1.1 second; 10000 \u2192 ~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\u00b2).\n\n## Affected Code\n\n`src/mistune/block_parser.py` \u2014 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[\u0027ref_links\u0027]`.\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\u0027s 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 \u2192 ~4.5 s. 20000 \u2192 ~18 s. Doubling input quadruples time.\n\n## Security Impact\n\n**Attacker capability:** small input \u2192 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 = \u0027[a]: u\\n\u0027 * n + \u0027[click][a]\u0027\n t = time.time()\n md(s)\n print(f\u0027 ref defs * {n} ({len(s)}b): {(time.time() - t) * 1000:.0f}ms\u0027)\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(\u0027[a]: u\\n\u0027 * 50_000 + \u0027[click][a]\u0027)` completes in under 1 second would catch any regression.",
"id": "BREW-jupyterlab-CVE-2026-59928",
"modified": "2026-09-17T19:02:18Z",
"published": "2026-08-13T17:01: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"
}
],
"schema_version": "1.7.3",
"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 block_parser: quadratic-time parsing on long lists of repeated reference-link definitions",
"upstream": [
"GHSA-ffq3-xpv3-j92q",
"CVE-2026-59928",
"PYSEC-2026-2216"
]
}
BREW-RECON-NG-CVE-2026-59928 (GHSA-FFQ3-XPV3-J92Q)
Vulnerability from osv_homebrew – Published: 2026-08-13 17:32 – Updated: 2026-09-10 01:05 – Source websiteSummary
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.
File: src/mistune/block_parser.py (reference-link def parsing) and the surrounding ref_links env-dictionary handling.
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²).
Affected Code
src/mistune/block_parser.py — reference-definition rule fires on every line that matches [label]: url. For each one:
- unikey(label) is called (linear scan of the label).
- The def is appended to state.env['ref_links'].
- 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.
The cumulative parse time grows as the square of the number of defs.
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).
Exploit Chain
- Application uses mistune to render attacker-supplied markdown. No plugins required.
- Attacker submits a 35 KB document of
[a]: u\nrepeated 5000 times followed by[click][a]. - CPU pegs for ~1.1 seconds. 10000 defs → ~4.5 s. 20000 → ~18 s. Doubling input quadruples time.
Security Impact
Attacker capability: small input → large CPU. Predictable scaling. Can be repeated.
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.
Differential: PoC-verified against mistune@3.2.1, default config:
import mistune, time
md = mistune.create_markdown()
for n in [1000, 2000, 5000, 10000]:
s = '[a]: u\n' * n + '[click][a]'
t = time.time()
md(s)
print(f' ref defs * {n} ({len(s)}b): {(time.time() - t) * 1000:.0f}ms')
# Output (Python 3.13, Linux, 2.5GHz CPU):
# ref defs * 1000 ( 7012b): 46ms
# ref defs * 2000 (14012b): 186ms
# ref defs * 5000 (35012b): 1121ms
# ref defs * 10000 (70012b): 4400ms
The patched build (with the surrounding parser amortised to O(N)) keeps the time linear.
Suggested Fix
Replace 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.
A regression test asserting that md('[a]: u\n' * 50_000 + '[click][a]') completes in under 1 second would catch any regression.
| URL | Type | |||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
||||||||||||||||||||
{
"affected": [
{
"ecosystem_specific": {
"fix": null,
"range_state": "affected",
"resource": "mistune",
"resource_purl": "pkg:pypi/mistune@3.1.4",
"upstream_fixed_in": "3.3.0"
},
"package": {
"ecosystem": "Homebrew",
"name": "recon-ng",
"purl": "pkg:brew/recon-ng"
},
"ranges": [
{
"events": [
{
"introduced": "0"
}
],
"type": "ECOSYSTEM"
}
]
}
],
"database_specific": {
"confidence": "high",
"source": "matched",
"strategy": "registry",
"upstream_evidence": [
{
"ecosystem": "PyPI",
"key": "pkg:pypi/mistune@3.1.4",
"name": "mistune",
"resource": "mistune",
"strategy": "registry",
"subject_version": "3.1.4"
}
]
},
"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\u00b2) parser time. 5000 repeated `[a]: u\\n` definitions take ~1.1 second; 10000 \u2192 ~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\u00b2).\n\n## Affected Code\n\n`src/mistune/block_parser.py` \u2014 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[\u0027ref_links\u0027]`.\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\u0027s 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 \u2192 ~4.5 s. 20000 \u2192 ~18 s. Doubling input quadruples time.\n\n## Security Impact\n\n**Attacker capability:** small input \u2192 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 = \u0027[a]: u\\n\u0027 * n + \u0027[click][a]\u0027\n t = time.time()\n md(s)\n print(f\u0027 ref defs * {n} ({len(s)}b): {(time.time() - t) * 1000:.0f}ms\u0027)\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(\u0027[a]: u\\n\u0027 * 50_000 + \u0027[click][a]\u0027)` completes in under 1 second would catch any regression.",
"id": "BREW-recon-ng-CVE-2026-59928",
"modified": "2026-09-10T01:05:54Z",
"published": "2026-08-13T17:32:25Z",
"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"
}
],
"schema_version": "1.7.3",
"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 block_parser: quadratic-time parsing on long lists of repeated reference-link definitions",
"upstream": [
"GHSA-ffq3-xpv3-j92q",
"CVE-2026-59928",
"PYSEC-2026-2216"
]
}
CVE-2026-59928 (GCVE-0-2026-59928)
Vulnerability from cvelistv5 – Published: 2026-07-08 16:23 – Updated: 2026-07-08 19:40| URL | Tags |
|---|---|
| https://github.com/lepture/mistune/security/advis… | x_refsource_CONFIRM |
| https://github.com/lepture/mistune/commit/2b04d7b… | x_refsource_MISC |
| https://github.com/lepture/mistune/releases/tag/v3.3.0 | x_refsource_MISC |
{
"containers": {
"adp": [
{
"metrics": [
{
"other": {
"content": {
"id": "CVE-2026-59928",
"options": [
{
"Exploitation": "poc"
},
{
"Automatable": "yes"
},
{
"Technical Impact": "partial"
}
],
"role": "CISA Coordinator",
"timestamp": "2026-07-08T17:46:13.539153Z",
"version": "2.0.3"
},
"type": "ssvc"
}
}
],
"providerMetadata": {
"dateUpdated": "2026-07-08T19:40:43.968Z",
"orgId": "134c704f-9b21-4f2e-91b3-4a467353bcc0",
"shortName": "CISA-ADP"
},
"references": [
{
"tags": [
"exploit"
],
"url": "https://github.com/lepture/mistune/security/advisories/GHSA-ffq3-xpv3-j92q"
}
],
"title": "CISA ADP Vulnrichment"
}
],
"cna": {
"affected": [
{
"product": "mistune",
"vendor": "lepture",
"versions": [
{
"status": "affected",
"version": "\u003c 3.3.0"
}
]
}
],
"descriptions": [
{
"lang": "en",
"value": "Mistune is a Python Markdown parser with renderers and plugins. Prior to 3.3.0, a Markdown document containing many repeated or distinct reference-link definitions causes quadratic work in src/mistune/block_parser.py and the ref_links environment dictionary handling, allowing denial of service through CPU exhaustion. This issue is fixed in version 3.3.0."
}
],
"metrics": [
{
"cvssV3_1": {
"attackComplexity": "LOW",
"attackVector": "NETWORK",
"availabilityImpact": "HIGH",
"baseScore": 7.5,
"baseSeverity": "HIGH",
"confidentialityImpact": "NONE",
"integrityImpact": "NONE",
"privilegesRequired": "NONE",
"scope": "UNCHANGED",
"userInteraction": "NONE",
"vectorString": "CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H",
"version": "3.1"
}
}
],
"problemTypes": [
{
"descriptions": [
{
"cweId": "CWE-407",
"description": "CWE-407: Inefficient Algorithmic Complexity",
"lang": "en",
"type": "CWE"
}
]
},
{
"descriptions": [
{
"cweId": "CWE-1333",
"description": "CWE-1333: Inefficient Regular Expression Complexity",
"lang": "en",
"type": "CWE"
}
]
}
],
"providerMetadata": {
"dateUpdated": "2026-07-08T16:23:21.000Z",
"orgId": "a0819718-46f1-4df5-94e2-005712e83aaa",
"shortName": "GitHub_M"
},
"references": [
{
"name": "https://github.com/lepture/mistune/security/advisories/GHSA-ffq3-xpv3-j92q",
"tags": [
"x_refsource_CONFIRM"
],
"url": "https://github.com/lepture/mistune/security/advisories/GHSA-ffq3-xpv3-j92q"
},
{
"name": "https://github.com/lepture/mistune/commit/2b04d7ba341c16ac78fe82d3076bdd5c3de87c69",
"tags": [
"x_refsource_MISC"
],
"url": "https://github.com/lepture/mistune/commit/2b04d7ba341c16ac78fe82d3076bdd5c3de87c69"
},
{
"name": "https://github.com/lepture/mistune/releases/tag/v3.3.0",
"tags": [
"x_refsource_MISC"
],
"url": "https://github.com/lepture/mistune/releases/tag/v3.3.0"
}
],
"source": {
"advisory": "GHSA-ffq3-xpv3-j92q",
"discovery": "UNKNOWN"
},
"title": "Mistune block_parser: quadratic-time parsing on long lists of repeated reference-link definitions"
}
},
"cveMetadata": {
"assignerOrgId": "a0819718-46f1-4df5-94e2-005712e83aaa",
"assignerShortName": "GitHub_M",
"cveId": "CVE-2026-59928",
"datePublished": "2026-07-08T16:23:21.000Z",
"dateReserved": "2026-07-07T18:20:06.126Z",
"dateUpdated": "2026-07-08T19:40:43.968Z",
"state": "PUBLISHED"
},
"dataType": "CVE_RECORD",
"dataVersion": "5.2"
}
PYSEC-2026-2216
Vulnerability from pysec - Published: 2026-07-08 17:17 - Updated: 2026-07-13 05:49Mistune is a Python Markdown parser with renderers and plugins. Prior to 3.3.0, a Markdown document containing many repeated or distinct reference-link definitions causes quadratic work in src/mistune/block_parser.py and the ref_links environment dictionary handling, allowing denial of service through CPU exhaustion. This issue is fixed in version 3.3.0.
| Name | purl | mistune | pkg:pypi/mistune |
|---|
{
"affected": [
{
"ecosystem_specific": {},
"package": {
"ecosystem": "PyPI",
"name": "mistune",
"purl": "pkg:pypi/mistune"
},
"ranges": [
{
"events": [
{
"introduced": "0"
},
{
"fixed": "3.3.0"
}
],
"type": "ECOSYSTEM"
}
],
"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"
]
}
],
"aliases": [
"CVE-2026-59928",
"GHSA-ffq3-xpv3-j92q"
],
"details": "Mistune is a Python Markdown parser with renderers and plugins. Prior to 3.3.0, a Markdown document containing many repeated or distinct reference-link definitions causes quadratic work in src/mistune/block_parser.py and the ref_links environment dictionary handling, allowing denial of service through CPU exhaustion. This issue is fixed in version 3.3.0.",
"id": "PYSEC-2026-2216",
"modified": "2026-07-13T05:49:57.952134Z",
"published": "2026-07-08T17:17:28.600Z",
"references": [
{
"type": "ADVISORY",
"url": "https://github.com/lepture/mistune/releases/tag/v3.3.0"
},
{
"type": "FIX",
"url": "https://github.com/lepture/mistune/commit/2b04d7ba341c16ac78fe82d3076bdd5c3de87c69"
},
{
"type": "EVIDENCE",
"url": "https://github.com/lepture/mistune/security/advisories/GHSA-ffq3-xpv3-j92q"
}
],
"severity": [
{
"score": "CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H",
"type": "CVSS_V3"
}
]
}
Sightings
| Author | Source | Type | Date | Other |
|---|
Nomenclature
- Seen: The vulnerability was mentioned, discussed, or observed by the user.
- Confirmed: The vulnerability has been validated from an analyst's perspective.
- Published Proof of Concept: A public proof of concept is available for this vulnerability.
- Exploited: The vulnerability was observed as exploited by the user who reported the sighting.
- Patched: The vulnerability was observed as successfully patched by the user who reported the sighting.
- Not exploited: The vulnerability was not observed as exploited by the user who reported the sighting.
- Not confirmed: The user expressed doubt about the validity of the vulnerability.
- Not patched: The vulnerability was not observed as successfully patched by the user who reported the sighting.
The approach is described in our paper Mapping CVEs to MITRE ATT&CK Techniques: A Curated Gold-Set Classifier and the Limits of LLM-Assisted Label Expansion.
Browse all ATT&CK techniques and the vulnerabilities related to each.
Related by attack behaviour
Vulnerabilities whose description is nearest to this one in the vector space of the CIRCL/vulnerability-attack-technique-biencoder model. This is a similarity search over the bi-encoder space (plain cosine), not a classification, and it has no measured accuracy.