[VulnWatch] Algorithmic Complexity Attacks and the Linux Networking Code

From: Florian Weimer (fw_at_deneb.enyo.de)
Date: 05/17/03

  • Next message: Andreas Constantinides: "[VulnWatch] Plaintext Password in Settings.ini of CesarFTP"
    To: vulnwatch@vulnwatch.org
    Date: Sat, 17 May 2003 23:12:58 +0200

             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).

    The Attack

       Our attack is targeted at a host and uses packets with carefully
       chosen source addresses and TOS values to trigger collisions in the
       lower bits of the routing cache hash function. (Note that these
       collisions have nothing to do with colliding packets on the wire.)
       As a result, all these packets create distinct flows which are
       stored in a linear list hooked to a single bucket to a hash table.
       In essence, this reduces the hash table to a linear list, and
       finding entries becomes extremely expensive when the list is very
       long. (This effect is detailed in the paper cited below.)

       The effectiveness of the attack depends significantly on the
       maximum size of routing cache. As described above, the default
       maximum size depends on the amount of physical RAM present in the
       machine. Therefore, machines with more RAM are more vulnerable if
       they operate in the default configuration. For example, we were
       able to freeze a machine with four gigabytes of RAM with a stream
       of about 400 packets per second. (The same machine remained
       unaffected when we used random source addresses instead of source
       addresses that lead to collisions in the hash function.)

       Of course, the hash function is extremely simple, but this is not
       source of the problem. Even though it is possible to find
       collisions by solving a rather small system of linear equations
       over the field of two elements, the main problem results from the
       fact that the attacker can determine the hash bucket for traffic
       flows (and send packets based on that information).


       Red Hat published a security advisory which includes a patch (see
       below) which changes the hash function to a non-linear, keyed hash
       function. While the the hash function is not cryptographically
       strong, it is certainly much more complicated (if not even
       impossible) for an attacker to trigger collisions. (As an
       additional protection, the key is changed every ten minutes.) In
       our experience, the patch, applied to stock Linux 2.4.20, works
       reasonably well in typical denial of service situations.

       If you cannot apply the patch and are confronted with an attack of
       this type, there are two options to protect machines: setting rate
       limits using iptables, or decreasing the routing cache size.
       Choosing suitable rate limits is very complicated, so it is not
       recommended. You can decrease the routing cache size using the
       /proc interface. (If the total size of the cache is reduced, the
       maximum length of a collision chain is reduced, too, and this
       particular attack is no longer possible.) As root, run the
       following commands:

    # echo 4096 > /proc/sys/net/ipv4/route/max_size
    # echo 2048 > /proc/sys/net/ipv4/route/gc_thresh

       (On most systems, you can edit /etc/sysctl.conf to make these
       changes permanent.)

       However, note that this approach of decreasing the cache size has a
       severe impact on routing performance if the number of parallel
       flows processed by the machine exceeds the maximum routing cache

    Frequently Asked Questions

         * How significant is this problem?

           The Linux IP stack is not very robust against various types of
           denial of service attacks. As a result, this problem is
           unlikely to have any practical consequences. We recommend to
           apply the patch to fix this problem during routine maintenance
           and not to change the maximum routing cache size preventively
           because of the potential performance impact.

         * Are other vendors affected by the problem?

           At this time, we do not believe that Cisco IOS routers or
           machines running Solaris or one of the BSD variants are
           affected. However, only source code inspection can reveal if a
           product is affected, and vendors are encouraged to verify that
           their products are unaffected. Flow-based routing using hash
           tables is particularly prone to this vulnerability, and
           implementations of this principle should therefore be

         * Is exploit code available publicly?

           To our knowledge, this kind of attack is currently (May 2003)
           not in the wild, and no widely available attack tools support

         * Does this attack affect only affects routers?

           No, it is also relevant for hosts. The routing cache includes
           both source and destination addresses, and it is possible to
           spoof source addresses accordingly. However, routers are at
           somewhat greater risk because to attack them, you can choose
           the destination addresses in a way that trigger collisions
           which does not require root privileges (or special IP packet
           generation code) on the attacking host.

         * I've read that it is impossible to spoof source addresses on the
           current Internet, thanks to ingress filtering, so this attack is
           not a problem, right?

           While proper ingress (and egress) filtering is a standard
           practice to reduce source address spoofing, it isn't
           universally applied throughout the Internet. A lot of denial
           of service attacks still use spoofed source addresses and
           arrive at the intended victim.

         * Is it possible to use rate limits to counter the attack?

           It is possible, but not recommended. To protect machines which
           large amounts of memory in default configurations, ridiculously
           low rate limits would be required which would enable denial of
           service attacks on their own. Note that all rate limits which
           protect the routing cache have to be applied in the PREROUTING
           chain, as the standard INPUT chain is processed after a packet
           has already updated the routing cache.

         * Netfilter connection tracking uses a huge hash table as well.
           Is it affected?

           Yes, we believe that it is affected by the essentially same
           problem. The Red Hat patch corrects Netfilter connection
           tracking, too.

         * Will the Red Hat patch fix other performance issues with the
           routing cache?

           Unfortunately, the answer is no. We now have multiple reports
           that Linux routers break down according to the inefficiency of
           the routing cache under stress, at incredible low packet rates.
           These problems continue to exist and are likely to persist
           until the kernel developers eliminate the routing cache.

         * Why took it so long before this bug was fixed?

           Kernel developers were contacted at the beginning of April,
           when the issue was independently discovered in the Linux
           kernel, not in February, when the first technical report was
           written by Scott Crosby and Dan Wallach.


         * Scott A. Crosby, Dan S. Wallach, Denial of Service via
           Algorithmic Complexity Attacks

         * Red Hat, Updated 2.4 kernel fixes security vulnerabilities and
           various bugs

         * The patch for Linux 2.4.20 that has been published by Red Hat

         * Most current version of this document

  • Next message: Andreas Constantinides: "[VulnWatch] Plaintext Password in Settings.ini of CesarFTP"

    Relevant Pages

    • [UNIX] Algorithmic Complexity Attacks and the Linux Networking Code
      ... The following security advisory is sent to the securiteam mailing list, and can be found at the SecuriTeam web site: http://www.securiteam.com ... The Linux networking code makes extensive use of hash tables to implement ... algorithmic complexity attack. ... The routing cache caches routing decisions for a traffic ...
    • Re: If not readdir() then what?
      ... All we have to do is cache the open files. ... We keep these in an LRU list and a hash table. ... hash LRU chain, but rather a number of LRU chains. ... Have a rbtree for storing directory entries. ...
    • Re: If not readdir() then what?
      ... Unfortunately, in the NFS case if there are hash collisions, under the ... sequence number when adding new entries). ... the first problem you'll run into is that ext3 doesn't store ... directories in the page cache. ...
    • problem using both Memoize::Expire and DB_File
      ... Subroutine 'test0' is memoized via a simple cache, 'test1' uses a disk-backed cache, 'test2' uses an expiring cache, and 'test3' uses both. ... } my %test0_hash; memoize 'test0', ...
    • soft cache
      ... on of solutions to this problem is weak hash tables -- they do not prevent ... it gives no guarantee how long entries stay in cache. ... HT just points to entry in LRU singly linked list, ...