Algoritmic Complexity Attacks and 2.4.20 the dcache code

Algoritmic Complexity Attacks and 2.4.20 the dcache code

Post by Scott A Crosb » Fri, 30 May 2003 22:50:11



Hello. We have analyzed this software to determine its vulnerability
to a new class of DoS attacks that related to a recent paper. ''Denial
of Service via Algorithmic Complexity Attacks.''

This paper discusses a new class of denial of service attacks that
work by exploiting the difference between average case performance and
worst-case performance. In an adversarial environment, the data
structures used by an application may be forced to experience their
worst case performance. For instance, hash tables are usually thought
of as being constant time operations, but with large numbers of
collisions will degrade to a linked list and may lead to a 100-10,000
times performance degradation. Because of the widespread use of hash
tables, the potential for attack is extremely widespread. Fortunately,
in many cases, other limits on the system limit the impact of these
attacks.

To be attackable, an application must have a deterministic or
predictable hash function and accept untrusted input. In general, for
the attack to be signifigant, the applications must be willing and
able to accept hundreds to tens of thousands of 'attack
inputs'. Because of that requirement, it is difficult to judge the
impact of these attack without knowing the source code extremely well,
and knowing all ways in which a program is used.

As part of this project, one of the applications examined was the
linux kernel 2.4.20, both the networking stack (subject of another
email) and in this email, the dcache.

I have confirmed via an actual attack that it is possible to force the
dcache to experience a 200x performance degradation if the attacker
can control filenames. On a P4-1.8ghz, the time to list a directory of
10,000 files is 18 seconds instead of .1 seconds.

The solution for these attacks on hash tables is to make the hash
function unpredictable via a technique known as universal
hashing. Universal hashing is a keyed hash function where, based on
the key, one of a large set hash functions is chosen. When
benchmarking, we observe that for short or medium length inputs, it is
comparable in performance to simple predictable hash functions such as
the ones in Python or Perl. Our paper has graphs and charts of our
benchmarked performance.

I highly advise using a universal hashing library, either our own or
someone elses. As is historically seen, it is very easy to make silly
mistakes when attempting to implement your own 'secure' algorithm.

The abstract, paper, and a library implementing universal hashing is
available at   http://www.cs.rice.edu/~scrosby/hash/.

Scott
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in

More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

 
 
 

Algoritmic Complexity Attacks and 2.4.20 the dcache code

Post by David S. Mille » Sat, 31 May 2003 06:10:07



> I highly advise using a universal hashing library, either our own or
> someone elses. As is historically seen, it is very easy to make silly
> mistakes when attempting to implement your own 'secure' algorithm.

Why are you recommending this when after 2 days of going back
and forth in emails with me you came to the conclusion that for
performance critical paths such as the hashes in the kernel the Jenkins
hash was an acceptable choice?

It is unacceptably costly to use a universal hash, it makes a multiply
operation for every byte of key input plus a modulo operation at the
end of the hash computation.  All of which can be extremely expensive
on some architectures.

I showed and backed this up for you with benchmarks comparing your
universal hashing code and Jenkins.

Some embedded folks will have your head on a platter if we end up using
a universal hash function for the DCACHE solely based upon your advice.
:-)

--

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in

More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

 
 
 

Algoritmic Complexity Attacks and 2.4.20 the dcache code

Post by Ingo Molna » Sat, 31 May 2003 06:10:07



Quote:> I have confirmed via an actual attack that it is possible to force the
> dcache to experience a 200x performance degradation if the attacker can
> control filenames. On a P4-1.8ghz, the time to list a directory of
> 10,000 files is 18 seconds instead of .1 seconds.

are you sure this is a big issue? Kernel 2.0 (maybe even 2.2) lists 10,000
files at roughly the same speed (18 seconds) without any attack pattern
used for filenames - still it's a kernel being used.

the network hash collision was a much more serious issue, because it could
be triggered externally, could be maintained with a relatively low input
packet flow, and affected all users of the network stack.

also, directories with 10,000 files are not quite common on systems where
there is a trust problem between users. So a typical directory with say
100 files will be listed in 0.18 seconds - it's slower, but does not make
the system unusable.

also, dcache flushes happen quite frequently under VM pressure - and
especially when using many files you get VM pressure. So it would take a
really specialized attack to keep the dcache size at the critical level
and trigger the slowdown.

