Vulnerability Note VU#903934

Hash table implementations vulnerable to algorithmic complexity attacks

Original Release date: 28 Dec 2011 | Last revised: 15 Feb 2016


Some programming language implementations do not sufficiently randomize their hash functions or provide means to limit key collision attacks, which can be leveraged by an unauthenticated attacker to cause a denial-of-service (DoS) condition.


Many applications, including common web framework implementations, use hash tables to map key values to associated entries. If the hash table contains entries for different keys that map to the same hash value, a hash collision occurs and additional processing is required to determine which entry is appropriate for the key. If an attacker can generate many requests containing colliding key values, an application performing the hash table lookup may enter a denial of service condition.

Hash collision denial-of-service attacks were first detailed in 2003, but recent research details how these attacks apply to modern language hash table implementations.


An application can be forced into a denial-of-service condition. In the case of some web application servers, specially-crafted POST form data may result in a denial-of-service.


Apply an update
Please review the Vendor Information section of this document for vendor-specific patch and workaround details.

Limit CPU time

Limiting the processing time for a single request can help minimize the impact of malicious requests.

Limit maximum POST size

Limiting the maximum POST request size can reduce the number of possible predictable collisions, thus reducing the impact of an attack.

Limit maximum request parameters

Some servers offer the option to limit the number of parameters per request, which can also minimize impact.

Vendor Information (Learn More)

VendorStatusDate NotifiedDate Updated
Apache TomcatAffected-28 Dec 2011
Microsoft CorporationAffected01 Nov 201129 Dec 2011
Oracle CorporationAffected01 Nov 201115 Feb 2016
RubyAffected01 Nov 201128 Dec 2011
The PHP GroupAffected-28 Dec 2011
AdobeUnknown01 Nov 201101 Nov 2011
IBM CorporationUnknown01 Nov 201101 Nov 2011
If you are a vendor and your product is affected, let us know.

CVSS Metrics (Learn More)

Group Score Vector
Base 0.0 AV:--/AC:--/Au:--/C:--/I:--/A:--
Temporal 0.0 E:ND/RL:ND/RC:ND
Environmental 0.0 CDP:ND/TD:ND/CR:ND/IR:ND/AR:ND



Thanks to Alexander Klink and Julian Wälde for reporting these vulnerabilities.

This document was written by Jared Allar and David Warren.

Other Information


If you have feedback, comments, or additional information about this vulnerability, please send us email.