From owner-freebsd-hackers@FreeBSD.ORG Tue Nov 14 16:36:35 2006 Return-Path: X-Original-To: freebsd-hackers@freebsd.org Delivered-To: freebsd-hackers@freebsd.org Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id 4C23C16A415 for ; Tue, 14 Nov 2006 16:36:35 +0000 (UTC) (envelope-from twohey@cs.stanford.edu) Received: from smtp3.stanford.edu (smtp3.Stanford.EDU [171.67.20.26]) by mx1.FreeBSD.org (Postfix) with ESMTP id 6802343D67 for ; Tue, 14 Nov 2006 16:36:34 +0000 (GMT) (envelope-from twohey@cs.stanford.edu) Received: from smtp3.stanford.edu (localhost.localdomain [127.0.0.1]) by localhost (Postfix) with SMTP id 33C4C4C44A; Tue, 14 Nov 2006 08:36:34 -0800 (PST) Received: from keeda.stanford.edu (keeda.Stanford.EDU [171.64.72.55]) by smtp3.stanford.edu (Postfix) with ESMTP id 161ED4C29E; 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-hackers@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Technical Discussions relating to 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