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

["Zack Weinberg" <zack@owlfolio.org>]

On Fri, Mar 22, 2024, at 3:47 PM, Mathieu Desnoyers wrote:
> On 2024-03-22 14:05, Adhemerval Zanella Netto wrote:
>> On 22/03/24 12:30, Zack Weinberg wrote:

>>> I would describe that as a "CSPRNG with a known bug that makes it
>>> unsuitable for use under some conditions", but not as "not a CSPRNG".
...
>> I tend to agree, but the contention point was really 'that makes it
>> unsuitable for use under some conditions' was a deal breaker in face that
>> kernel provides an API with better guarantees.

How strong exactly are the guarantees that OpenBSD provides for its
arc4random?  I don't think we *need* to do any better than that,
although obviously we should if we can.

>>> On a related note, why is MADV_WIPEONFORK not adequate "feedback from the
>>> kernel"?
>> If I recall correctly, the problem was not only state wipe on fork (with
>> MADV_WIPEONFORK should take care), but rather when the state needs to be
>> reseed due various situations outside of the userland knowledge
...
> 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?
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?

---

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.

zw