also, any local user who can create thousands of files can cause much more
havoc by simply overloading the system. You might as well use that CPU
time to really bog down the system by making it swap heavily - this will
cause a _much_ heavier slowdown.

        Ingo

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in

More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

 
 
 

Algoritmic Complexity Attacks and 2.4.20 the dcache code

Post by Ingo Molna » Sat, 31 May 2003 06:40:09



Quote:> > I highly advise using a universal hashing library, either our own or
> > someone elses. As is historically seen, it is very easy to make silly
> > mistakes when attempting to implement your own 'secure' algorithm.

> Why are you recommending this when after 2 days of going back
> and forth in emails with me you came to the conclusion that for
> performance critical paths such as the hashes in the kernel the Jenkins
> hash was an acceptable choice?

> It is unacceptably costly to use a universal hash, it makes a multiply
> operation for every byte of key input plus a modulo operation at the end
> of the hash computation.  All of which can be extremely expensive on
> some architectures.

> I showed and backed this up for you with benchmarks comparing your
> universal hashing code and Jenkins.

i'd suggest to use the jhash for the following additional kernel entities:  
pagecache hash, inode hash, vcache hash.

the buffer-cache hash and the pidhash should be hard (impossible?) to
attack locally.

        Ingo

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in

More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

 
 
 

Algoritmic Complexity Attacks and 2.4.20 the dcache code

Post by Scott A Crosb » Sat, 31 May 2003 06:50:07




> > I have confirmed via an actual attack that it is possible to force the
> > dcache to experience a 200x performance degradation if the attacker can
> > control filenames. On a P4-1.8ghz, the time to list a directory of
> > 10,000 files is 18 seconds instead of .1 seconds.

> are you sure this is a big issue? Kernel 2.0 (maybe even 2.2) lists 10,000
> files at roughly the same speed (18 seconds) without any attack pattern
> used for filenames - still it's a kernel being used.

No. Its not that severe, but it does exist, and it is noticable even
with a quarter that number of files. I did it because it was an
interesting illustrative example, and it only took 30 seconds or so of
coding to put the hash function into generator generating program.

Quote:> So it would take a really specialized attack to keep the dcache size
> at the critical level and trigger the slowdown.

Yup. It is probably a very unusual configuration, but that doesn't
mean that somebody won't experience it. :)

Scott
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in

More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

 
 
 

Algoritmic Complexity Attacks and 2.4.20 the dcache code

Post by David S. Mille » Sat, 31 May 2003 07:10:08



> It is probably a very unusual configuration,

It is worth noting that it might even be possible to go after
this remotely. Consider a mailserver that you can someone influence
the queued mail file names for.

--

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in

More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

 
 
 

Algoritmic Complexity Attacks and 2.4.20 the dcache code

Post by Scott A Crosb » Sat, 31 May 2003 07:10:10




> > I highly advise using a universal hashing library, either our own or
> > someone elses. As is historically seen, it is very easy to make silly
> > mistakes when attempting to implement your own 'secure' algorithm.

> Why are you recommending this when after 2 days of going back
> and forth in emails with me you came to the conclusion that for
> performance critical paths such as the hashes in the kernel the Jenkins
> hash was an acceptable choice?

That was a boilerplate paragraph in all the other vulnerability
reports I shipped out today. Perhaps I should have stripped out out or
replaced it.

Quote:> It is unacceptably costly to use a universal hash,

Yup the Jenkin's is about 5 times faster than our CW construction on
SPARC, and thus likely at least as much faster on a wide variety of
other CPU's. I do not know if the dcache hash is performance critical,
nor do I know if there exists other more efficient universal hash
functions.

In any case, the attacks I describe are strong in relative terms, but
rather weak in terems of actual impact, so fixing it may not matter
much.

Quote:> Some embedded folks will have your head on a platter if we end up using
> a universal hash function for the DCACHE solely based upon your advice.
> :-)

Have you seen the current dcache function?

/* Linux dcache */
#define HASH_3(hi,ho,c)  ho=(hi + (c << 4) + (c >> 4)) * 11

Scott
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in

More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

 
 
 

Algoritmic Complexity Attacks and 2.4.20 the dcache code

