From mboxrd@z Thu Jan 1 00:00:00 1970 From: "Nikolaos D. Bougalis" Subject: Re: RFC: Established connections hash function Date: Fri, 23 Mar 2007 05:45:30 -0700 Message-ID: References: <391F64D0A7C5463CA2D70362E4B3E7EC@XEON> <20070322182156.GB17793@2ka.mipt.ru> <1199CE22A40740D28833A585014BE559@XEON> <20070322.135834.74723088.davem@davemloft.net> <20070323080715.GB29991@2ka.mipt.ru> Reply-To: nikb@webmaster.com Mime-Version: 1.0 Content-Type: text/plain; format=flowed; charset="koi8-r"; reply-type=original Content-Transfer-Encoding: 7bit To: Return-path: Received: from mail1.webmaster.com ([216.152.64.169]:1081 "EHLO mail1.webmaster.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S934045AbXCWMpg (ORCPT ); Fri, 23 Mar 2007 08:45:36 -0400 Received: from XEON by webmaster.com (Cipher TLSv1:RC4-MD5:128) (MDaemon.PRO.v8.1.3.R) with ESMTP id md50001458257.msg for ; Fri, 23 Mar 2007 05:45:44 -0800 In-Reply-To: <20070323080715.GB29991@2ka.mipt.ru> Sender: netdev-owner@vger.kernel.org List-Id: netdev.vger.kernel.org Let me start off by saying that I hope I didn't come across as condenscending in my previous posts. If I did, then it wasn't intended. Now, on to more important things :) > jhash_2words(const, const, ((const << 16) | $sport) ^ $random) > > where $sport is 1-65535 in a loop, and $random is pseudo-random number > obtained on start. If you are correct that jhash_3words doesn't properly distribute the bits in 'c' (which I don't believe you are, but let's assume it for a second) then this function will also be broken: jhash_2words calls jhash_3words; jhash_3words adds (a linear operation) initval and c before calling __jhash_mix. So, if there is a problem with passing values under the direct control of the attacker into 'c' both jhash_2words and jhash_3words are affected; in other words, this variant would also be flawed. > Which is exactly the case of web server and attacker connects to 80 port > from the same IP address and different source ports. > > Result with jenkins: > 1 23880 > 2 12108 > 3 4040 > 4 1019 > 5 200 > 6 30 > 7 8 > 8 1 > > Xor: > 1 65536 I believe that the XOR results, if generated by your test above, are somewhat meaningless because you're feeding what is ideal input into the XOR hash. Which means that you'll get a perfect distribution. With your input, one might as well suggest that using the remote port will give a perfect distribution, and it will, but only for that specific input. Just for kicks, I went to one of our servers, and did "netstat -n | grep ESTABLISHED" and ended up with 31072 distinct ip:port/ip:port 4-tuples which I then hashed into a 65536 bucket table. There are the results; feel free to draw your own conclusions: [ I think this should come out looking good; sorry if whitespace is screwy ] +---+-------+-------+-------+-------+ | | xor | j2w 1 | j2w 2 | j3w 1 | +---+-------+---------------+-------+ | 0 | 40868 | 40930 | 40767 | 40750 | | 1 | 19208 | 19119 | 19382 | 19413 | | 2 | 4636 | 4618 | 4576 | 4554 | | 3 | 716 | 769 | 715 | 734 | | 4 | 99 | 91 | 87 | 76 | | 5 | 7 | 8 | 9 | 9 | | 6 | 1 | 1 | 0 | 0 | | 7 | 1 | 0 | 0 | 0 | | 8 | 0 | 0 | 0 | 0 | +---+-------+-------+-------+-------+ xor: the vanilla linux function j2w 1 is my variant: jhash_2words(laddr + rport, raddr + lport, seed) j2w 2 is your variant: jhash_2words(laddr, raddr, (rport << 16) ^ lport) ^ seed) j3w: jhash_3words(laddr, raddr, (rport << 12) + lport, seed) The seed used for all the Jenkins hashes came from the low-order 32-bits returned by RDTSC, executed when the program started. It remained constant throughout the run. 8 runs where made, to ensure that the seed wasn't causing weirdness, all runs giving almost identical results. The Jenkins hashes did not use the extra 2 right-shifts to fold high-order bits into the low-order bits, that is employed by the XOR hash. -n