Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!nntp.club.cc.cmu.edu!feeder.erje.net!news-1.dfn.de!news.dfn.de!fu-berlin.de!uni-berlin.de!individual.net!not-for-mail
From: Rainer Weikusat <rweikusat@mssgmbh.com>
Newsgroups: comp.os.linux.development.system
Subject: Re: xfrm spi hash
Date: Sun, 12 Aug 2012 22:17:42 +0100
Lines: 27
Message-ID: <87628n7qtl.fsf@sapphire.mobileactivedefense.com>
References: <87y5m25q36.fsf@sapphire.mobileactivedefense.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
X-Trace: individual.net gx9VSKw6kSzwuLgC9omkIA/6pTuw19tFjNTiSxw1hycb/8yLZkL+jF0bqbAqo8QbM=
Cancel-Lock: sha1:jfvVFunhDYjOYdolQa+QP9XwrKI= sha1:wuX3Rl9m5FRcUTuDdfBp+mY9x9U=
User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.2 (gnu/linux)
Xref: csiph.com comp.os.linux.development.system:458

Rainer Weikusat <rweikusat@mssgmbh.com> writes:

[64K pointers hash table]

> Assuming the PRNG the kernel uses to generate the SPI is 'good' in
> the sense that a sequences of SPIs is statistically
> indistinguishable from a random sequence, the only effect of these
> calculations ought to be to transform a random set of bits into a
> different, equally random set of bits with no specific relation to
> any of the other input values whatsoever. I'm therefore very much
> tempted to drop all of it and just use the SPI as hash value.

Just using the lower sixteen bit of the SPI as hash value lead to a
'good enough' result I didn't really like. With the help some 'evil
inside knowledge' about the SPI numbers which are actually generated
by Linux and by the clients connecting to these VPN servers (Apple
'i'-devices or Android-based somethings), I arrived at the following
calculation:

(spi ^ ((spi & 0xffff0000) >> 12)) % 65536

For the presently largest installation, where 0 - 1732 new phase2 SAs
are created per 5 minutes interval (average 452.75, std. dev 230.34,
median 412), this results between 0 and 1.54% collisions during this
time (avg 0.25%, std dev 0.27%, median 0.21%).