Skip site navigation (1)Skip section navigation (2)
Date:      Wed, 06 Dec 2006 12:11:04 +0000
From:      David Malone <dwmalone@maths.tcd.ie>
To:        Luigi Rizzo <rizzo@icir.org>
Cc:        dwmalone@maths.tcd.ie, Max Laier <max@love2party.net>, freebsd-ipfw@freebsd.org
Subject:   Re: Better "hash_packet6" 
Message-ID:  <200612061211.aa82579@walton.maths.tcd.ie>
In-Reply-To: Your message of "Wed, 06 Dec 2006 03:54:41 PST." <20061206035441.A58131@xorpc.icir.org> 

next in thread | previous in thread | raw e-mail | index | archive | help
> maybe just ipfw2-ipv4 on and a single accept rule.
> that's to give an estimate of all the remaining packet processing
> costs that you were mentioning (interrupts etc.)

OK.

> > I've read the description of the Hsieh hash now and I'm pretty sure
> > it should be possible to produce lots of collisions fairly easily

> i am not saying that this is the only option, the page lists other
> hashes.

It looks to me as if none of them are designed to be resistent to
collision attacks. He compares it to FNV, which I'm familar with,
and it isn't designed to be resistent either. I think he's looking
at the wrong sort of hash functions for what we want.

The Usenix paper mentioned covered most of the suitable hash functions
available at the time:

	http://www.cs.rice.edu/~scrosby/hash/

We basically chose something like the CW12-20, but modified for our
input and output requirements. I have to admit, that I didn't follow
try hard to follow the literature forward to see if there have been
any advances since then.

> If i may make a modest proposal, lets make the hashing algorithm
> a compile (or run) time option so people worried about collisions
> will be able to use the expensive function, and others can select
> a simpler one e.g. some simpler hash that xor's the addresses
> instead of sorting them.

I suspect that xoring is probably both cheap and efficient if you
believe that you won't see attacks of this nature. Making it a
compile- or run-time option sounds reasonable to me.

> with the 36 bytes strings we have to work on, i doubt we can find
> something that is not a memory killer yet runs in decent times!

Indeed - might be worth having a dig around though!

	David.



Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?200612061211.aa82579>