Immutable: Hash-collision algorithmic complexity denial of service in Immutable.Map/Set

Summary

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

• = 4.0.0-beta.1, < 4.3.9

• = 5.0.0-beta.1, < 5.1.8

• < 3.8.4

Patches