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
