Hash table implementations vulnerable to algorithmic complexity attacks

Overview

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.

Description

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.

---

Impact

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.

---

Solution

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

903934

Filter by status: All Affected Not Affected Unknown

Filter by content: __ Additional information available

__ Sort by: Status Alphabetical

Expand all

Javascript is disabled. Click here to view vendors.

Apache Tomcat __ Affected

Updated: December 28, 2011

Status

Affected

Vendor Statement

We have not received a statement from the vendor.

Vendor Information

According to the n.runs AG advisory:
“Tomcat has released updates (7.0.23, 6.0.35) for this issue which limit the number of request parameters using a configuration parameter. The default value of 10.000 should provide sufficient protection.”

Vendor References

• <http://tomcat.apache.org/tomcat-7.0-doc/changelog.html&gt;

Microsoft Corporation __ Affected

Notified: November 01, 2011 Updated: December 29, 2011

Status

Affected

Vendor Statement

We have not received a statement from the vendor.

Vendor Information

Microsoft has released an update to the .NET Framework with Microsoft Security Bulletin MS11-100, which addresses this issue.

Vendor References

• <http://technet.microsoft.com/en-us/security/bulletin/ms11-100.mspx&gt;
• <http://technet.microsoft.com/en-us/security/advisory/2659883&gt;
• <http://blogs.technet.com/b/srd/archive/2011/12/27/more-information-about-the-december-2011-asp-net-vulnerability.aspx&gt;

Oracle Corporation __ Affected

Notified: November 01, 2011 Updated: February 15, 2016

Status

Affected

Vendor Statement

We have not received a statement from the vendor.

Vendor Information

We are not aware of further vendor information regarding this vulnerability.

Addendum

New information regarding this vulnerability in Java 8 was provided in Februrary 2016, which was sent to Oracle for review.

If you have feedback, comments, or additional information about this vulnerability, please send us [email](<mailto:[email protected]?Subject=VU%23903934 Feedback>).

Ruby __ Affected

Notified: November 01, 2011 Updated: December 28, 2011

Status

Affected

Vendor Statement

We have not received a statement from the vendor.

Vendor Information

According to the n.runs AG advisory:
“CRuby and JRuby provide updates for this issue with a randomized hash function (CRuby 1.8.7-p357, JRuby 1.6.5.1, CVE-2011-4815).”

Vendor References

• <http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/391606&gt;

The PHP Group __ Affected

Updated: December 28, 2011

Status

Affected

Vendor Statement

We have not received a statement from the vendor.

Vendor Information

According to the n.runs AG advisory:
“PHP 5 uses the DJBX33A (Dan Bernstein’s times 33, addition) hash function and parses POST form data into the $_POST hash table. Because of the structure of the hash function, it is vulnerable to an equivalent substring attack.”

From the Workarounds section:
“The easiest way to reduce the impact of such an attack is to reduce the CPU time that a request is allowed to take. For PHP, this can be configured using the max_input_time parameter.”

PHP 5.4.0 RC4 has been released which adds a max_input_vars directive to help mitigate hash collision attacks. Please note that this is a release candidate, not a stable release.

Vendor References

• <http://www.php.net/archive/2011.php#id2011-12-25-1&gt;

Adobe Unknown

Notified: November 01, 2011 Updated: November 01, 2011

Status

Unknown

Vendor Statement

We have not received a statement from the vendor.

Vendor Information

We are not aware of further vendor information regarding this vulnerability.

IBM Corporation Unknown

Notified: November 01, 2011 Updated: November 01, 2011

Status

Unknown

Vendor Statement

We have not received a statement from the vendor.

Vendor Information

We are not aware of further vendor information regarding this vulnerability.

CVSS Metrics

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

References

• <http://www.ocert.org/advisories/ocert-2011-003.html&gt;
• <http://www.nruns.com/_downloads/advisory28122011.pdf&gt;
• <http://www.cs.rice.edu/~scrosby/hash/CrosbyWallach_UsenixSec2003.pdf&gt;
• <http://technet.microsoft.com/en-us/security/bulletin/ms11-100.mspx&gt;

Acknowledgements

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

This document was written by Jared Allar and David Warren.

Other Information

CVE IDs:	CVE-2011-4815, CVE-2011-3414, CVE-2011-4838, CVE-2011-4885
Severity Metric:	10.80 Date Public: