[Swan-dev] hash table size and hash

[Andrew Cagney]

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/20171018/b984b502/attachment.html>