Messages in this thread | | | Subject | Re: Algoritmic Complexity Attacks and 2.4.20 the dcache code | From | Scott A Crosby <> | Date | 30 May 2003 00:04:24 -0500 |
| |
On 29 May 2003 20:57:47 -0700, "David S. Miller" <davem@redhat.com> writes:
> On Thu, 2003-05-29 at 13:42, Scott A Crosby wrote: > > 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.
> 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.
> 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 the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
| |