Re: Question about tcp hash function tcp_hashfn()

[Evgeniy Polyakov <johnpol@2ka.mipt.ru>]

On Thu, Jun 01, 2006 at 04:24:57AM -0600, Brian F. G. Bidulock (bidulock@openss7.org) wrote:
> For purely random numbers you could amplify thermal noise off an
> open transitor junction (the audiofile's white noise generator)
> and feed it into an analog to digital converter.

It is also possible to look into window and count how many times sun
hides and shines... It is quite cloudy in Moscow though.

As Acrypto asynchronous crypto layer author I can use different hardware
crypto accelerators, but it is a topic for another discussion.

> > 
> > I've run it with following source ip/port selection algo:
> > 	if (++sport == 0) {
> > 		saddr++;
> > 		sport++;
> > 	}
> > 
> > Starting IP was 1.1.1.1 and sport was 1.
> > Destination IP and port are the same 192.168.0.1:80
> > 
> > Jenkins hash started to show different behaviour:
> > it does not have previous artefacts, but instead it's dispersion is
> > _much_ wider than in XOR case.
> 
> Aha!  But perhaps this is too easy a data set.  HTTP clients typically
> dynamically allocate port numbers within a range and source address
> are typically not less than a certain value.  That is why I suggested
> something like:
> 
>        sport = 10000;
>        saddr = 0x0a000000;  /* 10.0.0.0 */
> 
>        ...
> 
>        if (++sport == 16000) {
> 	       sport = 10000;
> 	       saddr++;
>        }
> 
> If this shows artifacts worse than XOR then more realistic gaps in the
> input values will cause artifacts.

Specially for you :)
It does not have artifacts, but it's dispersion is wider than XOR one.
_Much_ wider, which tends to creation of some specially crafted source
distribution which ends up in totally broken fairness.
As usual folded and not folded versions behave exactly the same.

> > With following ip/port selection algo:
> > 	if (++sport == 0) {
> > 		//saddr++;
> > 		sport += 123;
> > 	}
> > 
> > I see yet another jenkins artefacts, but again different from previous
> > two.
> 
> Adding primes.  Again, the arithmetic series of primes might auto-correlate
> with the Jenkins function.  Or it plain might not like gaps.
>

I want to confirm three things and one state:
1. Jenkins hash has some unacceptible artefacts in some source
address/port distributions, no matter if it has some law embedded or it
is (pseudo)-random set. 

If there are bugs, bugs exist.

2. If it does not have artifacts it has unacceptible dispersion.

3. It is 3 times slower than XOR one (28 seconds for XOR for 2^29
iterations vs. 101 seconds jhash nonfolded and 109 jhash folded on my AMD64
3500+ 2.2 Ghz desktop).

4. I believe it can be tuned or has some gaps inside refactoring logic,
which can be fixed, but as is it can not be used for fair hash creation.

-- 
	Evgeniy Polyakov
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/