GHSA-XVCM-6775-5M9R
Vulnerability from github – Published: 2026-07-21 19:02 – Updated: 2026-07-21 19:02Summary
Immutable.Map and Immutable.Set keep keys that share the same 32-bit hash in a collision bucket that is scanned linearly. The string hash is public and deterministic, so an attacker who controls the keys inserted into a Map can craft many keys that all collide, degrading insertion and lookup from amortized O(1) to O(n) per operation — and O(n²) to build or read the whole set. A small, attacker-shaped payload can therefore consume disproportionate CPU and, on a single-threaded runtime such as Node.js, stall the event loop and deny service.
Details
The string hash uses the JVM-style polynomial hashed = (31 * hashed + charCode) | 0. Strings such as "Aa" and "BB" hash to the same value (65*31+97 == 66*31+66 == 2112), and concatenating such blocks yields 2^n distinct strings sharing one hash (40 characters ⇒ >1,000,000 colliding keys).
All such keys route to a single HashCollisionNode, whose get/update walk the entire bucket testing is(). There is no per-process salt, so the colliding set is fully precomputable from the open-source algorithm.
Proof of concept
Inserting N colliding keys (e.g. via Immutable.Map(obj) / Immutable.fromJS(obj)) is O(N²). Measured on one machine, ~8,000 colliding
keys take ~0.7 s to build and ~0.6 s to read, scaling ×4 per doubling; ~16,000 keys exceed several seconds.
Impact
CPU-bound denial of service in applications that ingest attacker-controlled object keys into Immutable structures, e.g. Immutable.Map(req.body), Immutable.fromJS(req.body), state.merge(userObject) / mergeDeep(...). Applications that only store attacker input as values under fixed keys are not affected.
Affected versions
All versions through 5.1.7 (the deterministic string hash and linear collision bucket have existed since the 4.x line).
Patches
Fixed in 5.1.8 (adjust to the actual release): large collision buckets are indexed by a per-process seeded secondary hash, restoring near-linear behavior for the affected paths. The public hash() is unchanged (no breaking change), and is() remains the sole authority on key equality.
Workarounds
Before passing untrusted data to Immutable.js: cap request body size, limit object key count/length, and reject high-cardinality payloads; avoid building Maps directly from untrusted object keys.
References
- CWE-407 (Inefficient Algorithmic Complexity), CWE-400 (Uncontrolled Resource Consumption)
- OWASP API4:2023 (Unrestricted Resource Consumption)
{
"affected": [
{
"package": {
"ecosystem": "npm",
"name": "immutable"
},
"ranges": [
{
"events": [
{
"introduced": "0"
},
{
"fixed": "4.3.9"
}
],
"type": "ECOSYSTEM"
}
]
},
{
"package": {
"ecosystem": "npm",
"name": "immutable"
},
"ranges": [
{
"events": [
{
"introduced": "5.0.0-beta.1"
},
{
"fixed": "5.1.8"
}
],
"type": "ECOSYSTEM"
}
]
}
],
"aliases": [
"CVE-2026-59880"
],
"database_specific": {
"cwe_ids": [
"CWE-400",
"CWE-407"
],
"github_reviewed": true,
"github_reviewed_at": "2026-07-21T19:02:33Z",
"nvd_published_at": "2026-07-08T16:16:34Z",
"severity": "HIGH"
},
"details": "## Summary\n\n`Immutable.Map` and `Immutable.Set` keep keys that share the same 32-bit hash in a collision bucket that is scanned linearly. The string hash is public and deterministic, so an attacker who controls the **keys** inserted into a Map can craft many keys that all collide, degrading insertion and lookup from amortized O(1) to O(n) per operation \u2014 and O(n\u00b2) to build or read the whole set. A small, attacker-shaped payload can therefore consume disproportionate CPU and, on a single-threaded runtime such as Node.js, stall the event loop and deny service.\n\n## Details\n\nThe string hash uses the JVM-style polynomial `hashed = (31 * hashed + charCode) | 0`. Strings such as `\"Aa\"` and `\"BB\"` hash to the same value (`65*31+97 == 66*31+66 == 2112`), and concatenating such blocks yields `2^n` distinct strings sharing one hash (40 characters \u21d2 \u003e1,000,000 colliding keys). \nAll such keys route to a single `HashCollisionNode`, whose `get`/`update` walk the entire bucket testing `is()`. There is no per-process salt, so the colliding set is fully precomputable from the open-source algorithm.\n\n## Proof of concept\n\nInserting N colliding keys (e.g. via `Immutable.Map(obj)` / `Immutable.fromJS(obj)`) is O(N\u00b2). Measured on one machine, ~8,000 colliding\nkeys take ~0.7 s to build and ~0.6 s to read, scaling \u00d74 per doubling; ~16,000 keys exceed several seconds.\n\n## Impact\n\nCPU-bound denial of service in applications that ingest attacker-controlled object **keys** into Immutable structures, e.g. `Immutable.Map(req.body)`, `Immutable.fromJS(req.body)`, `state.merge(userObject)` / `mergeDeep(...)`. Applications that only store attacker input as **values** under fixed keys are not affected.\n\n## Affected versions\n\nAll versions through `5.1.7` (the deterministic string hash and linear collision bucket have existed since the 4.x line).\n\n## Patches\n\nFixed in `5.1.8` _(adjust to the actual release)_: large collision buckets are indexed by a per-process **seeded** secondary hash, restoring near-linear behavior for the affected paths. The public `hash()` is unchanged (no breaking change), and `is()` remains the sole authority on key equality.\n\n## Workarounds\n\nBefore passing untrusted data to Immutable.js: cap request body size, limit object key count/length, and reject high-cardinality payloads; avoid building Maps directly from untrusted object keys.\n\n## References\n\n- CWE-407 (Inefficient Algorithmic Complexity), CWE-400 (Uncontrolled Resource Consumption)\n- OWASP API4:2023 (Unrestricted Resource Consumption)",
"id": "GHSA-xvcm-6775-5m9r",
"modified": "2026-07-21T19:02:33Z",
"published": "2026-07-21T19:02:33Z",
"references": [
{
"type": "WEB",
"url": "https://github.com/immutable-js/immutable-js/security/advisories/GHSA-xvcm-6775-5m9r"
},
{
"type": "ADVISORY",
"url": "https://nvd.nist.gov/vuln/detail/CVE-2026-59880"
},
{
"type": "WEB",
"url": "https://github.com/immutable-js/immutable-js/commit/3dd7e5655012597a41873e328bf9142a8901527b"
},
{
"type": "WEB",
"url": "https://github.com/immutable-js/immutable-js/commit/e51d49fc612ded5ec4dfb94ff294d22074269b0f"
},
{
"type": "PACKAGE",
"url": "https://github.com/immutable-js/immutable-js"
},
{
"type": "WEB",
"url": "https://github.com/immutable-js/immutable-js/releases/tag/v4.3.9"
},
{
"type": "WEB",
"url": "https://github.com/immutable-js/immutable-js/releases/tag/v5.1.8"
}
],
"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": "Immutabl: Hash-collision algorithmic complexity denial of service in Immutable.Map/Set"
}
Sightings
| Author | Source | Type | Date | Other |
|---|
Nomenclature
- Seen: The vulnerability was mentioned, discussed, or observed by the user.
- Confirmed: The vulnerability has been validated from an analyst's perspective.
- Published Proof of Concept: A public proof of concept is available for this vulnerability.
- Exploited: The vulnerability was observed as exploited by the user who reported the sighting.
- Patched: The vulnerability was observed as successfully patched by the user who reported the sighting.
- Not exploited: The vulnerability was not observed as exploited by the user who reported the sighting.
- Not confirmed: The user expressed doubt about the validity of the vulnerability.
- Not patched: The vulnerability was not observed as successfully patched by the user who reported the sighting.