New MCP server — Bring vulnerability intelligence into your AI
Back to feed

CVE-2021-43854

ExploitedNVDCIRCLENISA

EUVD-2021-0148 · Published Jan 6, 2022

Inefficient Regular Expression Complexity in nltk (word_tokenize, sent_tokenize)

Impact

The vulnerability is present in PunktSentenceTokenizer, sent_tokenize and word_tokenize. Any users of this class, or these two functions, are vulnerable to a Regular Expression Denial of Service (ReDoS) attack.
In short, a specifically crafted long input to any of these vulnerable functions will cause them to take a significant amount of execution time. The effect of this vulnerability is noticeable with the following example:

from nltk.tokenize import word_tokenize

n = 8
for length in [10**i for i in range(2, n)]:
    # Prepare a malicious input
    text = "a" * length
    start_t = time.time()
    # Call `word_tokenize` and naively measure the execution time
    word_tokenize(text)
    print(f"A length of {length:<{n}} takes {time.time() - start_t:.4f}s")

Which gave the following output during testing:

A length of 100      takes 0.0060s
A length of 1000     takes 0.0060s
A length of 10000    takes 0.6320s
A length of 100000   takes 56.3322s
...

I canceled the execution of the program after running it for several hours.

If your program relies on any of the vulnerable functions for tokenizing unpredictable user input, then we would strongly recommend upgrading to a version of NLTK without the vulnerability, or applying the workaround described below.

Patches

The problem has been patched in NLTK 3.6.6. After the fix, running the above program gives the following result:

A length of 100      takes 0.0070s
A length of 1000     takes 0.0010s
A length of 10000    takes 0.0060s
A length of 100000   takes 0.0400s
A length of 1000000  takes 0.3520s
A length of 10000000 takes 3.4641s

This output shows a linear relationship in execution time versus input length, which is desirable for regular expressions.
We recommend updating to NLTK 3.6.6+ if possible.

Workarounds

The execution time of the vulnerable functions is exponential to the length of a malicious input. With other words, the execution time can be bounded by limiting the maximum length of an input to any of the vulnerable functions. Our recommendation is to implement such a limit.

References
For more information

If you have any questions or comments about this advisory:

Technologies

Nltk Nltk

Weaknesses

CWE-400

CVSS scores

  • v3.17.5CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H

MITRE ATT&CK

Inferred

Where this vulnerability fits in an attack

Initial Access Impact

References

Potentially impacted assets

See if this affects your attack surface

Latest trending attack

Criticalyesterday

Google Brotli decoder - Remote Code Execution via compressed requests (Exploitation Check)

This control is the second step of the Patrowl response to CVE-2026-111497 (Node2Shell). It complements the first control of 22 October 2026, which focused on the Node.js runtime, and does not replace it. Why a second control CVE-2026-111497 is an out-of-bounds write in the Google Brotli decoder, the library that decompresses Brotli ("br") data. It was first published as a Node.js vulnerability, because Node.js bundles this decoder. Later publications showed that the flaw is in the library itself. Every product that embeds an affected version of the decoder is concerned, whatever its language or vendor. A public proof of concept demonstrates code execution. Any server that decompresses request bodies sent with "Content-Encoding: br" exposes the decoder to unauthenticated attackers. Known cases include Express 5 and NestJS 11 on Node.js, Koa and Fastify setups, Bun, Envoy and Istio with request decompression enabled, and any application or reverse proxy that decodes Brotli request bodies with an affected library. The flaw also works in the other direction. A malicious server can compromise an unpatched client that decodes a Brotli response, for example Node.js fetch(), Python clients (requests, httpx, aiohttp, Scrapy) with the Brotli or brotlicffi package, or libcurl builds with Brotli support. What this control checks Patrowl sends small, valid Brotli-compressed requests to each asset and observes whether the server decodes them. The check does not depend on the technology: it detects the behaviour, whatever the stack behind it. These requests are what any legitimate client could send. They never reach the vulnerable code path and cannot affect the availability of the service. How to read the result Potentially impacted means the asset decodes Brotli request bodies: the attack surface is exposed. It does not confirm that the asset is vulnerable. The version of the Brotli decoder in use is not visible from the outside. This check covers applications that parse request bodies on their root path. A Not impacted result does not rule out exposure on other routes, nor on the client side. Checking the versions on the servers remains the only exhaustive verification. Affected and fixed versions Google Brotli 1.0.3 to 1.2.0 are affected, fixed in 1.0.10, 1.1.1 and 1.2.1. Fixed releases of the main products embedding it: Node.js 22.23.4, 24.22.1 and 26.12.1 (end-of-life lines 20.x and older and 25.x receive no fix), Bun 1.4.4, Envoy 1.37.8, 1.38.6, 1.39.3 and 1.40.0, Istio 1.29.9, 1.30.6 and 1.31.2, Python Brotli 1.2.1 and brotlicffi 1.2.1.0. Products that link against the system library depend on the Brotli package of the Linux distribution. Recommendations Update every component that embeds the Brotli decoder (only real fix). Start with the assets flagged by this control. Restart the processes after the update. Rebuild containers, single-executable applications and appliances that bundle an affected runtime or library. Reduce the exposure until the update is deployed. Reject requests with "Content-Encoding: br" at the reverse proxy, load balancer or WAF, case-insensitively and including lists such as "gzip, br". On Envoy and Istio, disable request decompression for Brotli. Review outbound calls. List the features that fetch content from servers you do not control, and patch the services that host them first.

Take 15 minutes to discover our platform with our experts

Patrowl Intel platform screenshot