Date: Tue, 14 Nov 2006 08:36:33 -0800 (PST) From: Paul Twohey <twohey@cs.stanford.edu> To: Max Laier <max@love2party.net> Cc: freebsd-hackers@freebsd.org, freebsd-net@freebsd.org Subject: Re: ipv6 connection hash function wanted ... Message-ID: <Pine.LNX.4.56.0611140835420.9151@keeda.stanford.edu> In-Reply-To: <200611141709.26644.max@love2party.net> References: <200611141709.26644.max@love2party.net>
next in thread | previous in thread | raw e-mail | index | archive | help
On Tue, 14 Nov 2006, Max Laier wrote: > this one is something for people who know their math. > > Input: 2x128bit of address (lower ~80bit selectable by user) and 2x16bit > of ports (more or less selectable by user). Note that the "flow_id" is > not useable as several broken stack implementations do not set it > consistently - and it is user settable as well. > Output: "int" hash value - by default we use the lower 8bit of it. > > Problems: Most of the input can be selected by a user meaning it is easy > to produce collisions. For legal connections, the lower 64bit are the > one with the highest entropy - in fact the upper 64bit might be the same > for many connections coming from/going to the same subnet. This function > will be used for every packet that is passed to a dynamic IPFW rule, so > efficiency is a concern. > > Any ideas? Any papers that deal with this problem? > > ref: sys/netinet/ip_fw2.c::hash_packet6 If you are worried about users controlling which values their packets hash to you might want to look at universal hashing. People who are worried about algorithmic denial of service attacks face similar problems. A good place to start would probably be: http://www.cs.rice.edu/~scrosby/hash Paul Twohey twohey@cs
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?Pine.LNX.4.56.0611140835420.9151>