I love hashes and hash tables. Always have. I even studied them for extra credit in high school. If you’ll recall, a hash is a one-way mathematical process that reduces any amount of data into a single (typically short) value. When hashes are used as indexes into a dataset, this is called a hash table.
A vulnerability released at 28C3 touches on one of my favorite subjects – hidden algorithmic complexity in a popular data structure. Today’s villain: hash tables
Hash tables are used for high-performance situations because they typically provide the fastest lookup. However, hash tables break down when there are too many hash collisions. Typically, hash collisions in the table are handled by putting a linked list off the hash table and then searching the list. Thus, in situations where there are a lot of hash collisions, the hash table goes from being the fastest possible solution – O(1) – to being bound by the number of nodes in the linked list – O(n). This can be painfully slower to the point of inverting performance: if the number of collisions sufficiently extreme, the CPU can literally spend hours managing the collision list.
And that’s where this neat little vulnerability comes in. At the Chaos Communication Congress in Berlin earlier this month, Alexander Klink and Julian Zeri demonstrated this attack that uses a large input post to contain thousands of keys that hash to the same value so a single post can exploit this inverted performance characteristic.
In this excellent write-up, Klink and Julian Wälde claim that with this attack a mere 30 Kbits/s can keep one Intel™ Core 2 core busy. At 30 Kbits/s a single client can DoS a CPU. An attacker with a gigabit connection could theoretically keep 10,000 Intel™ i7 cores busy. The authors did the right thing and notified the appropriate parties in advance so that patches could be created and released.
But the problem is much broader than just ASP.NET. Check out all the other platforms that have the same problem.
last modified: January 10, 2012