Denial of Service via Algorithmic Complexity Attacks

[Dave Farber <dave () farber net>]

> X-Sender: @ (Unverified)
> Date: Sat, 31 May 2003 10:22:56 -0400
> To: undisclosed-recipient:;
> From: Monty Solomon <monty () roscom com>
> Subject: Denial of Service via Algorithmic Complexity Attacks
>
>
> Denial of Service via Algorithmic Complexity Attacks
>
> Scott A. Crosby
> scrosby () cs rice edu
>
> Dan S. Wallach
> dwallach () cs rice edu
>
> Department of Computer Science, 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.
>
> http://www.cs.rice.edu/~scrosby/hash/CrosbyWallach_UsenixSec2003/index.html
>
> http://www.cs.rice.edu/~scrosby/hash/CrosbyWallach_UsenixSec2003.pdf


-------------------------------------
You are subscribed as interesting-people () lists elistx com
To manage your subscription, go to
 http://v2.listbox.com/member/?listname=ip

Archives at: http://www.interesting-people.org/archives/interesting-people/