Hello !
On Sat, Apr 05, 2003 at 06:37:43PM +0200, Florian Weimer wrote:
> Please read the following paper:
>
> <http://www.cs.rice.edu/~scrosby/tr/HashAttack.pdf>
very interesting article.
> Then look at the 2.4 route cache implementation.
Since we need commutative source/dest addresses in many places, the use of a
XOR is a common practice. In fact, while working on hash tables a while ago, I
found that I could get very good results with something such as :
RND1 = random_generated_at_start_time() ;
RND2 = random_generated_at_start_time() ;
/* RND2 may be 0 or equal to RND1, all cases seem OK */
x = (RND1 - saddr) ^ (RND1 - daddr) ^ (RND2 + saddr + daddr);
reduce(x) ...
With this method, I found no way to guess a predictable (saddr, daddr) couple
which gives a same result, and saddr/daddr are still commutative. It resists
common cases where saddr=daddr, saddr=~daddr, saddr=-daddr. And *I think* tha
the random makes other cases difficult to predict. I'm not specialized in
crypto or whatever, so I cannot tell how to generate the best RND1/2, and it's
obvious to me that stupid values like 0 or -1 may not help a lot, but this is
still better than a trivial saddr ^ daddr, at a very low cost.
For example, the x86 encoding of the simple XOR hash would result in :
mov saddr, %eax
xor daddr, %eax
=> 2 cycles with result in %eax
The new calculation will look like :
mov saddr, %ebx
mov daddr, %ecx
lea (%ebx,%ecx,1), %eax
neg %ecx
add RND2, %eax // can be omitted if zero
add RND1, %ecx
neg %ebx
xor %ecx, %eax
add RND1, %ebx
xor %ebx, %eax
=> 5 cycles on dual-pipelines CPUs, result in eax, but uses 2 more regs.
Any comments ?
Regards,
Willy
-
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/
This archive was generated by hypermail 2b29 : Mon Apr 07 2003 - 22:00:26 EST