GHSA-GPWC-27CW-RH9R: CVE-2026-126301: Quadratic CPU Exhaustion in NLTK LegalitySyllableTokenizer
CVE-2026-126301: Quadratic CPU Exhaustion in NLTK LegalitySyllableTokenizer Vulnerability ID: GHSA-GPWC-27CW-RH9R CVSS Score: 5.3 Published: 2026-11-13 The Natural Language Toolkit (NLTK) versions 3.6 through 3.10.3
CVE-2026-126301: Quadratic CPU Exhaustion in NLTK LegalitySyllableTokenizer
Vulnerability ID: GHSA-GPWC-27CW-RH9R
CVSS Score: 5.3
Published: 2026-11-13
The Natural Language Toolkit (NLTK) versions 3.6 through 3.10.3 contain an algorithmic complexity vulnerability in the LegalitySyllableTokenizer.tokenize method. When processing tokens composed of continuous runs of vowels, an unguarded string reversal and set membership lookup loop executes in quadratic time relative to the input token length. Remote attackers capable of submitting arbitrary text to applications utilizing this tokenizer can trigger sustained single-core CPU exhaustion and application-level denial of service.
TL;DR
An unguarded loop in NLTK's LegalitySyllableTokenizer.tokenize method causes quadratic O(n^2) CPU exhaustion when processing long vowel sequences, allowing unauthenticated attackers to cause a denial of service.
⚠️ Exploit Status: POC
Technical Details
- CVE ID: CVE-2026-126301 (GHSA-gpwc-27cw-rh9r)
- Weakness Class: CWE-407 (Inefficient Algorithmic Complexity) / CWE-400
- Affected Component: nltk.tokenize.legality_principle.LegalitySyllableTokenizer.tokenize
- CVSS v3.1 / v4.0: 5.3 Medium (v3.1) / 6.9 Medium (v4.0)
- EPSS Score: 0.51% (44.01st Percentile)
- Impact: Single-core CPU Exhaustion / Application Denial of Service
- Exploit Status: Public Proof-of-Concept (PoC) Available
- Patched Version: nltk 3.10.4
Affected Systems
- Python applications and NLP pipelines utilizing nltk.tokenize.LegalitySyllableTokenizer
-
nltk: >= 3.6, < 3.10.4 (Fixed in:
3.10.4)
Code Analysis
Commit: e20c40e
Introduces MAX_TOKEN_LEN = 4096 to LegalitySyllableTokenizer and raises ValueError on oversized tokens.
diff --git a/nltk/tokenize/legality_principle.py b/nltk/tokenize/legality_principle.py
index 928062c258..7d47f54d13 100644
--- a/nltk/tokenize/legality_principle.py
+++ b/nltk/tokenize/legality_principle.py
@@ -62,6 +62,8 @@ class LegalitySyllableTokenizer(TokenizerI):
+ MAX_TOKEN_LEN = 4096
+
def __init__(
self, tokenized_source_text, vowels="aeiouy", legal_frequency_threshold=0.001
@@ -121,6 +123,15 @@ def tokenize(self, token):
:return syllable_list: Single word or token broken up into syllables.
:rtype: list(str)
"""
+ if len(token) > self.MAX_TOKEN_LEN:
+ raise ValueError(
+ f"LegalitySyllableTokenizer: token length exceeds MAX_TOKEN_LEN "
+ f"({self.MAX_TOKEN_LEN}); syllabification is quadratic in the token "
+ "length (CWE-407). Raise MAX_TOKEN_LEN for longer tokens."
+ )
Commit: 78781ba
Bounds current_onset growth and reversal to max_onset length, reducing time complexity from O(n^2) to O(n * max_onset).
diff --git a/nltk/tokenize/legality_principle.py b/nltk/tokenize/legality_principle.py
index 7d47f54d13..db0f817bff 100644
--- a/nltk/tokenize/legality_principle.py
+++ b/nltk/tokenize/legality_principle.py
@@ -123,12 +123,12 @@ def tokenize(self, token):
- # current_onset grows to O(len) and is reversed each iteration, so the
- # loop is O(n**2) on a long token (CWE-407). A real word is short; reject
- # the oversized ones (mirrors SyllableTokenizer.MAX_TOKEN_LEN).
+ # A real word is short; refuse oversized tokens as defence in depth
+ # (mirrors SyllableTokenizer.MAX_TOKEN_LEN) even though the loop below
+ # is linear (CWE-407).
if len(token) > self.MAX_TOKEN_LEN:
raise ValueError(
f"LegalitySyllableTokenizer: token length exceeds MAX_TOKEN_LEN "
- f"({self.MAX_TOKEN_LEN}); syllabification is quadratic in the token "
- "length (CWE-407). Raise MAX_TOKEN_LEN for longer tokens."
+ f"({self.MAX_TOKEN_LEN}); refusing to syllabify an oversized token "
+ "(CWE-407). Raise MAX_TOKEN_LEN for longer tokens."
)
syllables = []
syllable, current_onset = "", ""
vowel, onset = False, False
+ # An onset longer than the longest legal one can never be legal, so stop
+ # growing and reversing current_onset past that length: the loop is then
+ # O(n * max_onset) instead of O(n**2) on a long vowel run (CWE-407).
+ max_onset = max(map(len, self.legal_onsets), default=0)
for char in token[::-1]:
char_lower = char.lower()
if not vowel:
syllable += char
vowel = bool(char_lower in self.vowels)
else:
- if char_lower + current_onset[::-1] in self.legal_onsets:
+ if (
+ len(current_onset) < max_onset
+ and char_lower + current_onset[::-1] in self.legal_onsets
+ ):
syllable += char
current_onset += char_lower
onset = True
elif char_lower in self.vowels and not onset:
syllable += char
- current_onset += char_lower
+ if len(current_onset) < max_onset:
+ current_onset += char_lower
else:
syllables.append(syllable)
syllable = char
Exploit Details
- GitHub Security Advisory: Public advisory containing proof-of-concept verification script demonstrating quadratic CPU growth on all-vowel strings.
Mitigation Strategies
- Upgrade NLTK to version 3.10.4 or higher to incorporate algorithmic linearization and token length limits.
- Enforce strict maximum token length validation at the application boundary prior to invoking NLP tokenization methods.
- Implement exception handling for ValueError around tokenization calls to gracefully handle rejected oversized tokens.
- Configure reverse proxies and API gateways to restrict maximum HTTP request payload sizes.
Remediation Steps:
- Update project dependency specifications (e.g., requirements.txt, pyproject.toml, or Pipfile) to require nltk>=3.10.4.
- Run 'pip install --upgrade "nltk>=3.10.4"' across all affected virtual environments and container images.
- Audit application code calling LegalitySyllableTokenizer.tokenize() to ensure ValueError exceptions are caught and handled appropriately.
- If immediate upgrading is blocked, implement a wrapper function that rejects or truncates tokens exceeding 1,000 characters before passing them to LegalitySyllableTokenizer.
References
- GitHub Security Advisory: GHSA-gpwc-27cw-rh9r
- CVE Record: CVE-2026-126301
- VulnCheck Security Advisory for CVE-2026-126301
- NLTK Upstream Pull Request #3895
- Fix Commit (Token Length Cap): e20c40e26ec9306de885703f6e53250695f1f49b
- Fix Commit (Loop Linearization): 78781ba4575d536fb1540897f27baca0fb40617c
- NLTK Release Tag v3.10.4
- NLTK Upstream Repository
Read the full report for GHSA-GPWC-27CW-RH9R on our website for more details including interactive diagrams and full exploit analysis.
Originally published by Dev.to Security. Aggregated on AIWithGhost for educational purposes — full credit and traffic to the original publisher.