Community
Participate
Working Groups
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
Andrea, Thanks for the report. Note that with Jetty, by default we limit the form content to be 8K in the URI and 200K in body content. Can you advise if the CPU usage grows linearly or greater with the size of the form? ie is a limited form size a moderate initial defence? Could you provide a list (or generator) of example keys that hash to the same value so that we may perform our own testing of impacts. We understand that such a list should not be widely distributed, but anybody with knowledge of this attack could generate such a list without much effort. Note also, that I would assume similar attacks can be mounted on HTTP headers and Cookies, although the later two are also size limited. Knowing the performance curve against size would be very good. I would also expect that many applications might also be vulnerable, specially ones that use JSON (or similar) to parse user supplied data into Maps of Maps. I would suggest that you raise this issue with the commonly supplied JSON libraries as well. Do you yet have any idea of what approach could possibly be implemented in the JVM to alleviate this? Would runtime selection of some random element to the hash algorithm be sufficient (although long running applications would be vulnerable to having the "frequency of their shields" discovered by the Klingons).
We have implemented a maxFormKeys configuration (default 1000) on the ContextHandler, which reduces the number of keys that can be added to the map, and thus reduces the impact of bad keys. The testing we did shows that severe non-linear impacts only occur after approx 10000 keys. The Multipart filter has been similarly updated. The jetty-8 servlet 3.0 multipart handling needs to be updated
*** Bug 367733 has been marked as a duplicate of this bug. ***
See also https://bugs.eclipse.org/bugs/show_bug.cgi?id=367638
Fixed for jetty-7.6.0.RC4 and jetty-8.1.0.RC4.
I don't see the difference between this bug and bug 367638. Are you talking about the same fix in both cases (maxFormKeys)?
Also, is there any workaround we can do on the Equinox side for Indigo stream where we are using an old Jetty 6? Or would you need to expose the same configurable property (and default upper bound) there first?
Is it time to turn off the "committer-only" flag?
(In reply to comment #8) > Is it time to turn off the "committer-only" flag? Ping?
why does the same bug have so many instances...I cleared that flag on the other one a while back, didn't realize this one was here.
