[VulnDiscuss] Re: Algorithmic Complexity Attacks and the Linux Networking Code

On Saturday 17 May 2003 23:12, Florian Weimer wrote:

looks like there is another patch for that problem inlcuded in

linux-2.4.21-rc2

from the changelog:

  o [NET]: Fix hashing exploits in ipv4 routing, IP conntrack, and TCP synq

But it looks like this patch is not the same as the one from redhat.

>          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).
>
> Countermeasures
>
>    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
>    size.
>
> 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
>        scrutinized.
>
>      * 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
>        it.
>
>      * 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.
>
> References
>
>      * Scott A. Crosby, Dan S. Wallach, Denial of Service via
>        Algorithmic Complexity Attacks
>       
> <http://www.cs.rice.edu/~scrosby/hash/CrosbyWallach_UsenixSec2003/index.htm
>l>
>
>      * 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>
>
>      * Most current version of this document
>        <http://www.enyo.de/fw/security/notes/linux-dst-cache-dos.html>

-- 
e-admin internet gmbh
Andreas Gietl                                            tel +49 941 3810884
Ludwig-Thoma-Strasse 35                      fax +49 89 244329104
93051 Regensburg                                  mobil +49 171 6070008

PGP/GPG-Key unter http://www.e-admin.de/gpg.html