From: Jann Horn <jannh@google.com>
To: Alexei Starovoitov <alexei.starovoitov@gmail.com>
Cc: "Paul E. McKenney" <paulmck@linux.ibm.com>,
Peter Zijlstra <peterz@infradead.org>,
Alexei Starovoitov <ast@kernel.org>,
"David S. Miller" <davem@davemloft.net>,
Daniel Borkmann <daniel@iogearbox.net>,
jakub.kicinski@netronome.com,
Network Development <netdev@vger.kernel.org>,
kernel-team@fb.com, Ingo Molnar <mingo@redhat.com>,
Will Deacon <will.deacon@arm.com>
Subject: Re: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock
Date: Sat, 26 Jan 2019 01:43:41 +0100 [thread overview]
Message-ID: <CAG48ez1dA8_P9iKE4wqeSvQv-uEQ4HDqP_tp-Pa8Ze39qm3=XA@mail.gmail.com> (raw)
In-Reply-To: <20190125234403.iisj5woztm4afwgh@ast-mbp.dhcp.thefacebook.com>
On Sat, Jan 26, 2019 at 12:44 AM Alexei Starovoitov
<alexei.starovoitov@gmail.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
next prev parent reply other threads:[~2019-01-26 0:44 UTC|newest]
Thread overview: 62+ messages / expand[flat|nested] mbox.gz Atom feed top
2019-01-24 4:13 [PATCH v4 bpf-next 0/9] introduce bpf_spin_lock Alexei Starovoitov
2019-01-24 4:13 ` [PATCH v4 bpf-next 1/9] bpf: " Alexei Starovoitov
2019-01-24 18:01 ` Peter Zijlstra
2019-01-24 18:56 ` Peter Zijlstra
2019-01-24 23:42 ` Paul E. McKenney
2019-01-25 0:05 ` Alexei Starovoitov
2019-01-25 1:22 ` Paul E. McKenney
2019-01-25 1:46 ` Jann Horn
2019-01-25 2:38 ` Alexei Starovoitov
2019-01-25 4:27 ` Alexei Starovoitov
2019-01-25 4:31 ` Paul E. McKenney
2019-01-25 4:47 ` Alexei Starovoitov
2019-01-25 16:02 ` Paul E. McKenney
2019-01-25 4:11 ` Paul E. McKenney
2019-01-25 16:18 ` Jann Horn
2019-01-25 22:51 ` Paul E. McKenney
2019-01-25 23:44 ` Alexei Starovoitov
2019-01-26 0:43 ` Jann Horn [this message]
2019-01-26 0:59 ` Jann Horn
2019-01-24 23:58 ` Alexei Starovoitov
2019-01-25 0:18 ` Jann Horn
2019-01-25 2:49 ` Alexei Starovoitov
2019-01-25 2:29 ` Eric Dumazet
2019-01-25 2:34 ` Alexei Starovoitov
2019-01-25 2:44 ` Eric Dumazet
2019-01-25 2:57 ` Alexei Starovoitov
2019-01-25 8:38 ` Peter Zijlstra
2019-01-25 9:10 ` Peter Zijlstra
2019-01-25 23:42 ` Alexei Starovoitov
2019-01-28 8:24 ` Peter Zijlstra
2019-01-28 8:31 ` Peter Zijlstra
2019-01-28 8:35 ` Peter Zijlstra
2019-01-28 20:49 ` Alexei Starovoitov
2019-01-28 8:43 ` Peter Zijlstra
2019-01-28 21:37 ` Alexei Starovoitov
2019-01-29 8:59 ` Peter Zijlstra
2019-01-30 2:20 ` Alexei Starovoitov
2019-01-25 9:59 ` Peter Zijlstra
2019-01-25 10:09 ` Peter Zijlstra
2019-01-25 10:23 ` Peter Zijlstra
2019-01-26 0:17 ` bpf memory model. Was: " Alexei Starovoitov
2019-01-28 9:24 ` Peter Zijlstra
2019-01-28 21:56 ` Alexei Starovoitov
2019-01-29 9:16 ` Peter Zijlstra
2019-01-30 2:32 ` Alexei Starovoitov
2019-01-30 8:58 ` Peter Zijlstra
2019-01-30 19:36 ` Alexei Starovoitov
2019-01-30 18:11 ` Will Deacon
2019-01-30 18:36 ` Paul E. McKenney
2019-01-30 19:51 ` Alexei Starovoitov
2019-01-30 21:05 ` Paul E. McKenney
2019-01-30 22:57 ` Alexei Starovoitov
2019-01-31 14:01 ` Paul E. McKenney
2019-01-31 18:47 ` Alexei Starovoitov
2019-02-01 14:05 ` Paul E. McKenney
2019-01-30 19:50 ` Alexei Starovoitov
2019-01-24 4:13 ` [PATCH v4 bpf-next 2/9] bpf: add support for bpf_spin_lock to cgroup local storage Alexei Starovoitov
2019-01-24 4:13 ` [PATCH v4 bpf-next 3/9] tools/bpf: sync include/uapi/linux/bpf.h Alexei Starovoitov
2019-01-24 4:13 ` [PATCH v4 bpf-next 4/9] selftests/bpf: add bpf_spin_lock tests Alexei Starovoitov
2019-01-24 4:13 ` [PATCH v4 bpf-next 5/9] selftests/bpf: add bpf_spin_lock C test Alexei Starovoitov
2019-01-24 4:14 ` [PATCH v4 bpf-next 6/9] bpf: introduce BPF_F_LOCK flag Alexei Starovoitov
2019-01-24 4:14 ` [PATCH v4 bpf-next 7/9] tools/bpf: sync uapi/bpf.h Alexei Starovoitov
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to='CAG48ez1dA8_P9iKE4wqeSvQv-uEQ4HDqP_tp-Pa8Ze39qm3=XA@mail.gmail.com' \
--to=jannh@google.com \
--cc=alexei.starovoitov@gmail.com \
--cc=ast@kernel.org \
--cc=daniel@iogearbox.net \
--cc=davem@davemloft.net \
--cc=jakub.kicinski@netronome.com \
--cc=kernel-team@fb.com \
--cc=mingo@redhat.com \
--cc=netdev@vger.kernel.org \
--cc=paulmck@linux.ibm.com \
--cc=peterz@infradead.org \
--cc=will.deacon@arm.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).