Re: [PATCH v4 1/9] stdlib: Add arc4random, arc4random_buf, and arc4random_uniform (BZ #4417)

[Adhemerval Zanella <adhemerval.zanella@linaro.org>]

On 25/04/2022 10:01, Adhemerval Zanella wrote:
> The implementation is based on scalar Chacha20, with global cache and
> locking.  It uses getrandom or /dev/urandom as fallback to get the
> initial entropy, and reseeds the internal state on every 16MB of
> consumed buffer.
> 
> It maintains an internal buffer which consumes at maximum one page on
> most systems (assuming minimum of 4k pages).  The internal buf optimizes
> the cipher encrypt calls, by amortizing arc4random calls (where both
> function call and lock cost are the dominating factor).
> 
> The ChaCha20 implementation is based on RFC8439 [1], omitting the final
> XOR of the keystream with the plaintext because the plaintext is a
> stream of zeros.  This strategy is similar to what OpenBSD arc4random
> does.
> 
> The arc4random_uniform is based on previous work by Florian Weimer,
> where the algorithm is based on Jérémie Lumbroso paper Optimal Discrete
> Uniform Generation from Coin Flips, and Applications (2013) [2], who
> credits Donald E. Knuth and Andrew C. Yao, The complexity of nonuniform
> random number generation (1976), for solving the general case.
> 
> The main advantage of this method is the that the unit of randomness is not
> the uniform random variable (uint32_t), but a random bit.  It optimizes the
> internal buffer sampling by initially consuming a 32-bit random variable
> and then sampling byte per byte.  Depending of the upper bound requested,
> it might lead to better CPU utilization.
> 
> Checked on x86_64-linux-gnu, aarch64-linux, and powerpc64le-linux-gnu.
> 
> Co-authored-by: Florian Weimer <fweimer@redhat.com>
> 
> [1] https://datatracker.ietf.org/doc/html/rfc8439
> [2] https://arxiv.org/pdf/1304.1916.pdf

And I forgot to address H.J review [1] for this one. I fixed them locally.

[1] https://sourceware.org/pipermail/libc-alpha/2022-April/137973.html