From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-8.6 required=3.0 tests=DKIMWL_WL_MED,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI, SPF_PASS,URIBL_BLOCKED,USER_IN_DEF_DKIM_WL autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id C7B76C282C0 for ; Sat, 26 Jan 2019 00:44:11 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id 8F7C2218FF for ; Sat, 26 Jan 2019 00:44:11 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b="wFKpNuFQ" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726122AbfAZAoK (ORCPT ); Fri, 25 Jan 2019 19:44:10 -0500 Received: from mail-oi1-f196.google.com ([209.85.167.196]:36157 "EHLO mail-oi1-f196.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1725550AbfAZAoK (ORCPT ); Fri, 25 Jan 2019 19:44:10 -0500 Received: by mail-oi1-f196.google.com with SMTP id x23so9052331oix.3 for ; Fri, 25 Jan 2019 16:44:08 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=XDlZgBTwzsJvhNjbGpeJIwks2GoCxVfW2GvzQWlJT+0=; b=wFKpNuFQ0Cz8xBAjfJN+Vel1edteguzC1yHA56nXpG112SJgisFAQy9DOHpPoo+5Rj FUQ7ByAA6WxGBs5T1T4ae31guFuhuYBObYWlnP0hM887kDqK38YhDRwu6+hRcsUH6WC+ WfUIgwhovDtH9sGtRCCa8kKU545hsypOucC/CZGvC7jIW2yGS2npkjrx+y5K9MMZ6LpH uDgfXEOB5eNvmaNb+Lgb1UqQd9IISCgck9feR/tML48yz86ty/qfxXGSd6x3MavS55a7 qG8ZeriNAVCTgaoVzuhwM9o3QqcuofpND8C5JyTqy6Beflpvy2NjF8s+bE5xmyWaUc/Y OeEw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=XDlZgBTwzsJvhNjbGpeJIwks2GoCxVfW2GvzQWlJT+0=; b=Qk0rx/wFgrzZpLq8I/CsCS49SqaaNO3mPgM3gzuzgGEGx6ETc0d7udITGN+OD0sr1t cJRlKwbFojt0egHqHtCg8zUZrw+rlpg6bosqoCE+598O9WNB9DxtGppWbQ8/hpC0fLSp yrkpAuiQkp1cGiEq7/mTOUf/VxiJO0f6Zqq3ae7S+XqUBHlNxSAucu3wMfKslgh1p7cs N/4K4vspL3oj/oY2EzPOyg0CyfnJYo8HzJRCW6LdDeOgM9Sa6T8I/ZjsMfBNZFfA+H5S jRsZ4vmwWowiTsTVLEsv9p5ls5iui+npxuIFapABmT/w893LTEX3Yi2z9LUp3OxsUW8B iUYQ== X-Gm-Message-State: AJcUukdmM3wWWXyo2fakngM5Uys+w0YGwI3qGx8XDesdHqm2+h5CwWD+ J6hTFS8yefLS5MtOhbQUwvhoo7vk+sZF1NVSCiKw4g== X-Google-Smtp-Source: ALg8bN5soP8ZrzmG9HK+SlqSzpRbEp/t7jzTYEFrphcjkH5LlclmosgH1XiAHiAMxI+cwSjHzbQunOeQzlfNu6vA/ao= X-Received: by 2002:aca:c43:: with SMTP id i3mr248667oiy.157.1548463448146; Fri, 25 Jan 2019 16:44:08 -0800 (PST) MIME-Version: 1.0 References: <20190124041403.2100609-2-ast@kernel.org> <20190124180109.GA27771@hirez.programming.kicks-ass.net> <20190124185652.GB17767@hirez.programming.kicks-ass.net> <20190124234232.GY4240@linux.ibm.com> <20190125000515.jizijxz4n735gclx@ast-mbp.dhcp.thefacebook.com> <20190125012224.GZ4240@linux.ibm.com> <20190125041152.GA4240@linux.ibm.com> <20190125225112.GF4240@linux.ibm.com> <20190125234403.iisj5woztm4afwgh@ast-mbp.dhcp.thefacebook.com> In-Reply-To: <20190125234403.iisj5woztm4afwgh@ast-mbp.dhcp.thefacebook.com> From: Jann Horn Date: Sat, 26 Jan 2019 01:43:41 +0100 Message-ID: Subject: Re: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock To: Alexei Starovoitov Cc: "Paul E. McKenney" , Peter Zijlstra , Alexei Starovoitov , "David S. Miller" , Daniel Borkmann , jakub.kicinski@netronome.com, Network Development , kernel-team@fb.com, Ingo Molnar , Will Deacon Content-Type: text/plain; charset="UTF-8" Sender: netdev-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: netdev@vger.kernel.org On Sat, Jan 26, 2019 at 12:44 AM Alexei Starovoitov 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