Bug 361316

Description Greg Wilkins 2011-10-18 19:41:48 EDT

Andrea Barisani lcars@ocert.org via webtide.com 

Hi,

oCERT recently received a report concerning a Denial Of Service condition which
can be triggered exploiting predictable collisions in hashing algorithms.

The issue is extremely similar to the one reported in 2003 in the paper "Denial
of Service via Algorithmic Complexity Attacks" [1] which was affecting the Perl
language.

In this newly reported scenario exploits multi collisions in hashing functions
of PHP/Java/Python in order to cause a DoS against the storage of key/value
pairs in CGI (POST) parameters.

As an example it has been reported that the attack can amplify 2 MB worth of
specially crafted parameters leading to a 100% of CPU usage which can last from
5 to several hours, depending on the targeted application and server
performance.

Your project Jetty has been reported as vulnerable to such condition and we
can provide you a PoC, if requested, which illustrates the issue. The test
case is created by posting several parameter keys which map to the same hash
code, triggering a large amount of CPU usage and hence causing a DoS
condition.

While we are currently discussing potential fixes in the underlying languages
hash algorithms in order to deal with this scenario we anticipate that in any
case the applications would have to be patched in order to effectively prevent
this possibility. As a language-level fix is still under discussion, and less
likely to be implemented by the respective maintainers, we would favour a fix
at the application-level for the time being.

On Java based applications moving away from HashMap/Hashtable in favour of
TreeMap is reportedly an effective solution.

For applications based on other languages move to a datastructure equivalent to
TreeMap or the implementation of a detection function for an anomalous number
of collisions per bucket would be necessary.

IMPORTANT: The embargo date for this issue has been set to December 27th per
request of the reports (who are going to present a talk regarding this attack
at the CCC event). We would ask you not to release publicly information about
the discussed issue before the specific date.

We would like to coordinate the release of a patch and/or new version of your
project at embargo expiration, it would be beneficial to publish an advisory
referencing the fixed versions when the embargo date is reached.

Please let us know if you have any questions or need any clarifications about
this report and how you would like to go forward.

I am cc'ing the original authors (which will be eventually credited in the
advisory) Alexander Klink <alexander.klink@nruns.com> and Julian Waelde
<jwaelde@cdc.informatik.tu-darmstadt.de>

We are separately contacting the other affected vendors.

Thanks a lot.

References:
[1] http://www.cs.rice.edu/~scrosby/hash/CrosbyWallach_UsenixSec2003.pdf