From owner-freebsd-ipfw@FreeBSD.ORG Mon Dec 4 11:08:40 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 6756316A494 for ; Mon, 4 Dec 2006 11:08:40 +0000 (UTC) (envelope-from owner-bugmaster@FreeBSD.org) Received: from freefall.freebsd.org (freefall.freebsd.org [69.147.83.40]) by mx1.FreeBSD.org (Postfix) with ESMTP id 0627043CC9 for ; Mon, 4 Dec 2006 11:07:48 +0000 (GMT) (envelope-from owner-bugmaster@FreeBSD.org) Received: from freefall.freebsd.org (linimon@localhost [127.0.0.1]) by freefall.freebsd.org (8.13.4/8.13.4) with ESMTP id kB4B8KGt045397 for ; Mon, 4 Dec 2006 11:08:20 GMT (envelope-from owner-bugmaster@FreeBSD.org) Received: (from linimon@localhost) by freefall.freebsd.org (8.13.4/8.13.4/Submit) id kB4B8IGe045394 for freebsd-ipfw@FreeBSD.org; Mon, 4 Dec 2006 11:08:18 GMT (envelope-from owner-bugmaster@FreeBSD.org) Date: Mon, 4 Dec 2006 11:08:18 GMT Message-Id: <200612041108.kB4B8IGe045394@freefall.freebsd.org> X-Authentication-Warning: freefall.freebsd.org: linimon set sender to owner-bugmaster@FreeBSD.org using -f From: FreeBSD bugmaster To: freebsd-ipfw@FreeBSD.org Cc: Subject: Current problem reports assigned to you 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: Mon, 04 Dec 2006 11:08:40 -0000 Current FreeBSD problem reports Critical problems Serious problems S Tracker Resp. Description -------------------------------------------------------------------------------- o kern/51274 ipfw [ipfw] [patch] ipfw2 create dynamic rules with parent o kern/73910 ipfw [ipfw] serious bug on forwarding of packets after NAT o kern/74104 ipfw [ipfw] ipfw2/1 conflict not detected or reported, manp o conf/78762 ipfw [ipfw] [patch] /etc/rc.d/ipfw should excecute $firewal o bin/80913 ipfw [patch] /sbin/ipfw2 silently discards MAC addr arg wit o kern/88659 ipfw [modules] ipfw and ip6fw do not work properly as modul o kern/93300 ipfw ipfw pipe lost packets o kern/95084 ipfw [ipfw] [patch] IPFW2 ignores "recv/xmit/via any" (IPFW o kern/97504 ipfw [ipfw] IPFW Rules bug o kern/97951 ipfw [ipfw] [patch] ipfw does not tie interface details to o kern/98831 ipfw [ipfw] ipfw has UDP hickups o kern/102471 ipfw [ipfw] [patch] add tos and dscp support o kern/103454 ipfw [ipfw] [patch] add a facility to modify DF bit of the 13 problems total. Non-critical problems S Tracker Resp. Description -------------------------------------------------------------------------------- a kern/26534 ipfw [ipfw] Add an option to ipfw to log gid/uid of who cau o kern/46159 ipfw [ipfw] [patch] ipfw dynamic rules lifetime feature o kern/48172 ipfw [ipfw] [patch] ipfw does not log size and flags o bin/50749 ipfw [ipfw] [patch] ipfw2 incorrectly parses ports and port o kern/55984 ipfw [ipfw] [patch] time based firewalling support for ipfw o kern/60719 ipfw [ipfw] Headerless fragments generate cryptic error mes o kern/69963 ipfw [ipfw] install_state warning about already existing en o kern/71366 ipfw [ipfw] "ipfw fwd" sometimes rewrites destination mac a o kern/72987 ipfw [ipfw] ipfw/dummynet pipe/queue 'queue [BYTES]KBytes ( o kern/73276 ipfw [ipfw] [patch] ipfw2 vulnerability (parser error) o bin/78785 ipfw [ipfw] [patch] ipfw verbosity locks machine if /etc/rc o kern/80642 ipfw [ipfw] [patch] ipfw small patch - new RULE OPTION o kern/82724 ipfw [ipfw] [patch] Add setnexthop and defaultroute feature o kern/86957 ipfw [ipfw] [patch] ipfw mac logging o kern/87032 ipfw [ipfw] [patch] ipfw ioctl interface implementation o kern/91847 ipfw [ipfw] ipfw with vlanX as the device o kern/103328 ipfw sugestions about ipfw table o kern/104682 ipfw [ipfw] [patch] Some minor language consistency fixes a o bin/104921 ipfw [patch] ipfw(8) sometimes treats ipv6 input as ipv4 (a o kern/105330 ipfw [ipfw] [patch] ipfw (dummynet) does not allow to set q 20 problems total. From owner-freebsd-ipfw@FreeBSD.ORG Tue Dec 5 01:22:20 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 5A77516A47C for ; Tue, 5 Dec 2006 01:22:20 +0000 (UTC) (envelope-from cristi@net.utcluj.ro) Received: from bavaria.utcluj.ro (bavaria.utcluj.ro [193.226.5.35]) by mx1.FreeBSD.org (Postfix) with ESMTP id 5F90A43CA2 for ; Tue, 5 Dec 2006 01:21:42 +0000 (GMT) (envelope-from cristi@net.utcluj.ro) Received: from localhost (localhost [127.0.0.1]) by bavaria.utcluj.ro (Postfix) with ESMTP id 2C2437F23E for ; Tue, 5 Dec 2006 03:22:17 +0200 (EET) X-Virus-Scanned: by the daemon playing with your mail on bavaria.utcluj.ro Received: from bavaria.utcluj.ro ([127.0.0.1]) by localhost (bavaria.utcluj.ro [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id JwwFcFmh4tQo for ; Tue, 5 Dec 2006 03:22:16 +0200 (EET) Received: from [172.27.2.200] (c7.campus.utcluj.ro [193.226.6.226]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by bavaria.utcluj.ro (Postfix) with ESMTP id DC2457F340 for ; Tue, 5 Dec 2006 03:22:15 +0200 (EET) Message-ID: <4574C9C7.3030807@net.utcluj.ro> Date: Tue, 05 Dec 2006 03:22:15 +0200 From: Cristian KLEIN Organization: Data Communication Center - Technical University of Cluj-Napoca User-Agent: Icedove 1.5.0.7 (X11/20061013) MIME-Version: 1.0 To: freebsd-ipfw@freebsd.org X-Enigmail-Version: 0.94.0.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Subject: IPFW + dummynet + other firewall 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: Tue, 05 Dec 2006 01:22:20 -0000 Hello everybody, I sure hope this is relevant for the list. I have been using IPFW and PF in FreeBSD 5.4 for some time, because I like PF's NAT and ftp-proxy, but I can't live without pipes. While giving me joy, this combination also results in some strange behaviour. In the default configuration (i.e. firewall_enable and pf_enable="YES" in rc.conf) ipfw loads first and pf last, which has the great advantage of seeing untranslated packets in ipfw. When combining ipfw + dummynet + pf, some strange behaviour occurs, due to the fact that dummynet reinjects the packets into ip_input(). The path of incomming packets looks like this: wire -> pf -> ipfw -> dummynet -> pf -> ipfw -> kernel. 1) rdr rules to localhost (required for ftp-proxy etc.) which go through pipes fail, because ip_input() drops 127/8. 2) pass log rules make packets appear twice on pflog. Other issues may exist. I believe that the single solution would be something like in the pre-PFIL times, when ip_input() contained a jump directly to ipfw, and the packet was processed from where it left. However, this is pretty hard to implement in PFIL. Any ideas? From owner-freebsd-ipfw@FreeBSD.ORG Tue Dec 5 12:24:22 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 5188116A47C for ; Tue, 5 Dec 2006 12:24:22 +0000 (UTC) (envelope-from Anand.Balasundraraj@aricent.com) Received: from tapal.aricent.com (spark.hss.co.in [203.145.155.21]) by mx1.FreeBSD.org (Postfix) with ESMTP id F3E0143CA7 for ; Tue, 5 Dec 2006 12:23:41 +0000 (GMT) (envelope-from Anand.Balasundraraj@aricent.com) Received: from tapal.aricent.com (localhost [127.0.0.1]) by tapal.aricent.com (8.13.8/8.13.8) with ESMTP id kB5CQNuB031690 for ; Tue, 5 Dec 2006 17:56:23 +0530 Received: from chemail01.che.flextronics.com (chemail01.che.flextronics.com [10.203.112.151])by tapal.aricent.com (8.13.8/8.13.8) with ESMTP id kB5CQL27031629for ; Tue, 5 Dec 2006 17:56:23 +0530 From: Anand Balasundraraj To: freebsd-ipfw@freebsd.org Message-ID: Date: Tue, 5 Dec 2006 17:34:37 +0530 X-MIMETrack: Serialize by Router on Chemail01/CHE/HSS(Release 6.5.5|November 30, 2005) at12/05/2006 05:52:28 PM Content-Disposition: inline X-imss-version: 2.044 X-imss-result: Passed X-imss-scanInfo: M:B L:E SM:2 X-imss-tmaseResult: TT:1 TS:-10.3482 TC:1F TRN:39 TV:3.6.1039(14852.003) X-imss-scores: Clean:100.00000 C:0 M:0 S:0 R:0 X-imss-settings: Baseline:2 C:1 M:1 S:1 R:1 (0.0000 0.0000) MIME-Version: 1.0 Content-Type: text/plain; charset="US-ASCII" X-Content-Filtered-By: Mailman/MimeDel 2.1.5 Subject: Anand Balasundraraj is out of the office. 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: Tue, 05 Dec 2006 12:24:22 -0000 I will be out of the office starting 12/05/2006 and will not return until 12/07/2006. I will respond to your message when I return. Please contact Manickaraja for any Network related queries<.manickaraja.arumugam@flextronicssoftware.com> "DISCLAIMER: This message is proprietary to Aricent and is intended solely for the use of the individual to whom it is addressed. It may contain privileged or confidential information and should not be circulated or used for any purpose other than for what it is intended. If you have received this message in error, please notify the originator immediately. If you are not the intended recipient, you are notified that you are strictly prohibited from using, copying, altering, or disclosing the contents of this message. Aricent accepts no responsibility for loss or damage arising from the use of the information transmitted by this email including damage from virus." From owner-freebsd-ipfw@FreeBSD.ORG Tue Dec 5 19:10:53 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 E4D4F16A403 for ; Tue, 5 Dec 2006 19:10:53 +0000 (UTC) (envelope-from max@love2party.net) Received: from moutng.kundenserver.de (moutng.kundenserver.de [212.227.126.186]) by mx1.FreeBSD.org (Postfix) with ESMTP id A32CC43CA2 for ; Tue, 5 Dec 2006 19:10:12 +0000 (GMT) (envelope-from max@love2party.net) Received: from [88.66.25.227] (helo=amd64.laiers.local) by mrelayeu.kundenserver.de (node=mrelayeu6) with ESMTP (Nemesis), id 0ML29c-1Grfgc3qpy-0008Vj; Tue, 05 Dec 2006 20:10:39 +0100 From: Max Laier Organization: FreeBSD To: freebsd-ipfw@freebsd.org Date: Tue, 5 Dec 2006 20:10:30 +0100 User-Agent: KMail/1.9.4 X-Face: ,,8R(x[kmU]tKN@>gtH1yQE4aslGdu+2]; R]*pL,U>^H?)gW@49@wdJ`H<%}*_BD U_or=\mOZf764&nYj=JYbR1PW0ud>|!~, , CPC.1-D$FG@0h3#'5"k{V]a~. X-Provags-ID: kundenserver.de abuse@kundenserver.de login:61c499deaeeba3ba5be80f48ecc83056 Subject: 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: Tue, 05 Dec 2006 19:10:54 -0000 --nextPart15756221.C6omajAhyg Content-Type: multipart/mixed; boundary="Boundary-01=_oQcdFPftAjRnopP" Content-Transfer-Encoding: 7bit Content-Disposition: inline --Boundary-01=_oQcdFPftAjRnopP Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable Content-Disposition: inline Hi, with a lot of help from David Malone and JINMEI Tatuya we came up with the= =20 following hash function for IPv6 connections using universal hashing. =20 Note that while it looks a lot more complicated, it is unlikely to=20 consume (much) more time. The most expensive operation is still the=20 memory access - which has to happen either way. Since this is a firewall=20 and as such a security feature, we should rather do it right. Note that=20 in IPv6 an attacker can easily choose 96 Byte of input, so it's trivial=20 to construct collisions with the current hash function. A degenerated=20 hash is certainly more expensive than this changes. Objections, Comments, anything else? BTW, don't suggest that we use memcmp in addr6_cmp. As it turns out, the=20 kernel version of memcmp() does not provide POSIX compliant return=20 values. =2D-=20 /"\ Best regards, | mlaier@freebsd.org \ / Max Laier | ICQ #67774661 X http://pf4freebsd.love2party.net/ | mlaier@EFnet / \ ASCII Ribbon Campaign | Against HTML Mail and News --Boundary-01=_oQcdFPftAjRnopP Content-Type: text/x-diff; charset="us-ascii"; name="v6hash.diff" Content-Transfer-Encoding: quoted-printable Content-Disposition: attachment; filename="v6hash.diff" Index: ip_fw2.c =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D RCS file: /usr/store/mlaier/fcvs/src/sys/netinet/ip_fw2.c,v retrieving revision 1.154 diff -u -r1.154 ip_fw2.c =2D-- ip_fw2.c 13 Nov 2006 19:07:32 -0000 1.154 +++ ip_fw2.c 1 Dec 2006 18:00:04 -0000 @@ -50,6 +50,7 @@ #include #include #include +#include #include #include #include @@ -231,6 +232,9 @@ static ipfw_dyn_rule **ipfw_dyn_v =3D NULL; static u_int32_t dyn_buckets =3D 256; /* must be power of 2 */ static u_int32_t curr_dyn_buckets =3D 256; /* must be power of 2 */ +#define HASHKEYLEN 36 /* sizeof(in6_addr) * 2 + sizeof(in_port_t) * 2 */ +#define HASHPRIME 65537 +static u_int32_t ipfw_hash_key[HASHKEYLEN]; =20 static struct mtx ipfw_dyn_mtx; /* mutex guarding dynamic rules */ #define IPFW_DYN_LOCK_INIT() \ @@ -640,16 +644,56 @@ return 1; =20 } + +static __inline int +addr6_cmp(struct ipfw_flow_id *id) +{ + int i; + + if (id->src_port < id->dst_port) + return 1; + if (id->src_port > id->dst_port) + return -1; + for (i =3D 7; i >=3D 0; i--) + if (id->dst_ip6.s6_addr16[i] !=3D id->src_ip6.s6_addr16[i]) + return ((int)id->dst_ip6.s6_addr16[i] - + id->src_ip6.s6_addr16[i]); + + return (0); +} + static __inline int hash_packet6(struct ipfw_flow_id *id) { =2D u_int32_t i; =2D i =3D (id->dst_ip6.__u6_addr.__u6_addr32[2]) ^ =2D (id->dst_ip6.__u6_addr.__u6_addr32[3]) ^ =2D (id->src_ip6.__u6_addr.__u6_addr32[2]) ^ =2D (id->src_ip6.__u6_addr.__u6_addr32[3]) ^ =2D (id->dst_port) ^ (id->src_port); =2D return i; + u_int32_t a; + int i, j; + struct in6_addr *a1, *a2; + u_int8_t *p1, *p2; + + if (addr6_cmp(id) >=3D 0) { + a1 =3D &id->dst_ip6; + a2 =3D &id->src_ip6; + p1 =3D (u_int8_t *)&id->dst_port; + p2 =3D (u_int8_t *)&id->src_port; + } else { + a1 =3D &id->src_ip6; + a2 =3D &id->dst_ip6; + p1 =3D (u_int8_t *)&id->src_port; + p2 =3D (u_int8_t *)&id->dst_port; + } + + a =3D 0; + j =3D 0; + for (i =3D 0; i < sizeof(a1->s6_addr); i++) + a +=3D a1->s6_addr[i] * ipfw_hash_key[j++]; + for (i =3D 0; i < sizeof(a2->s6_addr); i++) + a +=3D a2->s6_addr[i] * ipfw_hash_key[j++]; + a +=3D p1[0] * ipfw_hash_key[j++]; + a +=3D p1[1] * ipfw_hash_key[j++]; + a +=3D p2[0] * ipfw_hash_key[j++]; + a +=3D p2[1] * ipfw_hash_key[j++]; + + return (a % HASHPRIME); } =20 static int @@ -1290,6 +1334,7 @@ static void realloc_dynamic_table(void) { + int j; IPFW_DYN_LOCK_ASSERT(); =20 /* @@ -1297,7 +1342,7 @@ * not allow more than 64k entries. In case of overflow, * default to 1024. */ =2D + CTASSERT(HASHPRIME >=3D 65536); if (dyn_buckets > 65536) dyn_buckets =3D 1024; if ((dyn_buckets & (dyn_buckets-1)) !=3D 0) { /* not a power of 2 */ @@ -1314,6 +1359,8 @@ break; curr_dyn_buckets /=3D 2; } + for (j =3D 0; j < HASHKEYLEN; j++) + ipfw_hash_key[j] =3D arc4random() % HASHPRIME; } =20 /** --Boundary-01=_oQcdFPftAjRnopP-- --nextPart15756221.C6omajAhyg Content-Type: application/pgp-signature -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.5 (FreeBSD) iD8DBQBFdcQsXyyEoT62BG0RAnFNAJ9QTNFvA+UQIlfwb1bH5j0z0ujfwACggM6J nc5OP+aSC5fVrwszG+Yx4T4= =RdTi -----END PGP SIGNATURE----- --nextPart15756221.C6omajAhyg-- From owner-freebsd-ipfw@FreeBSD.ORG Tue Dec 5 21:05:14 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 7A55316A415 for ; Tue, 5 Dec 2006 21:05:14 +0000 (UTC) (envelope-from mg@fork.pl) Received: from mail.obligo.pl (bwe42.internetdsl.tpnet.pl [83.18.212.42]) by mx1.FreeBSD.org (Postfix) with ESMTP id 5432E43CB9 for ; Tue, 5 Dec 2006 21:04:28 +0000 (GMT) (envelope-from mg@fork.pl) Received: from localhost (localhost [127.0.0.1]) by mail.obligo.pl (Postfix) with ESMTP id 2D3C95581; Tue, 5 Dec 2006 22:05:08 +0100 (CET) X-Virus-Scanned: by amavisd-new at obligo.pl Received: from mail.obligo.pl ([127.0.0.1]) by localhost (smb.obligo.pl [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 5TIg9ePT1UV8; Tue, 5 Dec 2006 22:05:05 +0100 (CET) Received: from hq.fork.pl (hq.fork.pl [217.113.238.142]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by mail.obligo.pl (Postfix) with ESMTP id 3467B5580 for ; Tue, 5 Dec 2006 22:05:04 +0100 (CET) From: Marcin Gryszkalis To: freebsd-ipfw@freebsd.org Date: Tue, 5 Dec 2006 22:05:01 +0100 User-Agent: KMail/1.9.5 References: <27fef5640611232116o6e26cbcbx230d13981270bb89@mail.gmail.com> In-Reply-To: <27fef5640611232116o6e26cbcbx230d13981270bb89@mail.gmail.com> X-Face: %perY3B?Ru<]v$M}WY0A)HAxTs.{"M{0~o#Zqd8`xYr@E9FS9zm9B+~!%,Ya)=?utf-8?q?SJ=3F=26WnsZO=0A=09?= Subject: Re: port redirection with natd and ipfw 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: Tue, 05 Dec 2006 21:05:14 -0000 On Friday 24 November 2006 06:16, Nilton Volpato wrote: > But Split DNS does not work in my case. Because I have different > services on different machines, and the dns will map one name (and all > ports associated to it) to one machine. > > Is there any solution that will work without using split dns? Sometimes it's possible to solve such problem with SRV records (with or without split dns zones) but not all services support it. Eg. voip/sip engines usually support it. Refer to rfc2782. regards -- Marcin Gryszkalis, PGP 0x9F183FA3 jabber jid:mg@chrome.pl, gg:2532994 http://the.fork.pl From owner-freebsd-ipfw@FreeBSD.ORG Wed Dec 6 00:17:47 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 5A45916A40F for ; Wed, 6 Dec 2006 00:17:47 +0000 (UTC) (envelope-from rizzo@icir.org) Received: from xorpc.icir.org (xorpc.icir.org [192.150.187.68]) by mx1.FreeBSD.org (Postfix) with ESMTP id 1DC5043C9D for ; Wed, 6 Dec 2006 00:17:05 +0000 (GMT) (envelope-from rizzo@icir.org) Received: from xorpc.icir.org (localhost [127.0.0.1]) by xorpc.icir.org (8.12.11/8.13.6) with ESMTP id kB60Hjvw050341; Tue, 5 Dec 2006 16:17:45 -0800 (PST) (envelope-from rizzo@xorpc.icir.org) Received: (from rizzo@localhost) by xorpc.icir.org (8.12.11/8.12.3/Submit) id kB60HjAI050340; Tue, 5 Dec 2006 16:17:45 -0800 (PST) (envelope-from rizzo) Date: Tue, 5 Dec 2006 16:17:45 -0800 From: Luigi Rizzo To: Max Laier Message-ID: <20061205161744.A48319@xorpc.icir.org> References: <200612052010.36789.max@love2party.net> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline User-Agent: Mutt/1.2.5.1i In-Reply-To: <200612052010.36789.max@love2party.net>; from max@love2party.net on Tue, Dec 05, 2006 at 08:10:30PM +0100 Cc: 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 00:17:47 -0000 On Tue, Dec 05, 2006 at 08:10:30PM +0100, Max Laier wrote: > Hi, > > with a lot of help from David Malone and JINMEI Tatuya we came up with the > following hash function for IPv6 connections using universal hashing. I followed the discussion on the topic a few days (weeks ?) ago and investigated around a bit, also following some of the pointers that passed on the list. So I have the following comments: First, this proposal, with 36 multiplies and one division, the function seems rather expensive for e.g. a low end cpu (arm or soekris) as you might find on network-appliance boxes. Any chance to get performance numbers on that hardware ? I wonder if you have considered alternatives such as the one at http://www.azillionmonkeys.com/qed/hash.html which seems reasonable in terms of theoretical background, performance and also in terms of license (see the reference about being used in Apple products). Second, and related to this specific hash function: if we end up using it, i think it would be good to add a bit of documentation on algorithm used and on constraints that there are (e.g. wrt operand sizes and values of the hash keys) so that people don't break it in the future trying to optimze things that they should not touch. In particular, i have the following questions: - is the algorithm defined on a byte-by-byte basis, or it is just your decision to implement it this way ? (having it work on 16-bit entries would e.g. halve the number of multiplies). - i guess that you use addr6_cmp() to sort the components of the address insuring the algorithm hashes forward and reverse traffic to the same value. symmetric. But for this, one of the suggestions was to xor SRC and DST to achieve the same thing, and i don't understand why you use this different approach (which doubles the input size and the number of multiplications). - what are the requirements on ipfw_hash_key[] values ? E.g. it seems that 0 should not be allowed or the corresponding byte would have no contribution in the hash. Any other invalid value, recommended range etc ? In any case i am glad that people are looking at improving some code that i am certainly guilty of :) cheers luigi From owner-freebsd-ipfw@FreeBSD.ORG Wed Dec 6 03:52:06 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 B304316A415 for ; Wed, 6 Dec 2006 03:52:06 +0000 (UTC) (envelope-from max@love2party.net) Received: from moutng.kundenserver.de (moutng.kundenserver.de [212.227.126.177]) by mx1.FreeBSD.org (Postfix) with ESMTP id A7F7143CAF for ; Wed, 6 Dec 2006 03:51:19 +0000 (GMT) (envelope-from max@love2party.net) Received: from [88.66.25.227] (helo=amd64.laiers.local) by mrelayeu.kundenserver.de (node=mrelayeu3) with ESMTP (Nemesis), id 0MKxQS-1GrnpA1ddT-0004cx; Wed, 06 Dec 2006 04:52:01 +0100 From: Max Laier Organization: FreeBSD To: Luigi Rizzo Date: Wed, 6 Dec 2006 04:51:51 +0100 User-Agent: KMail/1.9.4 References: <200612052010.36789.max@love2party.net> <20061205161744.A48319@xorpc.icir.org> In-Reply-To: <20061205161744.A48319@xorpc.icir.org> X-Face: ,,8R(x[kmU]tKN@>gtH1yQE4aslGdu+2]; R]*pL,U>^H?)gW@49@wdJ`H<=?utf-8?q?=25=7D*=5FBD=0A=09U=5For=3D=5CmOZf764=26nYj=3DJYbR1PW0ud?=>|!~,,CPC.1-D$FG@0h3#'5"k{V]a~.<=?utf-8?q?mZ=7D44=23Se=7Em=0A=09Fe=7E=5C=5DX5B=5D=5Fxj?=(ykz9QKMw_l0C2AQ]}Ym8)fU MIME-Version: 1.0 Content-Type: multipart/signed; boundary="nextPart1742497.VWN3z6gnJ1"; protocol="application/pgp-signature"; micalg=pgp-sha1 Content-Transfer-Encoding: 7bit Message-Id: <200612060451.58473.max@love2party.net> X-Provags-ID: kundenserver.de abuse@kundenserver.de login:61c499deaeeba3ba5be80f48ecc83056 Cc: 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 03:52:06 -0000 --nextPart1742497.VWN3z6gnJ1 Content-Type: multipart/mixed; boundary="Boundary-01=_Z5jdFG6xnwahQje" Content-Transfer-Encoding: 7bit Content-Disposition: inline --Boundary-01=_Z5jdFG6xnwahQje Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable Content-Disposition: inline On Wednesday 06 December 2006 01:17, Luigi Rizzo wrote: > On Tue, Dec 05, 2006 at 08:10:30PM +0100, Max Laier wrote: > > Hi, > > > > with a lot of help from David Malone and JINMEI Tatuya we came up > > with the following hash function for IPv6 connections using universal > > hashing. > > I followed the discussion on the topic a few days (weeks ?) > ago and investigated around a bit, also following some of the pointers > that passed on the list. So I have the following comments: > > First, this proposal, with 36 multiplies and one division, the > function seems rather expensive for e.g. a low end cpu (arm or > soekris) as you might find on network-appliance boxes. > Any chance to get performance numbers on that hardware ? I tried the reference machines (see hacked up attachment): 78x ia64 40x amd64 60x p3 16x p4 I don't have my Soekris set up, so if somebody could give it a try. > I wonder if you have considered alternatives such as the one at > > http://www.azillionmonkeys.com/qed/hash.html > > which seems reasonable in terms of theoretical background, performance > and also in terms of license (see the reference about being used > in Apple products). It needs a seed at very least. > Second, and related to this specific hash function: if we end up ^ not? In which case I'd agree. > using it, i think it would be good to add a bit of documentation > on algorithm used and on constraints that there are (e.g. wrt operand > sizes and values of the hash keys) so that people don't break it > in the future trying to optimze things that they should not touch. > > In particular, i have the following questions: > - is the algorithm defined on a byte-by-byte basis, or it is just > your decision to implement it this way ? (having it work on 16-bit > entries would e.g. halve the number of multiplies). > > - i guess that you use addr6_cmp() to sort the components of the > address insuring the algorithm hashes forward and reverse traffic > to the same value. symmetric. But for this, one of the suggestions > was to xor SRC and DST to achieve the same thing, and i don't > understand why you use this different approach (which doubles the > input size and the number of multiplications). If an attacker can set src and dst it remains trivial to create (many)=20 collisions. In order to degrade the hash table it is enough to spoof=20 SYNs, isn't it? On that note, if I'm correct it might be a good idea to=20 use a seeded hash for IPv4 as well. > - what are the requirements on ipfw_hash_key[] values ? > E.g. it seems that 0 should not be allowed or the corresponding > byte would have no contribution in the hash. Any other invalid > value, recommended range etc ? I think the answer is "good random data" in [0, HASH_PRIME). That=20 includes zero, but I agree that using zero is a bit pointless. I'll let=20 others speak to the details of universal hashing. > In any case i am glad that people are looking at improving some code > that i am certainly guilty of :) =2D-=20 /"\ Best regards, | mlaier@freebsd.org \ / Max Laier | ICQ #67774661 X http://pf4freebsd.love2party.net/ | mlaier@EFnet / \ ASCII Ribbon Campaign | Against HTML Mail and News --Boundary-01=_Z5jdFG6xnwahQje Content-Type: text/plain; charset="iso-8859-1"; name="hash_cost.c" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="hash_cost.c" #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include /* XXX do we need this ? */ #include #include #include #include #include #include #include /* def. of struct route */ #include #include #include #include #include #include #include #include #include #define HASHKEYLEN 36 /* sizeof(in6_addr) * 2 + sizeof(in_port_t) * 2 */ #define HASHPRIME 65537 static u_int32_t ipfw_hash_key[HASHKEYLEN]; #define s6_addr8 __u6_addr.__u6_addr8 #define s6_addr16 __u6_addr.__u6_addr16 #define s6_addr32 __u6_addr.__u6_addr32 static __inline int addr6_cmp(struct ipfw_flow_id *id) { int i; if (id->src_port < id->dst_port) return 1; if (id->src_port > id->dst_port) return -1; for (i = 7; i >= 0; i--) if (id->dst_ip6.s6_addr16[i] != id->src_ip6.s6_addr16[i]) return ((int)id->dst_ip6.s6_addr16[i] - id->src_ip6.s6_addr16[i]); return (0); } static __inline int hash_packet5(struct ipfw_flow_id *id) { u_int32_t i; i = (id->dst_ip6.__u6_addr.__u6_addr32[2]) ^ (id->dst_ip6.__u6_addr.__u6_addr32[3]) ^ (id->src_ip6.__u6_addr.__u6_addr32[2]) ^ (id->src_ip6.__u6_addr.__u6_addr32[3]) ^ (id->dst_port) ^ (id->src_port); return i; } static __inline int hash_packet6(struct ipfw_flow_id *id) { u_int32_t a; int i, j; struct in6_addr *a1, *a2; u_int8_t *p1, *p2; if (addr6_cmp(id) >= 0) { a1 = &id->dst_ip6; a2 = &id->src_ip6; p1 = (u_int8_t *)&id->dst_port; p2 = (u_int8_t *)&id->src_port; } else { a1 = &id->src_ip6; a2 = &id->dst_ip6; p1 = (u_int8_t *)&id->src_port; p2 = (u_int8_t *)&id->dst_port; } a = 0; j = 0; for (i = 0; i < sizeof(a1->s6_addr); i++) a += a1->s6_addr[i] * ipfw_hash_key[j++]; for (i = 0; i < sizeof(a2->s6_addr); i++) a += a2->s6_addr[i] * ipfw_hash_key[j++]; a += p1[0] * ipfw_hash_key[j++]; a += p1[1] * ipfw_hash_key[j++]; a += p2[0] * ipfw_hash_key[j++]; a += p2[1] * ipfw_hash_key[j++]; return (a % HASHPRIME); } #define COUNT 100000 #define COUNT2 4096 int main(int argc, char **argv) { int i, j; struct ipfw_flow_id *ids; struct timeval start, stop; uint64_t dur1, dur2; for (j = 0; j < HASHKEYLEN; j++) ipfw_hash_key[j] = arc4random() % HASHPRIME; ids = calloc(sizeof(struct ipfw_flow_id), COUNT2); for (i = 0; i < COUNT2; i++) { for (j = 0; j < 8; j++) { ids[0].src_ip6.s6_addr32[j] = arc4random(); ids[0].dst_ip6.s6_addr32[j] = arc4random(); } ids[0].src_port = (uint16_t)arc4random(); ids[0].dst_port = (uint16_t)arc4random(); } gettimeofday(&start, NULL); for (i = 0; i < COUNT; i++) for (j = 0; j < COUNT2; j++) (volatile)hash_packet6(&ids[j]); gettimeofday(&stop, NULL); dur1 = stop.tv_sec - start.tv_sec; dur1 *= 1000000; dur1 += (stop.tv_usec - start.tv_usec); printf("%ld\n", dur1); printf("%Lf\n", (long double)dur1 / (COUNT * COUNT2)); gettimeofday(&start, NULL); for (i = 0; i < COUNT; i++) for (j = 0; j < COUNT2; j++) (volatile)hash_packet5(&ids[j]); gettimeofday(&stop, NULL); dur2 = stop.tv_sec - start.tv_sec; dur2 *= 1000000; dur2 += (stop.tv_usec - start.tv_usec); printf("%ld\n", dur2); printf("%Lf\n", (long double)dur2 / (COUNT * COUNT2)); printf("%Lf\n", (long double)dur1 / dur2); return (0); } --Boundary-01=_Z5jdFG6xnwahQje-- --nextPart1742497.VWN3z6gnJ1 Content-Type: application/pgp-signature -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.5 (FreeBSD) iD8DBQBFdj5eXyyEoT62BG0RAotFAJ9Rfk0KkPplXHX8zKb+R2jUu3xruwCcDe9w Lc2uPSu4Hd9XhJUhD/skeqI= =C23x -----END PGP SIGNATURE----- --nextPart1742497.VWN3z6gnJ1-- From owner-freebsd-ipfw@FreeBSD.ORG Wed Dec 6 09:29:38 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 563B416A47E for ; Wed, 6 Dec 2006 09:29:38 +0000 (UTC) (envelope-from rizzo@icir.org) Received: from xorpc.icir.org (xorpc.icir.org [192.150.187.68]) by mx1.FreeBSD.org (Postfix) with ESMTP id E62EB43CA7 for ; Wed, 6 Dec 2006 09:28:47 +0000 (GMT) (envelope-from rizzo@icir.org) Received: from xorpc.icir.org (localhost [127.0.0.1]) by xorpc.icir.org (8.12.11/8.13.6) with ESMTP id kB69TV2o056453; Wed, 6 Dec 2006 01:29:31 -0800 (PST) (envelope-from rizzo@xorpc.icir.org) Received: (from rizzo@localhost) by xorpc.icir.org (8.12.11/8.12.3/Submit) id kB69TV9v056452; Wed, 6 Dec 2006 01:29:31 -0800 (PST) (envelope-from rizzo) Date: Wed, 6 Dec 2006 01:29:31 -0800 From: Luigi Rizzo To: Max Laier Message-ID: <20061206012931.A56288@xorpc.icir.org> References: <200612052010.36789.max@love2party.net> <20061205161744.A48319@xorpc.icir.org> <200612060451.58473.max@love2party.net> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline User-Agent: Mutt/1.2.5.1i In-Reply-To: <200612060451.58473.max@love2party.net>; from max@love2party.net on Wed, Dec 06, 2006 at 04:51:51AM +0100 Cc: 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 09:29:38 -0000 On Wed, Dec 06, 2006 at 04:51:51AM +0100, Max Laier wrote: > On Wednesday 06 December 2006 01:17, Luigi Rizzo wrote: ... > > First, this proposal, with 36 multiplies and one division, the > > function seems rather expensive for e.g. a low end cpu (arm or > > soekris) as you might find on network-appliance boxes. > > Any chance to get performance numbers on that hardware ? > > I tried the reference machines (see hacked up attachment): > 78x ia64 > 40x amd64 > 60x p3 > 16x p4 i assume the first number is the slowdown between the current and the proposed method ? I have slightly modified/extended the program adding the hsieh hash that i mentioned below, and made it easy to add more methods. the code is at http://info.iet.unipi.it/~luigi/hc.c as expected, especially the simplest algorithms depend a lot on cache effects so if you change the number of packets or the number of loops things vary a lot. In any case, on a soekris (the default parameters are too high): # ./hc 1000 100 starting algorithm hash_pkt5 1000 loops 100 packets took 87862 usec, 0.878620 per cycle starting algorithm hash_hsieh 1000 loops 100 packets took 1082883 usec, 10.828830 per cycle starting algorithm hash_pkt6 1000 loops 100 packets took 2697178 usec, 26.971780 per cycle # ./hc 100 10000 starting algorithm hash_pkt5 100 loops 10000 packets took 2023610 usec, 2.023610 per cycle starting algorithm hash_hsieh 100 loops 10000 packets took 11619238 usec, 11.619238 per cycle starting algorithm hash_pkt6 100 loops 10000 packets took 27739595 usec, 27.739595 per cycle (here we probably overflow some cache so the simple algorithm suffers a lot by increasing the number of different packets) on my new 3 GHz pentium D > ./hc 1000 100 starting algorithm hash_pkt5 1000 loops 100 packets took 1258 usec, 0.012580 per cycle starting algorithm hash_hsieh 1000 loops 100 packets took 16152 usec, 0.161520 per cycle starting algorithm hash_pkt6 1000 loops 100 packets took 25485 usec, 0.254850 per cycle > ./hc 100 10000 starting algorithm hash_pkt5 100 loops 10000 packets took 12870 usec, 0.012870 per cycle starting algorithm hash_hsieh 100 loops 10000 packets took 162510 usec, 0.162510 per cycle starting algorithm hash_pkt6 100 loops 10000 packets took 248003 usec, 0.248003 per cycle Surely we need to experiment a bit more, but the cost is significant especially on low end boxes. Maybe we could restrict the hash to just a part of the address ? cheers luigi From owner-freebsd-ipfw@FreeBSD.ORG Wed Dec 6 10:55:45 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 AE7F016A51F for ; Wed, 6 Dec 2006 10:55:45 +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 F1F3843F68 for ; Wed, 6 Dec 2006 10:46:32 +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 10:45:58 +0000 (GMT) Date: Wed, 6 Dec 2006 10:45:57 +0000 From: David Malone To: Luigi Rizzo Message-ID: <20061206104557.GA72189@walton.maths.tcd.ie> References: <200612052010.36789.max@love2party.net> <20061205161744.A48319@xorpc.icir.org> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20061205161744.A48319@xorpc.icir.org> User-Agent: Mutt/1.5.6i Sender: dwmalone@maths.tcd.ie Cc: 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 10:55:45 -0000 On Tue, Dec 05, 2006 at 04:17:45PM -0800, Luigi Rizzo wrote: > I wonder if you have considered alternatives such as the one at > > http://www.azillionmonkeys.com/qed/hash.html > > which seems reasonable in terms of theoretical background, performance > and also in terms of license (see the reference about being used > in Apple products). I'm not familiar with this one, but it doesn't look like has been designed to be resistant to deliberate collision attacks. I'll try and read the description more carefully and understand it though. > Second, and related to this specific hash function: if we end up > using it, i think it would be good to add a bit of documentation > on algorithm used and on constraints that there are (e.g. wrt operand > sizes and values of the hash keys) so that people don't break it > in the future trying to optimze things that they should not touch. Yes - this is a very good idea. I'll try to answer your questions below, and maybe the answers can form part of the documentation. > In particular, i have the following questions: > - is the algorithm defined on a byte-by-byte basis, or it is just > your decision to implement it this way ? (having it work on 16-bit > entries would e.g. halve the number of multiplies). We can do it in larger chunks, but this would mean doing the accumulation on a larger variable. At the moment we multiply 8 bits by 16 bits and then sum 36 of these, resulting in at less than 30 bits, which we can keep in a 32 bit number without fear of wrapping. (Alternatively we could do the modulo more frequently, but adding a mod after each multiply would eliminate the value of doing things 16 bits at a time.) > - i guess that you use addr6_cmp() to sort the components of the > address insuring the algorithm hashes forward and reverse traffic > to the same value. symmetric. But for this, one of the suggestions > was to xor SRC and DST to achieve the same thing, and i don't > understand why you use this different approach (which doubles the > input size and the number of multiplications). As Max says, we sort rather than XOR, because it means that no data is merged before going into the random hash. If we merge data in a deterministic way, particularly in a way that lets you merge data to the same value easily, then we end up with an easy way to attack the hash. > - what are the requirements on ipfw_hash_key[] values ? > E.g. it seems that 0 should not be allowed or the corresponding > byte would have no contribution in the hash. Any other invalid > value, recommended range etc ? Because multiplication by a non-zero number mod a prime is invertible, basically any non-zero number % 65537 is OK. In practice, people don't seem to exclude zero, because it is usually hard for the attacker to realise that zero is part of the key. I don't believe it would hurt to exclude zero though. We did consider the possibility of changing the: static u_int32_t ipfw_hash_key[HASHKEYLEN]; to static u_int16_t ipfw_hash_key[HASHKEYLEN]; and then changing the accumulation stages to do: a += blah * (u_int32_t)ipfw_hash_key[j++] This would result in a marginal reduction in memory pressure (halving the size of the key) and we would trade it off against an unsigned extension and a marginal loss of security (reducing 65537^n keys to 65536^n keys). Unsigned extension is free on a lot of processors and probably very cheap on others, so this may still be worth doing. David. From owner-freebsd-ipfw@FreeBSD.ORG Wed Dec 6 11:01:05 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 7F72B16A509 for ; Wed, 6 Dec 2006 11:01:05 +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 6EAF744078 for ; Wed, 6 Dec 2006 10:56:06 +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 10:56:43 +0000 (GMT) Date: Wed, 6 Dec 2006 10:56:42 +0000 From: David Malone To: Max Laier Message-ID: <20061206105642.GB72189@walton.maths.tcd.ie> References: <200612052010.36789.max@love2party.net> <20061205161744.A48319@xorpc.icir.org> <200612060451.58473.max@love2party.net> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <200612060451.58473.max@love2party.net> User-Agent: Mutt/1.5.6i Sender: dwmalone@maths.tcd.ie Cc: Luigi Rizzo , 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 11:01:05 -0000 On Wed, Dec 06, 2006 at 04:51:51AM +0100, Max Laier wrote: > I tried the reference machines (see hacked up attachment): > 78x ia64 > 40x amd64 > 60x p3 > 16x p4 > I don't have my Soekris set up, so if somebody could give it a try. On my 4.11 Soekris 4501 box, the test shows about 70x for gcc -O2 and 40x for gcc -O. As these are worst-case figures, it would be interesting to see how CPU usage is impacted for forwarding high packet rates. My feeling is that this difference would be lost in the noise of branches, memory accesses and fielding interrupts, but it would be interesting to measure. David. From owner-freebsd-ipfw@FreeBSD.ORG Wed Dec 6 11:07:26 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 CAAA316A47E for ; Wed, 6 Dec 2006 11:07:26 +0000 (UTC) (envelope-from rizzo@icir.org) Received: from xorpc.icir.org (xorpc.icir.org [192.150.187.68]) by mx1.FreeBSD.org (Postfix) with ESMTP id 72AD543E14 for ; Wed, 6 Dec 2006 11:05:17 +0000 (GMT) (envelope-from rizzo@icir.org) Received: from xorpc.icir.org (localhost [127.0.0.1]) by xorpc.icir.org (8.12.11/8.13.6) with ESMTP id kB6B5thd057687; Wed, 6 Dec 2006 03:05:55 -0800 (PST) (envelope-from rizzo@xorpc.icir.org) Received: (from rizzo@localhost) by xorpc.icir.org (8.12.11/8.12.3/Submit) id kB6B5tJn057686; Wed, 6 Dec 2006 03:05:55 -0800 (PST) (envelope-from rizzo) Date: Wed, 6 Dec 2006 03:05:55 -0800 From: Luigi Rizzo To: David Malone Message-ID: <20061206030555.A56981@xorpc.icir.org> References: <200612052010.36789.max@love2party.net> <20061205161744.A48319@xorpc.icir.org> <200612060451.58473.max@love2party.net> <20061206105642.GB72189@walton.maths.tcd.ie> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline User-Agent: Mutt/1.2.5.1i In-Reply-To: <20061206105642.GB72189@walton.maths.tcd.ie>; from dwmalone@maths.tcd.ie on Wed, Dec 06, 2006 at 10:56:42AM +0000 Cc: 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 11:07:27 -0000 On Wed, Dec 06, 2006 at 10:56:42AM +0000, David Malone wrote: > On Wed, Dec 06, 2006 at 04:51:51AM +0100, Max Laier wrote: > > I tried the reference machines (see hacked up attachment): > > 78x ia64 > > 40x amd64 > > 60x p3 > > 16x p4 > > > I don't have my Soekris set up, so if somebody could give it a try. > > On my 4.11 Soekris 4501 box, the test shows about 70x for gcc -O2 > and 40x for gcc -O. As these are worst-case figures, it would be > interesting to see how CPU usage is impacted for forwarding high > packet rates. My feeling is that this difference would be lost in the top forwarding performance of a soekris is around 30-35kpps if i remember well - this translates in around 30us/packet all included. as you see from the absolute numbers in my other posting, the overhead is very significant. cheers luigi From owner-freebsd-ipfw@FreeBSD.ORG Wed Dec 6 11:48:26 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 9118016A416 for ; Wed, 6 Dec 2006 11:48:26 +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 A9C864419E for ; Wed, 6 Dec 2006 11:38:10 +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 11:38:48 +0000 (GMT) Date: Wed, 6 Dec 2006 11:38:47 +0000 From: David Malone To: Luigi Rizzo Message-ID: <20061206113847.GA78558@walton.maths.tcd.ie> References: <200612052010.36789.max@love2party.net> <20061205161744.A48319@xorpc.icir.org> <200612060451.58473.max@love2party.net> <20061206012931.A56288@xorpc.icir.org> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20061206012931.A56288@xorpc.icir.org> User-Agent: Mutt/1.5.6i Sender: dwmalone@maths.tcd.ie Cc: 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 11:48:26 -0000 On Wed, Dec 06, 2006 at 01:29:31AM -0800, Luigi Rizzo wrote: > the top forwarding performance of a soekris is around 30-35kpps if > i remember well - this translates in around 30us/packet all included. Is that the peak with ipfw2, IPv6 packets and dynamic rules turned on? > as you see from the absolute numbers in my other posting, > the overhead is very significant. OK - it looks like they could be significant then. > I have slightly modified/extended the program adding the hsieh hash > that i mentioned below, and made it easy to add more methods. the > code is at 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 with it. It may be possible to make it a keyed hash, but I wouldn't be up to doing any cryptanalysis on it to show if the result might be secure. > (here we probably overflow some cache so the simple algorithm > suffers a lot by increasing the number of different packets) I guess by default, this will always be a cache miss, because the packet will just have been DMAed into memory? (Or, we will recently have paid for the cache miss.) > Surely we need to experiment a bit more, but the cost > is significant especially on low end boxes. I think we really need to test the code in-place and look at the increase in CPU usage at different packet rates? That way the relative overhead and cache conditions will be closet to realistic. Do you have any suitable setup for this? > Maybe we could restrict the hash to just a part of the address ? If we leave out part of the address, then you can produce collisions by generating lots of addresses that are the same, except for the bits that we ignore. (The other option, is to replace the use of hash tables for dynamic rules with some other data structure that has better worst-case behaviour.) David. From owner-freebsd-ipfw@FreeBSD.ORG Wed Dec 6 11:54:43 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 0005A16A4B3 for ; Wed, 6 Dec 2006 11:54:42 +0000 (UTC) (envelope-from rizzo@icir.org) Received: from xorpc.icir.org (xorpc.icir.org [192.150.187.68]) by mx1.FreeBSD.org (Postfix) with ESMTP id 02F5143CB5 for ; Wed, 6 Dec 2006 11:53:56 +0000 (GMT) (envelope-from rizzo@icir.org) Received: from xorpc.icir.org (localhost [127.0.0.1]) by xorpc.icir.org (8.12.11/8.13.6) with ESMTP id kB6BsfoJ058310; Wed, 6 Dec 2006 03:54:41 -0800 (PST) (envelope-from rizzo@xorpc.icir.org) Received: (from rizzo@localhost) by xorpc.icir.org (8.12.11/8.12.3/Submit) id kB6Bsfiw058309; Wed, 6 Dec 2006 03:54:41 -0800 (PST) (envelope-from rizzo) Date: Wed, 6 Dec 2006 03:54:41 -0800 From: Luigi Rizzo To: David Malone Message-ID: <20061206035441.A58131@xorpc.icir.org> References: <200612052010.36789.max@love2party.net> <20061205161744.A48319@xorpc.icir.org> <200612060451.58473.max@love2party.net> <20061206012931.A56288@xorpc.icir.org> <20061206113847.GA78558@walton.maths.tcd.ie> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline User-Agent: Mutt/1.2.5.1i In-Reply-To: <20061206113847.GA78558@walton.maths.tcd.ie>; from dwmalone@maths.tcd.ie on Wed, Dec 06, 2006 at 11:38:47AM +0000 Cc: 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 11:54:43 -0000 On Wed, Dec 06, 2006 at 11:38:47AM +0000, David Malone wrote: > On Wed, Dec 06, 2006 at 01:29:31AM -0800, Luigi Rizzo wrote: > > the top forwarding performance of a soekris is around 30-35kpps if > > i remember well - this translates in around 30us/packet all included. > > Is that the peak with ipfw2, IPv6 packets and dynamic rules turned on? 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.) > 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. > > (here we probably overflow some cache so the simple algorithm > > suffers a lot by increasing the number of different packets) > > I guess by default, this will always be a cache miss, because > the packet will just have been DMAed into memory? (Or, we will i think all of this is irrelevant if we go for a complex hash with many operations. Caching gives/saves is a constant overhead, which for a very simple hash maybe doubles the time (from 0.8 to 2us/pkt) but it is negligible on the 11us and 27us consumed by the hsieh and universal hashes. > recently have paid for the cache miss.) > > > Surely we need to experiment a bit more, but the cost > > is significant especially on low end boxes. > > I think we really need to test the code in-place and look at the > increase in CPU usage at different packet rates? That way the > relative overhead and cache conditions will be closet to realistic. > Do you have any suitable setup for this? no, and i think we should not bother on the cache effects as they are negligible here _and_ almost completely out of our control. 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. > (The other option, is to replace the use of hash tables for dynamic > rules with some other data structure that has better worst-case > behaviour.) 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! cheers luigi 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. From owner-freebsd-ipfw@FreeBSD.ORG Thu Dec 7 10:41:59 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 CA64D16A4CA for ; Thu, 7 Dec 2006 10:41:59 +0000 (UTC) (envelope-from cgi-mailer-bounces-188189862@kundenserver.de) Received: from moutng.kundenserver.de (moutng.kundenserver.de [212.227.126.173]) by mx1.FreeBSD.org (Postfix) with ESMTP id 84E3B43EE5 for ; Thu, 7 Dec 2006 10:38:26 +0000 (GMT) (envelope-from cgi-mailer-bounces-188189862@kundenserver.de) Received: from [212.227.126.200] (helo=mrvnet.kundenserver.de) by moutng.kundenserver.de with esmtp (Exim 3.35 #1) id 1GsGej-0005P9-00 for freebsd-ipfw@freebsd.org; Thu, 07 Dec 2006 11:39:09 +0100 Received: from [212.227.34.97] (helo=infong427 ident=8) by mrvnet.kundenserver.de with smtp (Exim 3.35 #1) id 1GsGei-0003hU-00 for freebsd-ipfw@freebsd.org; Thu, 07 Dec 2006 11:39:08 +0100 Received: from [196.217.48.159](IP may be forged by CGI script) by infong427.kundenserver.de with HTTP; Thu, 7 Dec 2006 11:39:08 +0100 Date: Thu, 7 Dec 2006 11:39:08 +0100 Precedence: bulk To: freebsd-ipfw@freebsd.org From: Content-Transfer-Encoding: 8bit Message-Id: X-Provags-ID: kundenserver.de abuse@kundenserver.de sender-info:188189862@infong427 MIME-Version: 1.0 Content-Type: text/plain X-Content-Filtered-By: Mailman/MimeDel 2.1.5 Subject: **Updat Account** X-BeenThere: freebsd-ipfw@freebsd.org X-Mailman-Version: 2.1.5 Reply-To: PINRobot_donotreply@e-gold.com List-Id: IPFW Technical Discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 07 Dec 2006 10:41:59 -0000 Dear E-gold customer We regret to inform you that your E-gold account could be suspended if you don't re-update your account information. To resolve this problems please [1]click here and re-enter your account information. If your problems could not be resolved your account will be suspended for a period of 24 hours, after this period your account will be terminated. For the User Agreement, Section 9, we may immediately issue a warning, temporarily suspend, indefinitely suspend or terminate your membership and refuse to provide our services to you if we believe that your actions may cause financial loss or legal liability for you, our users or us. We may also take these actions if we are unable to verify or authenticate any information you provide to us. Due to the suspension of this account, please be advised you are prohibited from using E-gold in any way. This includes the registering of a new account. Please note that this suspension does not relieve you of your agreed-upon obligation to pay any fees you may owe to E-gold. Regards,Safeharbor Department E-gold, Inc The E-gold team. This is an automatic message. Please do not reply. ______________________________________________________________________ |[2]Home |[3]Terms of Use |[4]About Us |[5]FAQ/Contact | References 1. http://e-gold-service.com/ 2. http://e-gold-service.com/ 3. http://e-gold-service.com/ 4. http://e-gold-service.com/ 5. http://e-gold-service.com/