Post by David S. Mille » Sat, 31 May 2003 08:30:14



   Date: 30 May 2003 00:04:24 -0500

   Have you seen the current dcache function?

   /* Linux dcache */
   #define HASH_3(hi,ho,c)  ho=(hi + (c << 4) + (c >> 4)) * 11

Awesome, moving the Jenkins will actually save us some
cycles :-)
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in

More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

 
 
 

Algoritmic Complexity Attacks and 2.4.20 the dcache code

Post by Scott A Crosb » Sat, 31 May 2003 08:50:09




>    Date: 30 May 2003 00:04:24 -0500

>    Have you seen the current dcache function?

>    /* Linux dcache */
>    #define HASH_3(hi,ho,c)  ho=(hi + (c << 4) + (c >> 4)) * 11

> Awesome, moving the Jenkins will actually save us some
> cycles :-)

Tricky though, because what if you want to hash more than 64 bits? You
have to somehow chain Jenkin's together.

Let H(a,b,c) be a jenkin's hash that does  '' mix(a,b,c) ; return a ''

Let a,b,c,d,e be inputs to be hashed, and R,S,T,U be random keys.

Its not safe to do anything like

 H(H(a,b,c),H(d,e,f),R)

Because an attacker can brute-force to find tuples (a,b,c),
(a',b',c'), ... so that H(a,b,c) == H(a',b',c') == ....

A better approach (which I make with no formal analysis of its
quality) might be to construct this:

 H(a,b,R) ^ H(c,d,S) ^ H(e,f,T)

Perhaps the best approach is to visit Usenix Security 2003 this August
and ask the experts there.

Scott
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in

More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

 
 
 

Algoritmic Complexity Attacks and 2.4.20 the dcache code

Post by David S. Mille » Sat, 31 May 2003 09:00:14



   Date: 30 May 2003 01:46:12 -0500

   Its not safe to do anything like

One thing that helps here is that we don't need to provide
protection outside the realm of a single name.

This is because the hash function takes the pointer of the dentry of
the directory it is in (the parent), and contributes this into
the hash.

Back to the basic problem, using jenkins for hashing names.  You could
simply shuffle the bytes into a set of 3 32-bit words, every time
you've contributed 12 bytes (the 3 words are full) or you've finished
the string, you run a __jhash_mix(a,b,c) pass.  And you can make
init_name_hash() insert the initial random value (choosen using
get_random_bytes() right before we mount root).

After all, a string is just a variable number of u32 words.

Actually, since we can say something about the alignment of the string
pointer in the dentry case, we can simply feed this as a u32 pointer
straight into the jenkins hash.  We know the length of the string so
this is pretty easy.  Actually, the most generic version "jhash()"
handles arbitrary byte lengths and alignments.
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in

More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

 
 
 

Algoritmic Complexity Attacks and 2.4.20 the dcache code

Post by Alex Riese » Sat, 31 May 2003 11:10:07


David S. Miller, Fri, May 30, 2003 08:24:40 +0200:


>    Date: 30 May 2003 00:04:24 -0500

>    Have you seen the current dcache function?

>    /* Linux dcache */
>    #define HASH_3(hi,ho,c)  ho=(hi + (c << 4) + (c >> 4)) * 11

> Awesome, moving the Jenkins will actually save us some
> cycles :-)

    static
    int hash_3(int hi, int c)
    {
        return (hi + (c << 4) + (c >> 4)) * 11;
    }

gcc-3.2.1 -O2 -march=pentium

    hash_3:
            pushl       %ebp
            movl        %esp, %ebp
            movl        12(%ebp), %eax
            movl        8(%ebp), %ecx
            movl        %eax, %edx
            popl        %ebp
            sall        $4, %edx
            sarl        $4, %eax
            addl        %ecx, %edx
            addl        %eax, %edx
            leal        (%edx,%edx,4), %eax
            leal        (%edx,%eax,2), %eax
            ret

It is not guaranteed to be this way on all architectures, of course.
But still - no multiplications.

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in

More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

 
 
 

Algoritmic Complexity Attacks and 2.4.20 the dcache code

Post by David S. Mille » Sat, 31 May 2003 11:10:16



   Date: Fri, 30 May 2003 10:59:01 +0200

       static
       int hash_3(int hi, int c)
       {
        return (hi + (c << 4) + (c >> 4)) * 11;
       }

   gcc-3.2.1 -O2 -march=pentium
 ...  
   It is not guaranteed to be this way on all architectures, of course.
   But still - no multiplications.

