Negative result: algorithmic complexity attack against nscd hash function

[Florian Weimer]

I was wondering if performance degrades substantially if the nscd cache
contains many records which hash to the same value (or rather, hash
bucket).  This does not seem to be the case because although performance
degrades substantially, the default cache size (about 30 MB) limits the
maximum hash chain length to roughly 300,000 entries (for getaddrinfo
cache entries).  Even such a large number of entries can be searched in
a reasonable time on current systems (compared to uncached/cache miss
lookup performance).

The situation is certainly not ideal, but it does not seem to be an
exploitable denial of service issue in the default configuration.
Still, a possible reimplementation of the nscd cache should probably
switch to a balanced binary tree for more predictable performance.

Thanks,
Florian