netdev - Re: RFC: Established connections hash function

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:	Fri, 23 Mar 2007 05:45:30 -0700
From:	"Nikolaos D. Bougalis" <nikb@...master.com>
To:	<netdev@...r.kernel.org>
Subject: Re: RFC: Established connections hash function

    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 


-
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html