From owner-freebsd-ipfw@FreeBSD.ORG Wed Dec 6 12:16:34 2006 Return-Path: X-Original-To: freebsd-ipfw@freebsd.org Delivered-To: freebsd-ipfw@freebsd.org Received: from mx1.FreeBSD.org (mx1.freebsd.org [69.147.83.52]) by hub.freebsd.org (Postfix) with ESMTP id 5A9F316A47B for ; Wed, 6 Dec 2006 12:16:34 +0000 (UTC) (envelope-from dwmalone@maths.tcd.ie) Received: from salmon.maths.tcd.ie (salmon.maths.tcd.ie [134.226.81.11]) by mx1.FreeBSD.org (Postfix) with SMTP id 92CE343CC4 for ; Wed, 6 Dec 2006 12:10:23 +0000 (GMT) (envelope-from dwmalone@maths.tcd.ie) Received: from walton.maths.tcd.ie ([134.226.81.10] helo=walton.maths.tcd.ie) by salmon.maths.tcd.ie with SMTP id ; 6 Dec 2006 12:11:06 +0000 (GMT) Received: from localhost ([127.0.0.1] helo=maths.tcd.ie) by walton.maths.tcd.ie with SMTP id ; 6 Dec 2006 12:11:04 +0000 (GMT) To: Luigi Rizzo In-reply-to: Your message of "Wed, 06 Dec 2006 03:54:41 PST." <20061206035441.A58131@xorpc.icir.org> X-Request-Do: Date: Wed, 06 Dec 2006 12:11:04 +0000 From: David Malone Message-ID: <200612061211.aa82579@walton.maths.tcd.ie> Cc: dwmalone@maths.tcd.ie, Max Laier , freebsd-ipfw@freebsd.org Subject: Re: Better "hash_packet6" X-BeenThere: freebsd-ipfw@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: IPFW Technical Discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 06 Dec 2006 12:16:34 -0000 > 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.