Indeed, I'd missed this.  GCC will emit the constant multiply
expansion unless the multiply cost is set VERY low.
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in

More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

 
 
 

Algoritmic Complexity Attacks and 2.4.20 the dcache code

Post by Nikita Danilo » Sat, 31 May 2003 16:00:09


Quote:Scott A Crosby writes:

 > Hello. We have analyzed this software to determine its vulnerability
 > to a new class of DoS attacks that related to a recent paper. ''Denial
 > of Service via Algorithmic Complexity Attacks.''
 >
 > This paper discusses a new class of denial of service attacks that
 > work by exploiting the difference between average case performance and
 > worst-case performance. In an adversarial environment, the data
 > structures used by an application may be forced to experience their
 > worst case performance. For instance, hash tables are usually thought
 > of as being constant time operations, but with large numbers of
 > collisions will degrade to a linked list and may lead to a 100-10,000
 > times performance degradation.

Another nice way to experience "worst case performance", is to create
deeply nested directory structure, like

0/1/2/3/4/.../99999/100000

try to unmount and see how shrink_dcache_parent/prune_dcache consume
100% of CPU without allowing preemption. Not recommended on a single
processor machine.

 >                                Because of the widespread use of hash
 > tables, the potential for attack is extremely widespread. Fortunately,
 > in many cases, other limits on the system limit the impact of these
 > attacks.
 >

[...]

 >
 > Scott

Nikita.
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in

More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

 
 
 

Algoritmic Complexity Attacks and 2.4.20 the dcache code

Post by Scott A Crosb » Sat, 31 May 2003 17:10:16




>    Date: Fri, 30 May 2003 10:59:01 +0200

>        static
>        int hash_3(int hi, int c)
>        {
>            return (hi + (c << 4) + (c >> 4)) * 11;
>        }

>    gcc-3.2.1 -O2 -march=pentium
>  ...  
>    It is not guaranteed to be this way on all architectures, of course.
>    But still - no multiplications.

> Indeed, I'd missed this.  GCC will emit the constant multiply
> expansion unless the multiply cost is set VERY low.

It may still be a win. This does a bit under a dozen instructions per
byte. However, jenkin's does many bytes at a time.

Scott
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in

More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

 
 
 

Algoritmic Complexity Attacks and 2.4.20 the dcache code

Post by Timothy Mille » Sat, 31 May 2003 20:10:11



> i'd suggest to use the jhash for the following additional kernel entities:  
> pagecache hash, inode hash, vcache hash.

> the buffer-cache hash and the pidhash should be hard (impossible?) to
> attack locally.

Maybe this is what someone is saying, and I just missed it, but...

Coming late into this discussion (once again), I am making some
assumptions here.  A while back, someone came up with a method for
breaking encryption (narrowing the brute force computations) by
determining how long it took a given host to compute encryption keys or
hashes or something.

If you have a situation where a lot of hashes are to be computed, and
you want to decouple the computation time from the response time, then
do this:

1) A kernel thread requests a hash to be computed.  That hash is
computed and put into a queue.  The kernel thread is put into the task
queue.
2) Other kernel threads do the same.
3) Threads get woken up only when their hash is pulled off the queue.

This way, the only added overhead is kernel context switch from one
thread to another.  The algorithm doesn't waste CPU time trying to hide
the complexity of the computation, because the time between request and
receipt of a hash is dependent on whatever other random hashed are also
being computed.  That is, receipt is much later than request, but you
haven't wasted time.

The only case where this doesn't deal with the problem in a low-cost way
is when the queue starts out empty when you make a request, and then
it's the only one on the queue when it's pulled off.  In that case, you
do have to waste time.  However, given that the kernel thread will go to
sleep anyhow, the time between sleeping and waking up is somewhat random
due to whatever other kernel and user threads might get executed in the
mean time.

In fact, one solution to this problem would be for the hash computing
function to just yield the CPU before or after the computation of the
hash.  Even in a system with absolutely no other load, the fact that we
have to go into and out of the scheduler will add some randomness to the
computation time, perhaps.

Have I just completely left the topic here?  :)

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in

More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/