xfrm spi hash

[Rainer Weikusat]

Leading remark: The following text will probably very cryptic to
anynone not familiar with the inner workings of the racoon IKE
implementation and the process of establishing IPsec-based 'VPN
tunnels'. There's a more general question at the end but I think I
should also include enough background information to communicate the
general situation.

Recently, I replaced the SADB_DUMP-based mechanism racoon uses to get
completely rid of all phase2 IPsec SAs associated with a particular
phase1 SA with 'something sane' based on using already available
information to determine the phase2 SAs to be removed. Because I need
to do accounting for 'user VPNs', deleteing a kernel phase2 SA/ xfrm
state is a two step procedure comprised of first sending a SADB_GET
message to the kernel in order to get the traffic counters and then
deleting it. The code which deals with the replies to this get message
needs to find the corresponding ph2handle structures of the daemon
based on using SPI, source and destination address and the IPsec
protocol ID. The racoon code keeps all ph2handles on a global linked
list and locates a specific one by searching this list using 'some
comparison criterion'. In the case of a SPI-based search, that's a
particular atrocious procedure because a SPI may be stored in one of
two members of a saproto structure, a linked list of which is hooked
to a saprop structure and the ph2handle structure itself contains two
linked lists of these. This seemed a little gross to be and because of
that, I added a static (64K pointers) hash table to be used for these
lookups.

Since the same problem needs to be solved by the kernel, I
looked at the kernel source in order to see what kind of hash function
Linux uses for this. For IPv4, it is essentially

x = spi ^ proto ^ ntohl(daddr);

The spi is a (pseudo-)random 32-bit value, proto is the eight bit
protocol ID and daddr is the IPv4 destination address. This value is
then post-processed as

x = x ^ (x >> 10) ^ (x >> 20);

to calculate the hash value. Since it is usually pointless to change
something which is known to work, I used the same calculation for my
code. But since this is a relativley expensive calculation, I
continued to think about it and some doubts about it arose: 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. Is there some kind of obvious error in this
reasoning or does anyone know something about the raison d'etre for
this specific hash function?

[Rainer Weikusat]

Rainer Weikusat <rwei...@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%).