linux-kernel - Re: Question on rhashtable in worst-case scenario.

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: <1459410405.4576.8.camel@sipsolutions.net>
Date:	Thu, 31 Mar 2016 09:46:45 +0200
From:	Johannes Berg <johannes@...solutions.net>
To:	Ben Greear <greearb@...delatech.com>,
	David Miller <davem@...emloft.net>
Cc:	linux-kernel@...r.kernel.org, herbert@...dor.apana.org.au,
	linux-wireless@...r.kernel.org, netdev@...r.kernel.org,
	tgraf@...g.ch
Subject: Re: Question on rhashtable in worst-case scenario.

On Wed, 2016-03-30 at 09:52 -0700, Ben Greear wrote:

> If someone can fix rhashtable, then great.
> I read some earlier comments [1] back when someone else reported
> similar problems, and the comments seemed to indicate that rhashtable
> was broken in this manner on purpose to protect against hashing
> attacks.
> 
> If you are baking in this type of policy to what should be a basic
> data-type, then it is not useful for how it is being used in
> the mac80211 stack.
> 
> [1]  http://lkml.iu.edu/hypermail/linux/kernel/1512.2/01681.html
> 

That's not really saying it's purposely broken, that's more saying that
Herbert didn't see a point in fixing a case that has awful behaviour
already.

However, I'm confused now - we can much more easily live with
*insertion* failures, as the linked email indicates, than *deletion*
failures, which I think you had indicated originally. Are you really
seeing *deletion* failures?

If there are in fact *deletion* failures then I think we really need to
address those in rhashtable, no matter the worst-case behaviour of the
hashing or keys, since we should be able to delete entries in order to
get back to something reasonable. Looking at the code though, I don't
actually see that happening.

If you're seeing only *insertion* failures, which you indicated in the
root of this thread, then I think for the general case in mac80211 we
can live with that - we use a seeded jhash for the hash function, and
since in the general case we cannot accept entries with identical MAC
addresses to start with, it shouldn't be possible to run into this
problem under normal use cases.

In this case, I think perhaps you can just patch your local system with
the many interfaces connecting to the same AP to add the parameter
Herbert suggested (.insecure_elasticity = true in sta_rht_params). This
is, after all, very much a case that "normal" operation doesn't even
get close to.

johannes