REDHAT-BUG-750533

First published: Tue Nov 01 2011(Updated: )

Julian Wälde and Alexander Klink reported that the String.hashCode() hash function is not sufficiently collision resistant. hashCode() value is used in the implementations of HashMap and Hashtable classes: <a href="http://docs.oracle.com/javase/6/docs/api/java/util/HashMap.html">http://docs.oracle.com/javase/6/docs/api/java/util/HashMap.html</a> <a href="http://docs.oracle.com/javase/6/docs/api/java/util/Hashtable.html">http://docs.oracle.com/javase/6/docs/api/java/util/Hashtable.html</a> A specially-crafted set of keys could trigger hash function collisions, which can degrade performance of HashMap or Hashtable by changing hash table operations complexity from an expected/average O(1) to the worst case O(n). Reporters were able to find colliding strings efficiently using equivalent substrings and meet in the middle techniques. This problem can be used to start a denial of service attack against Java applications that use untrusted inputs as HashMap or Hashtable keys. An example of such application is web application server (such as tomcat, see <a class="bz_bug_link bz_status_CLOSED bz_closed bz_public " title="CLOSED ERRATA - CVE-2011-4858 tomcat: hash table collisions CPU usage DoS (oCERT-2011-003)" href="show_bug.cgi?id=750521">bug #750521</a>) that may fill hash tables with data from HTTP request (such as GET or POST parameters). A remote attack could use that to make JVM use excessive amount of CPU time by sending a POST request with large amount of parameters which hash to the same value. This problem is similar to the issue that was previously reported for and fixed in e.g. perl: <a href="http://www.cs.rice.edu/~scrosby/hash/CrosbyWallach_UsenixSec2003.pdf">http://www.cs.rice.edu/~scrosby/hash/CrosbyWallach_UsenixSec2003.pdf</a>

Never miss a vulnerability like this again

Sign up to SecAlerts for real-time vulnerability data matched to your software, aggregated from hundreds of sources.

Read MoreStart Free Trial

• collector/redhat-bugzilla
• alias/CVE-2012-2739
• agent/last-modified-date
• agent/first-publish-date
• agent/type
• agent/severity
• agent/description
• agent/references
• agent/event
• agent/softwarecombine
• agent/tags
• agent/guess-ai
• agent/software-canonical-lookup
• agent/software-canonical-lookup-request
• vendor/oracle
• canonical/java
• vendor/apache
• canonical/tomcat