From the advisory: Algorithmic Complexity Attacks and the Linux Networking Code The Linux networking code makes extensive use of hash tables to implement caches to support packet classification. One of these caches, the routing cache, can be used to mount effective denial of service attacks, using an algorithmic complexity attack. The Linux Routing Cache The routing cache (or "dst cache") caches routing decisions for a traffic flow. A traffic flow consists of packets which have the same IPv4 source and destination address and the same TOS value in the IP header. These flows are unidirectional; for a two-way communication, two flows exist, one in each direction. Even if the cache is also called "dst cache" for historical reasons, the cache covers more than just destination addresses. When a packet arrives, the kernel must route it. The IP routing code checks for a suitable traffic flow and reuses the cached routing decisions, if possible. Otherwise, it makes a new routing decision and creates a new traffic flow, by updating the routing cache accordingly. This routing occurs on single-homed host with disabled IP forwarding as well as on full-table routers. The routing cache is implemented as a hash table, in a rather particular way. The bucket count is an integral power of two which is fixed on system boot and scaled according to the amount of physical RAM. The hash function is GF(2)-linear (which means that it is easy to find collisions). Collision chaining is used to store different entries which hash to the same bucket. A garbage collection mechanism ensures that the size of the cache stays below the configured maximum entry count. This entry count is scaled with available system memory, too. Note that there are additional hash tables in the networking code. For example, IP connection tracking adds an additional hash table (which uses a different, but still rather weak hash table). Reproducible: Always Steps to Reproduce: References: * This is issue has been assigned the name CAN-2003-0244 by the Common Vulnerability and Exposures dictionary. http://cve.mitre.org/cgi-bin/cvename.cgi?name=CAN-2003-0244 * Scott A. Crosby, Dan S. Wallach, Denial of Service via Algorithmic Complexity Attacks http://www.cs.rice.edu/~scrosby/hash/CrosbyWallach_UsenixSec2003/index.html * Red Hat, Updated 2.4 kernel fixes security vulnerabilities and various bugs https://rhn.redhat.com/errata/RHSA-2003-172.html * The patch for Linux 2.4.20 that has been published by Red Hat http://www.enyo.de/fw/security/notes/linux-2.4.20-nethashfix.patch
Note: The redhat patches also fix the following: > A flaw has been found in the "ioperm" system call, which fails to properly > restrict privileges. This flaw can allow an unprivileged local user to > gain read and write access to I/O ports on the system. The Common > Vulnerabilities and Exposures project (cve.mitre.org) has assigned the name > CAN-2003-0246 to this issue.
*** This bug has been marked as a duplicate of 21076 ***
