|
12th USENIX Security Symposium — Abstract
Pp. 29-44 of the Proceedings
Denial of Service via Algorithmic Complexity Attacks
Scott A. Crosby and Dan S. Wallach, Rice University
Abstract
We present 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. Using bandwidth less
than a typical dialup modem, we can bring a dedicated Bro server to
its knees; after six minutes of carefully chosen packets, our Bro
server was dropping as much as 71% of its traffic and consuming all
of its CPU. We show how modern universal hashing techniques can yield
performance comparable to commonplace hash functions while being
provably secure against these attacks.
- View the full text of this paper in HTML and
PDF.
Until August 2004, you will need your USENIX membership identification in order to access the full papers. The Proceedings are published as a collective work, © 2003 by the USENIX Association. All Rights Reserved. Rights to individual papers remain with the author or the author's employer. Permission is granted for the noncommercial reproduction of the complete work for educational or research purposes. USENIX acknowledges all trademarks within this paper.
- If you need the latest Adobe Acrobat Reader, you can download it from Adobe's site.
|
Need help? Use our Contacts page.
