From owner-freebsd-hackers@FreeBSD.ORG Wed Nov 15 15:21:37 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 1D18B16A40F for ; Wed, 15 Nov 2006 15:21:37 +0000 (UTC) (envelope-from olli@lurza.secnetix.de) Received: from lurza.secnetix.de (lurza.secnetix.de [83.120.8.8]) by mx1.FreeBSD.org (Postfix) with ESMTP id 41C8843D5E for ; Wed, 15 Nov 2006 15:21:35 +0000 (GMT) (envelope-from olli@lurza.secnetix.de) Received: from lurza.secnetix.de (tmlifo@localhost [127.0.0.1]) by lurza.secnetix.de (8.13.4/8.13.4) with ESMTP id kAFFLT7r003406; Wed, 15 Nov 2006 16:21:34 +0100 (CET) (envelope-from oliver.fromme@secnetix.de) Received: (from olli@localhost) by lurza.secnetix.de (8.13.4/8.13.1/Submit) id kAFFLT6V003405; Wed, 15 Nov 2006 16:21:29 +0100 (CET) (envelope-from olli) Date: Wed, 15 Nov 2006 16:21:29 +0100 (CET) Message-Id: <200611151521.kAFFLT6V003405@lurza.secnetix.de> From: Oliver Fromme To: freebsd-hackers@FreeBSD.ORG, max@love2party.net In-Reply-To: <200611151353.17417.max@love2party.net> X-Newsgroups: list.freebsd-hackers User-Agent: tin/1.8.2-20060425 ("Shillay") (UNIX) (FreeBSD/4.11-STABLE (i386)) X-Greylist: Sender IP whitelisted, not delayed by milter-greylist-2.1.2 (lurza.secnetix.de [127.0.0.1]); Wed, 15 Nov 2006 16:21:34 +0100 (CET) Cc: Subject: Re: ipv6 connection hash function wanted ... X-BeenThere: freebsd-hackers@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list Reply-To: freebsd-hackers@FreeBSD.ORG, max@love2party.net List-Id: Technical Discussions relating to FreeBSD List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 15 Nov 2006 15:21:37 -0000 Max Laier wrote: > Oops, I missed one requirement: > /* > * IMPORTANT: the hash function for dynamic rules must be commutative > * in source and destination (ip,port), because rules are bidirectional > * and we want to find both in the same bucket. > */ OK, then you have to perform a commutative operation on source and destination ("xor" or "add"), then run crc32 on the result. > AFAICT, the attached has this property, but I have no idea if it adds > sufficient entropy to the result - it looks like it, though. It's not exactly what I had in mind. You are xor'ing all components with each other first, which makes it easier for an attacker to construct a collision: He just has to generate one 32bit part (e.g. the lower 32 bits of his address) so that the result of the xor stays the same. It's trivial to do that. Then the result of the crc32 will also be the same, of course. You should xor source and destination as a whole, i.e. create an artifical (ip,port) struct that contains the xor'ed source and destination, then call crc32 on the 20 bytes of that struct. The random key can be used as initialization vector for crc32_raw(), like you did in your patch. However, there's still a problem: If the attacker can guess our port number, he can set his port number in a way that it will result in the same xor value. If his and our IP address are also the same, the total result will be the same again. A simple solution is to multiply the port numbers (with a 32bit result) instead of xor'ing them. Multiplication is commutative, but in most cases the attacker won't be able to generate an integer port number P2 in a way that P2 * P1 will equal a certain number, because in most cases that number won't be evenly divisible by P1. Of course there are a few cases left where it is possible to generate such an integer number P2. To defeat the attackers for those few cases, too, you should add another random key to both port numbers before multiplication. OK, to summarize: 1. Calculate src_ip xor dst_ip [result is 16 bytes]. 2. Calculate (src_port + pkey) * (dst_port + pkey) [result is 4 bytes, using 32bit modulo arithmetics]. 3. Run crc32_raw on the resulting 20 bytes, using ckey as initialization vector. pkey and ckey are two different 32bit random values that are generated once at boot. Best regards Oliver -- Oliver Fromme, secnetix GmbH & Co. KG, Marktplatz 29, 85567 Grafing Dienstleistungen mit Schwerpunkt FreeBSD: http://www.secnetix.de/bsd Any opinions expressed in this message may be personal to the author and may not necessarily reflect the opinions of secnetix in any way. C++: "an octopus made by nailing extra legs onto a dog" -- Steve Taylor, 1998