Multiple applications data-driven algorithmic complexity denial of service
| data-algorithmic-complexity-dos (15382) |  Low Risk |
Description:
Applications in software and hardware are made up of one or more algorithms, which specify how they process data. Among other factors, programmers choose specific algorithms based on the time and memory needed to process a typical data set. This attribute of the algorithm is known as its "algorithmic complexity."
If a programmer chooses an algorithm that is inappropriate for the data set, then it is possible for specially-crafted data to consume significantly more resources or time, resulting in a denial of service.
Platforms Affected:
- GNU, glibc 2.2.1
- Larry Wall, Perl 5.6.1
- Larry Wall, Perl 5.8.0
- Linux, Kernel 2.4.20
- Mozilla, Mozilla 1.3.1
- Python Software Foundation, Python 2.3 Beta1
- Tcl Developer Exchange, TCL 8.3.4
- Various vendors, Any application
- Vern Paxson, Bro 0.8a20
Remedy:
Potentially any application may be impacted by this issue. Some affected platforms are listed in the research paper listed in References, and some applications have posted patches or software updates to resolve the denial of service condition.
Consequences:
Denial of Service
References:
- Rice University Department of Computer Science, Technical Report TR-03-416, Denial of Service via Algorithmic Complexity Attacks at http://www.cs.rice.edu/~scrosby/hash/.
- VulnWatch Mailing List, Sat May 17 2003 - 16:12:58 CDT , Algorithmic Complexity Attacks and the Linux Networking Code at http://archives.neohapsis.com/archives/vulnwatch/2003-q2/0073.html.
Reported:
Feb 01, 2003
The information within this database may change without notice. Use of this information constitutes acceptance for use in an AS IS condition. There are NO warranties, implied or otherwise, with regard to this information or its use. Any use of this information is at the user's risk. In no event shall the author/distributor (Internet Security Systems X-Force) be held liable for any damages whatsoever arising out of or in connection with the use or spread of this information.
Copyright (c) 1994-2008 Internet Security Systems, Inc. All rights reserved worldwide.
For corrections or additions please email xforce@iss.net