Re: Algoritmic Complexity Attacks and 2.4.20 the dcache code

[Scott A Crosby]

On Fri, 30 May 2003 06:02:18 +0200 (CEST), Ingo Molnar <[e-mail]> writes:

> On 29 May 2003, Scott A Crosby wrote:
> 
> > 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.

> 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