Denial of Service via Algorithmic
Denial of Service via Algorithmic Complexity Attacks:[...]a new class of low-bandwidth denial of service attacks that exploit algorithmic deficiencies in many common applications' data structures. Frequently used data structures have “average-case” expected running time that’s far more efficient than the worst case. For example, both binary trees and hash tables can degenerate to linked lists with carefully chosen input. We show how an attacker can effectively compute such input, and we demonstrate attacks against the hash table implementations in two versions of Perl, the Squid web proxy, and the Bro intrusion detection system. [...] We show how modern universal hashing techniques can yield performance comparable to commonplace hash functions while being provably secure against these attacks.
e.p.c. posted this at 13:44 GMT on 1-Jun-2003 . Archive Link