search menu icon-carat-right cmu-wordmark

CERT Coordination Center

Hash table implementations vulnerable to algorithmic complexity attacks

Vulnerability Note VU#903934

Original Release Date: 2011-12-28 | Last Revised: 2016-02-15

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
 
Affected   Unknown   Unaffected

Apache Tomcat

Updated:  December 28, 2011

Status

  Affected

Vendor Statement

No statement is currently available from the vendor regarding this vulnerability.

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

Microsoft Corporation

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

Status

  Affected

Vendor Statement

No statement is currently available from the vendor regarding this vulnerability.

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 http://technet.microsoft.com/en-us/security/advisory/2659883 http://blogs.technet.com/b/srd/archive/2011/12/27/more-information-about-the-december-2011-asp-net-vulnerability.aspx

Oracle Corporation

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

Status

  Affected

Vendor Statement

No statement is currently available from the vendor regarding this vulnerability.

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.

Ruby

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

Status

  Affected

Vendor Statement

No statement is currently available from the vendor regarding this vulnerability.

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

The PHP Group

Updated:  December 28, 2011

Status

  Affected

Vendor Statement

No statement is currently available from the vendor regarding this vulnerability.

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

Adobe

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

Status

  Unknown

Vendor Statement

No statement is currently available from the vendor regarding this vulnerability.

Vendor Information

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

IBM Corporation

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

Status

  Unknown

Vendor Statement

No statement is currently available from the vendor regarding this vulnerability.

Vendor Information

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


CVSS Metrics

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

References

Credit

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: 2011-12-28
Date First Published: 2011-12-28
Date Last Updated: 2016-02-15 20:05 UTC
Document Revision: 40

Sponsored by the Department of Homeland Security Office of Cybersecurity and Communications.