[Swan-dev] hash table size and hash
Andrew Cagney
andrew.cagney at gmail.com
Thu Oct 26 14:42:54 UTC 2017
FYI,
I pushed the changes:
- first, the linked list and hash table were made generic (I needed a hash
table to manage PIDs)
The the code was forked before 8e047dd53da900445dda569041ac602740d66de0 so
some of that didn't get copied over (I noticed it while merging this week
and testing was already painful enough); looking through it I think the
always-circular change could be re-merged but as part of code explicitly
allocating initializing and freeing the heaps and lists - to do dynamic
sizing of the heap we'll need this anyway.
- the state contain 499 slots
There's a rule of thumb that says hash tables should be ~50% full (true?)
but I've seen pluto with 1000 entries so we might need that dynamic resize
code; hopefully I've structured things to be friendly to that change; later
- for icookies it uses:
* 251 is a prime close to 256 (so like <<8).
for (unsigned j = 0; j < COOKIE_SIZE; j++) {
hash = hash * 251 + icookie[j];
}
- and for icookie+rcookie it uses:
* 251 is a prime close to 256 aka <<8. 65521 is a prime
* close to 65536 aka <<16.
for (unsigned j = 0; j < COOKIE_SIZE; j++) {
hash = hash * 65521 + icookie[j] * 251 + rcookie[j];
}
- hopefully 499, 251 and 65521 are all primes
- like the comments also say, there's no real rationale for doing this.
- there's also an ordered list available
Andrew
On 18 October 2017 at 16:40, Andrew Cagney <andrew.cagney at gmail.com> wrote:
>
>
> On 18 October 2017 at 15:51, D. Hugh Redelmeier <hugh at mimosa.com> wrote:
>
>> | From: Andrew Cagney <andrew.cagney at gmail.com>
>> | To: Libreswan Development List <swan-dev at lists.libreswan.org>
>>
>> | - icookie+zero-cookie (we probably shouldn't include the zero-cookie in
>> the
>> | hash but it should do no harm :-)
>> | - icookie+rcookie
>> |
>> | these use:
>> |
>> | for (j = 0; j < COOKIE_SIZE; j++)
>> | i = i * 407 + icookie[j] + rcookie[j];
>> |
>> | where 407 isn't prime (does anyone know where 407 came from? if not I'll
>> | change that to a prime 521 which I'm choosing randomly) and I'll change
>> the
>> | math to:
>> |
>> | i * 521 + icookie << 8 + rcookie
>> |
>> | So that we don't allow the cookies to cancel out (I could reply with
>> | rcookie = 255 - icookie making the hash very non-random),
>>
>> I'm surely responsible for the hash. I'm sure that I had a reason for
>> 407 but if their is no comment, that reason is lost. I think that I
>> wanted it to be in the middle of the range (256,512).
>>
>>
> So if I concatenate the two bytes, something between 32k and 64k would be
> better.
>
> Faster hashing could be done by treating the cookies as a sequence of
>> uint32_t values. I don't think that there has to be an alignment
>> problem since the cookies are at the start of a packet.
>>
>>
> That might be interesting. But from my pov, later.
>
> How should one combine the values? A commutative operation (^ or + or
>> +) hashes permutations to the same value, which seems questionable.
>>
>>
> Ideally it should be viewed as a very large integer.
>
> To prevent some attacks, it might be good to mix in something private.
>> That private thing ought to be determined once per run of pluto. (If
>> it changes in the middle of a run, the has table would need to be
>> rehashed. This is pointless if an attacker could deduce the private
>> thing, say by a timing attack.
>>
>>
>> I don't think it is worth it. Our half is always random so only when
> they carefully construct some strange sequence of cookies resulting in a
> single hash things will get slow. And if that happens the code requiring
> an initial cookie exchange would kick in.
>
> Andrew
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.libreswan.org/pipermail/swan-dev/attachments/20171026/313c902b/attachment.html>
More information about the Swan-dev
mailing list