Re: Algoritmic Complexity Attacks and 2.4.20 the dcache code

[Daniel Phillips]

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