On Sat, Jan 26, 2019 at 1:43 AM Jann Horn <ja...@google.com> wrote: > On Sat, Jan 26, 2019 at 12:44 AM Alexei Starovoitov > <alexei.starovoi...@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
Oh, and actually, you can probably also detect a collision in a simpler way: - insert A - insert B - query BPF_MAP_GET_NEXT_KEY - delete A - delete B - insert B - insert A - query BPF_MAP_GET_NEXT_KEY - delete A - delete B If the two BPF_MAP_GET_NEXT_KEY queries return the same result, A and B are in different buckets; if they return different results, A and B are in the same bucket, I think?
