netdev - Re: [PATCH net-next 1/3] rhashtable: Add a function for in order insertion in buckets

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <CALx6S37KRjff719DT_+f2EXoJ6ehdvX7P-jvgca9cTiHCSrkDg@mail.gmail.com>
Date:	Tue, 14 Jul 2015 17:59:53 -0700
From:	Tom Herbert <tom@...bertland.com>
To:	Herbert Xu <herbert@...dor.apana.org.au>
Cc:	"David S. Miller" <davem@...emloft.net>,
	Linux Kernel Network Developers <netdev@...r.kernel.org>,
	Thomas Graf <tgraf@...g.ch>, Kernel Team <kernel-team@...com>
Subject: Re: [PATCH net-next 1/3] rhashtable: Add a function for in order
 insertion in buckets

On Tue, Jul 14, 2015 at 4:58 PM, Herbert Xu <herbert@...dor.apana.org.au> wrote:
> On Tue, Jul 14, 2015 at 09:42:49AM -0700, Tom Herbert wrote:
>>
>> Scored lookups can provides the same functionality, but requires that
>> we scan all the elements so I see some overhead compared to doing
>> ordered insertion. One way to resolve the rehash problem is search any
>> future table after we find a hit in the first table to see if there
>> are any entries that would precede the element already found. So in
>> the common non-rehash case lookup happens as it does now except that
>> we would always check for future_tbl.
>
> There is another problem with this approach and that is it breaks
> the logic for determining hash collission attack.  Since you're
> intentionally inserting multiple elements with the same hash, the
> chain length would be inflated.
>
Conceptually, I agree with you, but I would point out that we've had
this model of intentional collisions for a while in socket lookup. I
would assume that it's a goal to use rhashtable for socket tables, so
we'll need some solution that works with that!

> The other reason I wanted to have this logic outside of rhashtable
> is because for IPsec, the wildcards may in fact change after a
> "rehash".  For example we may move from a /32 granularity to a
> /31 granlarity at the requst of the admin.  In that case you can't
> just mix the chain from the old table with the new.
>
Where ordering elements in the table can't be sustained, scoring would
be used (e.g. scoring function can be changed on the fly, but ordering
rules can't be).

Tom

> Cheers,
> --
> Email: Herbert Xu <herbert@...dor.apana.org.au>
> Home Page: http://gondor.apana.org.au/~herbert/
> PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
--
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html