When 2 MB of Data Can Take Down a Server: The Hidden Mathematics of Hash Collisions
On December 28, 2011, at the 28th Chaos Communication Congress in Berlin, Alexander Klink and Julian Wälde demonstrated something that sent shockwaves through the software industry. With just 2 megabytes of carefully crafted POST data, they kept a single CPU core busy for over 40 minutes. The attack didn’t exploit buffer overflows or SQL injection—it exploited the fundamental mathematics of hash tables. The technique, dubbed HashDoS, works because hash tables have a worst-case performance that’s dramatically different from their average case. When you understand the mathematics behind this vulnerability, you’ll see why it affected virtually every major programming language and why modern hash table implementations look very different from their predecessors. ...