The real problem of the hash table dos attack

December 29, 2011 at 6:20 PM - by Freek Lijten - 1 comment

Tags: Security, opinion, algorithm

The attack that was disclosed earlier this month uses the fact that keys that are inserted into a hash table may have collisions in their hashes. If the linked list of a single hash grows and grows the hash table suddenly becomes very inefficient. So if you choose your keys right you can slow down a hash table and that is exactly what this attack expoits. A hash table scales very well, a linked list however does not.

I will not go into further detail on the attack here, feel free to check this article for a complete explanation of the attack. It is even better download the video of the presentation (via torrent) trough this link. Both are very interesting and recommended. Interesting they may be, but I want to address what in my opinion is the real problem: The way the communication around it was handled by different projects and the fact that the exploit could still exist at all.

The real problem

Perl had this fixed in 2003. Two. thousand. and. three! Eight years ago this was discovered, yet almost no language picked this up and fixed this. It seems that only Ruby reacted on the Perl fix from 2003 although it took them 5 years. Maybe the attack didn't get as much attention in 2003 as it does now, but it still baffles me that this could happen. I don't know if oCERT even existed back then, but you would think this kind of news would spread out beyond the Perl community.

The real real problem?

In the presentation Wälde and Klink talk about their disclosure process. The PHP project had them wait 3 weeks for a first response while this is obviously a serious matter. Only after a reminder they got a reaction stating:

We are looking into it. Changing the core hash function in PHP isn't a trivial change and it will take us some time

Fair enough you might think. So communication could have been way better but at least it is a start. Sadly Wälde and Klink noticed later on that a commit had been made to PHP's 5.4 branch with a fix and a very clear message that this was to prevent hash collision attacks. Now this is good from a security point of view but they took the risk of disclosing the potential attack which is not very nice. First of all because credit needs to go where and when credit is due, but even more because other parties might not have had their own fix in place. Again no communication that a fix had been commited from PHP's side, which is rude to say the least.

PHP is not alone in this though. Java has the same vulnerabilities. Wälde and Klink talk about tomcat having a quick-fix in place already, but glassfish will "fix this in a future version". Even worse, Oracle stated the following:

As for java itself, it does not seem like there is anything that would require a change in Java hashmap implementation.

Right...

Python was also notified and here to, they received no reaction whatsoever. After the same reminder three weeks later, they received a reaction stating that there notification got stuck in moderation queue and would have to wait a couple of more days due to the thanksgiving holiday.

Right...

At the moment of the talk, another couple of weeks later, there was still no reaction and no fix in place. 

To be fair, Microsoft handled the attack disclosure very well according to Wälde and Klink. The Ruby security team appeared to be very helpful as well. To me it is appalling that other parties where so negligent in their reactions. You would think that someone kind enough to give you time to fix a serious expoit should deserve a little more attention.

Conclusion

This attack was the result of good research and it is important that it is disclosed. More importantly however is the fact that organisation got by with years of not noticing it and even worse, reacted very poor after being informed. I can't say I have a ready solution to avoid these kind of things in the future, perhaps that will prove to be an interesting discussion :) I would be very happy to hear your opinion on this in the comments below.

If you want to see the full talk here is the torrent link once again.

Thanks for bearing with my rant.