From owner-freebsd-net@FreeBSD.ORG Tue Nov 14 16:36:35 2006 Return-Path: X-Original-To: freebsd-net@freebsd.org Delivered-To: freebsd-net@freebsd.org Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id 3950416A412 for ; Tue, 14 Nov 2006 16:36:35 +0000 (UTC) (envelope-from twohey@cs.stanford.edu) Received: from smtp1.stanford.edu (smtp1.Stanford.EDU [171.67.22.28]) by mx1.FreeBSD.org (Postfix) with ESMTP id B317443D62 for ; Tue, 14 Nov 2006 16:36:34 +0000 (GMT) (envelope-from twohey@cs.stanford.edu) Received: from smtp1.stanford.edu (localhost.localdomain [127.0.0.1]) by localhost (Postfix) with SMTP id 330504C155 for ; Tue, 14 Nov 2006 08:36:34 -0800 (PST) Received: from keeda.stanford.edu (keeda.Stanford.EDU [171.64.72.55]) by smtp1.stanford.edu (Postfix) with ESMTP id 16EE74C0A9 for ; Tue, 14 Nov 2006 08:36:34 -0800 (PST) Received: from twohey (helo=localhost) by keeda.stanford.edu with local-esmtp (Exim 4.63) (envelope-from ) id 1Gk1H0-0002jC-0y; Tue, 14 Nov 2006 08:36:34 -0800 Date: Tue, 14 Nov 2006 08:36:33 -0800 (PST) From: Paul Twohey X-X-Sender: twohey@keeda.stanford.edu To: Max Laier In-Reply-To: <200611141709.26644.max@love2party.net> Message-ID: References: <200611141709.26644.max@love2party.net> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Cc: freebsd-hackers@freebsd.org, freebsd-net@freebsd.org Subject: Re: ipv6 connection hash function wanted ... X-BeenThere: freebsd-net@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Networking and TCP/IP with FreeBSD List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 14 Nov 2006 16:36:35 -0000 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