Re: [9front] [PATCH] libc: replace lrand's algorithm

[qwx@sciops.net]

On Tue Apr  2 16:38:36 +0200 2024, eolien55@disroot.org wrote:
> qwx@sciops.net wrote:
> > I like the idea of simplifying the tree and deleting some code,
> > but keep in mind that the xoroshiro128+ variant is what is
> > exposed by /dev/random via truerand(2).
> 
> That's not quite it. What is exposed by /dev/random is actually
> a Chacha-based CSPRNG. truerand(2) is a cryptographic PRNG.

Ah, my bad, sorry.


> However, the kernel itself (via tcp, ip, sdp, esp...) uses
> a non-cryptographic PRNG (in nrand and rand calls, in the
> kernel). The kernel's PRNG was changed to xoroshiro128+
> in 10275ad6dd2. I believe it would make sense to either
> change libc's lrand to xoroshiro128+ too, or to change
> them both at the same time.
[...]
> > Most people are
> > uninsterested in a change here because of the dichotomy between
> > rand and truerand, the negligeable performance impact, etc.,
> > and beyond this, it gets into "this is like, my opinion man"
> > territory.  I wouldn't mind replacing libc's lrand with a PCG
> > variant also exposing a 64bit version, which we don't have, if
> > it indeed also improves the statistical properties of the prng.
> > But that's like, my opinion man.
> 
> Well, this is feasible. Both PCG and xoroshiro require 128 bits
> of state for a 64-bit output. kernel's implementation simulates
> 128-bits operations using 2 64-bit integers. It should be feasible
> to implement a PC64 with the same approach, or to implement
> xoroshiro128+ (or another variant, for statistical quality of the
> lower bits).
> 
> I understand the change here is highly subjective, and has
> negligible performance impact (except for seeding/re-seeding).
> I still believe we could, and should, implement a better PRNG
> for libc. Kernel's PRNG has changed; why not libc's?
> 
> I found (rand()<<16) + rand() in kernel's devsdp, which is
> strange considering lrand already has 32 bits of output. I
> think this should be considered a bug.

I think at this point it would be better to look at a patch, with the
changes mentioned after the first post, and a sweep through the other
implementations.  There are some odd occurrences as you found; libc's
frand() is also somewhat suspect but will likely need to change if
lrand() does.  We need a 16bit, 32bit, floating point, and possibly
64bit variant; this will clean up some code and remove some
redundancies which is always nice.  Perhaps take the extreme route and
do *all* of the changes you'd like to see, so we could more easily
discuss each case.  We then need to check if there's a performance
impact on non-amd64 arches.  For xoroshiro128+ vs.  pcg I'd be
interested to know if there's any significant difference between the
two in statistical properties and performance; if we make a change,
it'd be nice to pick the best alternative and make it once and for
all.  Code size and simplicity also counts.  Is there any other
variant that should be assessed?


> > I agree, though again, I don't know what the impact of such
> > a change would be.
> 
> Arguably, very negligible. Both use random tests, and quality is
> somewhat important in these context. A little more than in, say,
> fortune(1), but way less than in tls(3). However, venti's randtest
> uses a hard-coded PRNG instead of libc's.
> 
> Cheers,
> Elie Le Vaillant

In that case, I wouldn't touch venti either.  There are at least two
projects for replacing venti with a new implementation; imo any such
changes should be made there.

Cheers,
qwx