NLTK: Quadratic CPU exhaustion

## Summary `LegalitySyllableTokenizer.tokenize` in the NLTK tokenizer package contains an unguarded O(n^2) processing loop. When the method is called on a single token that consists of a long run of vowels (for example `"a" * n`), it consumes CPU time proportional to the square of the token length. An attacker who can supply an untrusted token to this public tokenizer API can force a single request to saturate one CPU core for a prolonged period, degrading availability of any service that syllabifies attacker-controlled text. No authentication, special configuration, or user interaction is required. ## Root Cause The method walks the token in reverse and, on every iteration after the first vowel is seen, evaluates the membership test `char_lower + current_onset[::-1] in self.legal_onsets`. The set `legal_onsets` is built by `onset()`, which returns only the characters up to the first vowel, so every member is vowel-free. For an all-vowel token the first branch can therefore never match, `onset` never becomes `True`, and the reset branch that would clear `current_onset` is never reached. As a result `current_onset` grows by one character on every iteration. Building `current_onset[::-1]` and hashing the resulting string costs O(k) on iteration k, and this is repeated for k from 1 to n, giving total cost O(n^2). The security invariant that is violated is bounded per-token work: there is no length cap on this code path, so untrusted token length translates directly into quadratic CPU consumption. ```text Affected function: LegalitySyllableTokenizer.tokenize Source: nltk/tokenize/legality_principle.py (membership-test sink at line 133; loop over token[::-1] beginning at line 126) Helper establishing the vowel-free onset set: LegalitySyllableTokenizer.onset (nltk/tokenize/legality_principle.py, returns prefix up to first vowel) ``` ## Impact An attacker who controls a token passed to `LegalitySyllableTokenizer.tokenize` can trigger quadratic CPU work. In the reviewed release a token of roughly 64,000 vowel characters takes about 1.8 seconds on a single core, and the cost grows with the square of the length, so a token in the hundreds of kilobytes to megabyte range consumes a core for many seconds to minutes. Memory use is linear. The demonstrated capability is single-core CPU exhaustion leading to denial of service or latency degradation in any network-reachable component that syllabifies untrusted input. There is no confidentiality or integrity impact; the effect is availability degradation of the affected process. The plausible operational consequence, where multiple concurrent requests are used, is exhaustion of the available worker pool; this is inferred from the per-request cost and was not itself executed against a live deployment. ## Proof of Concept `Requires only the released nltk package; no corpus download is needed because the quadratic behavior is driven entirely by the attacker token, not by the size of the legal-onset set.` 1. Construct a tokenizer with any small onset source. 2. Call `tokenize` with an all-vowel token of increasing length and time each call. 3. Compare against a consonant-alternating control token of equal length. ```python import time from nltk.tokenize import LegalitySyllableTokenizer tok = LegalitySyllableTokenizer("tr c d".split()) # tiny 3-word onset source for n in (8000, 16000, 32000): payload = "a" * n start = time.perf_counter() tok.tokenize(payload) print("vowel-run", n, round(time.perf_counter() - start, 3)) control = "ba" * 32000 # equal-length linear control start = time.perf_counter() tok.tokenize(control) print("control", 64000, round(time.perf_counter() - start, 3)) ``` ```text vowel-run 8000 0.031 vowel-run 16000 0.120 vowel-run 32000 0.468 (about 4x per doubling => O(n^2)) control 64000 0.004 (linear, roughly 130x faster at larger size) ``` ## Attack Chain 1. **Exposure:** `LegalitySyllableTokenizer` is exported from `nltk.tokenize` and `tokenize` is a public, documented method reachable by any service that syllabifies untrusted text. 2. **Control:** The attacker fully controls the `token` argument, including its length and character content; a run of vowels such as `"a" * n` survives with no normalization or length reduction. 3. **Path:** The token flows into the reverse walk at `nltk/tokenize/legality_principle.py:126` and reaches the membership-test at line 133 on every iteration past the first vowel. 4. **Guard:** There is no length cap on this path. The sibling `SyllableTokenizer` received a `MAX_TOKEN_LEN` cap during the project hardening work, but `legality_principle.py` received no such guard. 5. **Primitive:** Repeated O(k) construction and hashing of `current_onset[::-1]` inside the loop yields cumulative O(n^2) CPU work. 6. **Result:** A single request with a large vowel-run token exhausts one CPU core for a sustained period, degrading service availability. ## Bypass Evidence No guard blocks this path. Membersh

• github.com/nltk/nltk/security/advisories/GHSA-gpwc-27cw-rh9r (opens in a new tab)
• nvd.nist.gov/vuln/detail/CVE-2026-126301 (opens in a new tab)
• github.com/nltk/nltk/pull/3895 (opens in a new tab)
• github.com/nltk/nltk/commit/78781ba4575d536fb1540897f27baca0fb40617c (opens in a new tab)
• github.com/nltk/nltk/commit/e20c40e26ec9306de885703f6e53250695f1f49b (opens in a new tab)
• github.com/nltk/nltk (opens in a new tab)
• github.com/nltk/nltk/releases/tag/v3.10.4 (opens in a new tab)
• vulncheck.com/advisories/nltk-from-3.6-before-3.10.4-quadratic-cpu-exhaustion-via-legalitysyllabletokenizer-tokenize (opens in a new tab)

• CVE-2026-126304: nltk · Link FollowingHighVulnerability2026-11-13
• CVE-2026-126303: nltk · Uncontrolled Resource ConsumptionHighVulnerability2026-11-13
• CVE-2026-126302: nltk · Link FollowingMediumVulnerability2026-11-13
• CVE-2026-126301: nltk · Inefficient Algorithmic ComplexityMediumVulnerability2026-11-13
• CVE-2026-126300: nltk · Inefficient Algorithmic ComplexityMediumVulnerability2026-11-13