Messages in this thread |  | | Subject | Re: Algoritmic Complexity Attacks and 2.4.20 the dcache code | From | Scott A Crosby <> | Date | 30 May 2003 01:46:12 -0500 |
| |
On Thu, 29 May 2003 23:24:40 -0700 (PDT), "David S. Miller" <davem@redhat.com> writes:
> From: Scott A Crosby <scrosby@cs.rice.edu> > Date: 30 May 2003 00:04:24 -0500 > > Have you seen the current dcache function? > > /* Linux dcache */ > #define HASH_3(hi,ho,c) ho=(hi + (c << 4) + (c >> 4)) * 11 > > Awesome, moving the Jenkins will actually save us some > cycles :-)
Tricky though, because what if you want to hash more than 64 bits? You have to somehow chain Jenkin's together.
Let H(a,b,c) be a jenkin's hash that does '' mix(a,b,c) ; return a ''
Let a,b,c,d,e be inputs to be hashed, and R,S,T,U be random keys.
Its not safe to do anything like
H(H(a,b,c),H(d,e,f),R)
Because an attacker can brute-force to find tuples (a,b,c), (a',b',c'), ... so that H(a,b,c) == H(a',b',c') == ....
A better approach (which I make with no formal analysis of its quality) might be to construct this:
H(a,b,R) ^ H(c,d,S) ^ H(e,f,T)
Perhaps the best approach is to visit Usenix Security 2003 this August and ask the experts there.
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/
|  |