From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtpout.efficios.com (smtpout.efficios.com [167.114.26.122]) by sourceware.org (Postfix) with ESMTPS id B8BA53858D28 for ; Sat, 23 Mar 2024 15:22:48 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org B8BA53858D28 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=efficios.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=efficios.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org B8BA53858D28 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=167.114.26.122 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1711207371; cv=none; b=ToXz+R1PTTQkV1GhPVPTZZmMSqTc65CUUfFBPP22YG6Q7wX8CIRvSGRoy5W5IBCaMaB93VzJ+JX4DBCIIcrabbVaps9tbWsYqMx8upqCM8/vSOD37G9PlGiNpGamewhfnOJwHMudCm8y7sJMOVlCvMMdNNCLkg4MnR+ui0Ol1hE= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1711207371; c=relaxed/simple; bh=kLPmzsa5x/MtcTofHcHsKliQ9O9+ecpOFEl4XEGyE+8=; h=DKIM-Signature:Message-ID:Date:MIME-Version:Subject:To:From; b=OqtdEOQv/BX/XLOQBbsP3jnxvXEf9kWfzwu0otPgya+JGBmattPzXbOKADhlwTY/IkVSQNQOXsBD0P37iwQoSmNc/4NetuFMgT/FTyKrchCeBXoHK+GmUsXlS2W54wr1lXAC+035WKvwKbScQgJaxlPhqLmiwSmyPuyOkFU+Oig= ARC-Authentication-Results: i=1; server2.sourceware.org DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=efficios.com; s=smtpout1; t=1711207367; bh=kLPmzsa5x/MtcTofHcHsKliQ9O9+ecpOFEl4XEGyE+8=; h=Date:Subject:To:Cc:References:From:In-Reply-To:From; b=MSv3IcE3vZbriqtIKk+vOL/DPhyPvhBJxOkacyNQMKVWAOlB0InoGSNoEC+Kx4t4K NMLp4qmMqL6JkRMOqlX5uNQFQIbouXXEZ/TERKBd41ogzLuMxEm3ffmtA0KY0OLCg7 4ZneIKBlxwds/qcvlp7PLSEE2qF6O4YhoW1WceRScv3lutaF2riyt/rITFfu11q5nb euJhO+hWCaGUeD33mUfxhkixdRb4C2VU2sVqFG77H5uMqyOcXqZ0QvjM+qMlZOf+2y mytJyqDpcvNiKxCsd9stVSc8c4m6/NSmdhoC2CPMssg8BIJwOl2NWIQq0FVf+Fwc4N w3lGQuX3a70Jg== Received: from [IPV6:2606:6d00:100:4000:cacb:9855:de1f:ded2] (unknown [IPv6:2606:6d00:100:4000:cacb:9855:de1f:ded2]) by smtpout.efficios.com (Postfix) with ESMTPSA id 4V22xy71kxzmZZ; Sat, 23 Mar 2024 11:22:46 -0400 (EDT) Message-ID: Date: Sat, 23 Mar 2024 11:23:09 -0400 MIME-Version: 1.0 User-Agent: Mozilla Thunderbird Subject: Re: [PATCH 2/2] Add single-threaded fast path to rand() Content-Language: en-US To: Zack Weinberg , Adhemerval Zanella , =?UTF-8?Q?Cristian_Rodr=C3=ADguez?= , Florian Weimer Cc: Wilco Dijkstra , GNU libc development , "Jason A. Donenfeld" References: <89b53f94-075f-4a34-99df-778271965de9@linaro.org> <878r2c11au.fsf@oldenburg.str.redhat.com> <40f9403d-5edc-47ae-8560-6549753ebf39@linaro.org> <17ac36a5-d5c0-4f71-8cf3-5eaf014194d6@linaro.org> <667f5ebb-13e5-4110-a002-3b2b0dfc2bdb@app.fastmail.com> <50b42519-4557-4e8c-8a58-0077168aa25d@linaro.org> <6a938fb2-30a5-4589-9b58-10828823df6f@efficios.com> <1ebd177e-8ad0-4bf1-84ea-40586bc3b00c@app.fastmail.com> From: Mathieu Desnoyers In-Reply-To: <1ebd177e-8ad0-4bf1-84ea-40586bc3b00c@app.fastmail.com> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Status: No, score=-4.7 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,SPF_HELO_NONE,SPF_PASS,TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org List-Id: On 2024-03-23 10:01, Zack Weinberg wrote: [...] > ... >> If the goal is to let userspace know that it needs to reseed due to >> various kernel events happening, one way I see we could extend rseq >> to support this would be to add a 64-bit "seed generation counter" >> in the struct rseq per-thread area which would be incremented by the >> kernel when the seed needs to be updated in userspace. > > I don't know hardly anything about rseq. I think that sounds workable > from libc's side of the fence; the remaining questions I see are > > 1) Will the kernel take your patch? I can start by creating a proof-of-concept patch. If there are use-cases justifying its integration, I don't see why the other rseq co-maintainers would object. As maintainer of the Linux kernel rseq system call, I would be OK with it as long as it fits in the RSEQ design constraints: each new rseq field should support many users per process (executable and libraries), and we should try to minimize coupling between kernel and user-space. There are a few things I would need to know to create a prototype: - Do we need a 64-bit counter for this, or is 32-bit enough ? - What kernel events are we interested in ? I suspect that some are global (e.g. sleep, hibernate) and some are per-process (e.g. fork/clone). Are there other events I am missing here ? - At which point would the generation counter be validated ? Would that be before generating a PRN or after ? If it's before, then what happens to the validity of this PNG if the kernel event happens exactly while the PRN is being generated ? > 2) Is it OK for us to provide an arc4random implementation that uses > this generation counter when available, but, when it's not available, > doesn't reseed on these events that are invisible to user space? That's up to you really. Or you could make this configurable: a user could request a PRNG with security guarantees, or not. rseq provides interfaces to query which fields are supported, so depending on the user needs, your library could either return an error or allow generating a less-secure random number. > > --- > > Independently, I propose that the existing non-cryptographic PRNGs > (rand(), random(), etc.) should all be changed to run off a thread-local > scrambled-linear generator > (https://vigna.di.unimi.it/ftp/papers/ScrambledLinear.pdf). These have > better statistical properties than anything we currently offer, and a > state space that's small enough (256 bits) that it's reasonable for us > to have one per thread, obviating locking concerns. I've been wondering if doing so would break the PRNG guarantees from a whole-program (multithreaded) perspective: let's suppose we have many threads which are synchronized in such a way that the order of execution of statements across threads is guaranteed to be the same across runs. Should they expect a global PRNG with the same initial seed to have the same behavior ? How would the per-thread seeds allow the global PRNG walk to be reproducible across runs ? Thanks, Mathieu -- Mathieu Desnoyers EfficiOS Inc. https://www.efficios.com