Re: Algoritmic Complexity Attacks and 2.4.20 the dcache code

Daniel Phillips
2003-06-01T01:01:40Z

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

You should have said "a solution", not "the solution", above. For the Ext2/3
HTree index, we found a rather nice solution that varies the hash dispersion
pattern on a per-volume basis, in a way that's difficult for a DOSer to
reconstruct (please feel free to analyze this approach and find a hole, if
there is one).

This is much simpler than what you propose. As we are talking core kernel
here, adding an extra spiderweb of complexity in the form of multiple hash
algorithms really isn't appealing, if it can be avoided. Not to mention the
overhead of indexing into the correct hash algorithm on each lookup.

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

Translation: adding bloat is often the easy way out for the lazy. Anyway,
thanks for your analysis, but I disagree with your recommendation.

Regards,

Daniel