hash flooding

An attack that sends a server many keys crafted to collide in its hash tables, turning each O(1) operation into O(n) and exhausting its CPU.

A few crafted requests can pin a server's CPU and deny service to everyone else.

In more detail

Inserting n colliding keys costs O(n^2) in total, so a single request of a few hundred kilobytes could keep a web server busy for minutes. In 2011 researchers showed it against Python, Ruby, Java, PHP and others, tracked for Python as CVE-2012-1150. The defence is a secret, per-process random seed mixed into string hashing, so attackers cannot predict which keys collide.

Related terms

Taught in

References