[REVS] Denial of Service via Algorithmic Complexity Attacks
From: SecuriTeam (support_at_securiteam.com)
Date: 05/31/03
- Previous message: SecuriTeam: "[NT] Multiple Vulnerabilities Found in Forums Web Server"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
To: list@securiteam.com Date: 31 May 2003 14:48:23 +0200
The following security advisory is sent to the securiteam mailing list, and can be found at the SecuriTeam web site: http://www.securiteam.com
- - promotion
In the US?
Contact Beyond Security at our new California office
housewarming rates on automated network vulnerability
scanning. We also welcome ISPs and other resellers!
Please contact us at: 323-882-8286 or ussales@beyondsecurity.com
- - - - - - - - -
Denial of Service via Algorithmic Complexity Attacks
------------------------------------------------------------------------
SUMMARY
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 is 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.
DETAILS
Introduction:
When analyzing the running time of algorithms, a common technique is to
differentiate best-case, common-case, and worst-cast performance. For
example, an unbalanced binary tree will be expected to consume O(nlogn)
time to insert n elements, but if the elements happen to be sorted
beforehand, then the tree would degenerate to a linked list, and it would
take O(n^2) time to insert all n elements. Similarly, a hash table would
be expected to consume O(n) time to insert n elements. However, if each
element hashes to the same bucket, the hash table will also degenerate to
a linked list, and it will take O(n^2) time to insert n elements.
While balanced tree algorithms, such as red-black trees, AVL trees, and
traps can avoid predictable input that causes worst-case behavior, and
universal hash functions can be used to make hash functions that are not
predictable by an attacker, many common applications use simpler
algorithms. If an attacker can control and predict the inputs being used
by these algorithms, then the attacker may be able to induce the
worst-case execution time, effectively causing a denial-of-service (DoS)
attack.
Such algorithmic DoS attacks have much in common with other low-bandwidth
DoS attacks, such as stack smashing or the ping-of-death, wherein a
relatively short message causes an Internet server to crash or misbehave.
While a variety of techniques can be used to address these DoS attacks,
common industrial practice still allows bugs like these to appear in
commercial products. However, unlike stack smashing, attacks that target
poorly chosen algorithms can function even against code written in safe
languages. One early example was discovered by Garfinkel, who described
nested HTML tables that induced the browser to perform super-linear work
to derive the tables' on-screen layout. More recently, Stubblefield and
Dean described attacks against SSL servers, where a malicious web client
can coerce a web server into performing expensive RSA decryption
operations. They suggested the use of crypto puzzles to force clients to
perform more work before the server does its work. Provably requiring the
client to consume CPU time may make sense for fundamentally expensive
operations like RSA decryption, but it seems out of place when the
expensive operation (e.g., HTML table layout) is only expensive because a
poor algorithm was used in the system. Another recent paper is a toolkit
that allows programmers to inject sensors and actuators into a program.
When a resource abuse is detected, an appropriate action is taken.
This paper focuses on DoS attacks that may be mounted from across a
network, targeting servers with the data that they might observe and store
in a hash table as part of their normal operation. Section 2 details how
hash tables work and how they can be vulnerable to malicious attacks.
Section 3 describes vulnerabilities in the Squid web cache, the DJB DNS
server, and Perl's built-in hash tables. Section 4 describes
vulnerabilities in the Bro intrusion detection system. Section 5 presents
some possible solutions to our attack. Finally, Section 6 gives our
conclusions and discusses future work.
Vulnerable products (found so far):
High:
* Bro 0.8a20
Confirmed vulnerable. Please see the paper. A patch exists and a fixed
release will be out soon. Bro does not crash, but drop rates of 70% are
experienced with an attack traffic as low as 16kbits/sec.
Medium-Low:
These are scripting languages or infrastructure libraries that are
vulnerable, but the impact of attack depends on how they are used. In some
cases, they may be important vulnerabilities, in other cases, irrelevant.
Please see our analysis of Perl in the paper, the same applies to all of
these.
* Python 2.3b1
* TCL 8.4.3
* Perl 5.6.1 and 5.8.0
* glib 2.2.1
* Mozilla 1.3.1
Low:
These are appear to be subject to a weak attack.
* DJBDNS 1.05
The DNS cache has an explicit limit to stop degradation from being more
severe than 100x on the hash table.
* Linux 2.4.20 dcache
Confirmed - the degradation requires the ability to construct files and is
about 200x, but appears small in absolute terms.
* Perl 5.6.1
Confirmed Insert all 10,000 strings into an associative array. See
<http://www.cs.rice.edu/~scrosby/hash/attack/blowout.pl> victim program
* Perl 5.8.0
Confirmed Insert all 10,000 strings into an associative array. See
<http://www.cs.rice.edu/~scrosby/hash/attack/blowout.pl> victim program
* Linux dcache 2.4.20
Confirmed Make a directory with filenames equal to those in this file. I
recommend using a cut-down subset, quadratic behavior seems to cease at
only a few thousand entries.
* Bro IDS 0.8a20
Confirmed forthcoming As the attack is rather severe, it will take some
time to manufacture an appropriately cut down file.
* Python 2.3b1
This corrected file is from "Alexis S. L. Carvalho" , and demonstrates the
attack.
* GLIB 2.2.1
A <http://www.cs.rice.edu/~scrosby/hash/attack/blowout-glib.c> test
program, also by "Alexis S. L. Carvalho" shows a degradation on this file.
ADDITIONAL INFORMATION
The complete article in HTML is available for download from:
<http://www.cs.rice.edu/~scrosby/hash/CrosbyWallach_UsenixSec2003/index.html> http://www.cs.rice.edu/~scrosby/hash/CrosbyWallach_UsenixSec2003/index.html
The complete article in PDF is available for download from:
<http://www.cs.rice.edu/~scrosby/hash/CrosbyWallach_UsenixSec2003.pdf>
http://www.cs.rice.edu/~scrosby/hash/CrosbyWallach_UsenixSec2003.pdf
The information has been provided by Scott A Crosby and Dan S Wallach.
========================================
This bulletin is sent to members of the SecuriTeam mailing list.
To unsubscribe from the list, send mail with an empty subject line and body to: list-unsubscribe@securiteam.com
In order to subscribe to the mailing list, simply forward this email to: list-subscribe@securiteam.com
====================
====================
DISCLAIMER:
The information in this bulletin is provided "AS IS" without warranty of any kind.
In no event shall we be liable for any damages whatsoever including direct, indirect, incidental, consequential, loss of business profits or special damages.
- Previous message: SecuriTeam: "[NT] Multiple Vulnerabilities Found in Forums Web Server"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Relevant Pages
|
