Hash-Table Attacks in PHP
When I got to implementing #hash tables, the first thing I did was ask an agent to research existing implementations across different languages. I wanted not so much to find the best algorithm, but to understand what kinds of problems other languages had encountered. Choosing an efficient hash-table algorithm has remained a hot topic for many years, simply because there is no universal solution. Depending on the use case, different approaches can differ in performance by 50% or even several times. So the best approach is still to use the algorithm that fits a particular case. But for PHP, that isn't really an option. The same is true for other similar languages that need a universal Swiss Army knife. Then one detail caught my eye: #PHP doesn't use a hash salt. Java, Go, and Python do, but PHP doesn't. Of course, not having a salt is good for performance: that's one less XOR operation on every read/write operation. But why would an array need a salt in the first place? And that's when I learned about this... The attack is called hash flooding. It was publicly demonstrated in 2011 at 28C3 by Klink and Wälde in “Efficient Denial of Service Attacks on Web Application Platforms.” PHP received CVE-2011-4885: https://aegiflow.com/threat-radar/database/cve-2011-4885/ Why does it work? When a collision occurs, inserting each key first requires searching for it in the bucket chain. The while (1) loop in zend_hash_find_bucket follows Z_NEXT from the head to the tail and returns NULL if the key isn't found. When all keys end up in the same bucket, the chain grows to N elements. Inserting the k-th key requires traversing k links, giving us O(N²) complexity. Should you be worried? Modern REST APIs often use JSON. Sending a 2.5 MB JSON body containing 65,000 keys can keep an API request busy for around 30 seconds, which can pose a real threat to production applications. This attack isn't particularly difficult to perform. At the application level, the only practical defense is to limit the size of JSON request bodies. A defense at the PHP level is possible only by adding either a salt or an attack detector directly to Zend's hash table implementation. Perhaps this issue still requires a proper solution.
