Lesson 4 of 81953–20118 min
Hash tables
In December 2011, at the Chaos Communication Congress in Berlin, Alexander Klink and Julian Wälde showed that many web platforms (PHP, Java, ASP.NET, Python and others) could be knocked over with a single request. They sent form parameters whose names had been chosen to land in the same slot of the server's hash table, turning each lookup from constant time into a linear scan and the request into quadratic work.
The fix was to make the hash function unpredictable. Python added hash randomisation and turned it on by default in version 3.3. The episode is a lesson in how much the speed of a hash table depends on assumptions about its keys.
The rest of this lesson is part of Pro
Create a free account to read the first lesson of every path, and go Pro for the rest.
Sources
- oCERT-2011-003: multiple implementations denial-of-service via hash algorithm collision — oCERT
- PYTHONHASHSEED (command line and environment) — Python documentation
- Mapping Types: dict — Python documentation
- Algorithms, 4th edition, §3.4 Hash Tables — R. Sedgewick and K. Wayne, Princeton University