netdev - Re: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin

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]

Date:   Sat, 26 Jan 2019 01:43:41 +0100
From:   Jann Horn <jannh@...gle.com>
To:     Alexei Starovoitov <alexei.starovoitov@...il.com>
Cc:     "Paul E. McKenney" <paulmck@...ux.ibm.com>,
        Peter Zijlstra <peterz@...radead.org>,
        Alexei Starovoitov <ast@...nel.org>,
        "David S. Miller" <davem@...emloft.net>,
        Daniel Borkmann <daniel@...earbox.net>,
        jakub.kicinski@...ronome.com,
        Network Development <netdev@...r.kernel.org>,
        kernel-team@...com, Ingo Molnar <mingo@...hat.com>,
        Will Deacon <will.deacon@....com>
Subject: Re: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock

On Sat, Jan 26, 2019 at 12:44 AM Alexei Starovoitov
<alexei.starovoitov@...il.com> wrote:
>
> On Fri, Jan 25, 2019 at 02:51:12PM -0800, Paul E. McKenney wrote:
> > > >
> > > > So no more than (say) 100 milliseconds?
> > >
> > > Depends on RLIMIT_MEMLOCK and on how hard userspace is trying to make
> > > things slow, I guess - if userspace manages to create a hashtable,
> > > with a few dozen megabytes in size, with worst-case assignment of
> > > elements to buckets (everything in a single bucket), every lookup call
> > > on that bucket becomes a linked list traversal through a list that
> > > must be stored in main memory because it's too big for the CPU caches.
> > > I don't know into how much time that translates.
> >
> > So perhaps you have a candidate BPF program for the RCU CPU stall warning
> > challenge, then.  ;-)
>
> I'd like to see one that can defeat jhash + random seed.

Assuming that the map isn't created by root with BPF_F_ZERO_SEED:

The dumb approach would be to put things into the map, try to measure
via timing/sidechannel whether you got collisions, and then keep
trying different keys, and keep them if the timing indicates a
collision. That'd probably be pretty slow and annoying though. Two
years ago, I implemented something similar to leak information about
virtual addresses from Firefox by measuring hash bucket collisions
from JavaScript (but to be fair, it was easier there because you can
resize the hash table):
https://thejh.net/misc/firefox-cve-2016-9904-and-cve-2017-5378-bugreport

But I think there's an easier way, too: The jhash seed is just 32
bits, and AFAICS the BPF API leaks information about that seed through
BPF_MAP_GET_NEXT_KEY: Stuff two random keys into the hash table, run
BPF_MAP_GET_NEXT_KEY with attr->key==NULL, and see which key is
returned. Do that around 32 times, and you should have roughly enough
information to bruteforce the jhash seed? Recovering the seed should
then be relatively quick, 2^32 iterations of a fast hash don't take
terribly long.

That said, I don't think this is interesting enough to spend the time
necessary to implement it. :P