Re: [PATCH 2/2] Add single-threaded fast path to rand()

[Mathieu Desnoyers <mathieu.desnoyers@efficios.com>]

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