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

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

On 25/04/2022 09:15, Adhemerval Zanella wrote:
> 
> 
> On 22/04/2022 10:54, Yann Droneaud wrote:
>> Le 19/04/2022 à 23:28, Adhemerval Zanella via Libc-alpha a écrit :
>>> 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 amortize arc4random calls (where both
>>> function call and locks cost are the dominating factor).
>>>
>>> The ChaCha20 implementation is based on the RFC8439 [1], with last
>>> step that XOR with the input omited.  Since the input stream will either
>>> zero bytes (initial state) or the PRNG output itself this step does not
>>> add any extra entropy.
>>
>>
>> This can also state the implementation is following OpenBSD arc4random current implementation.
>>
>>
> 
> Agree, it is worth to add it.
> 
>>> +
>>> +/* Besides the cipher state 'ctx', it keeps two counters: 'have' is the
>>> +   current valid bytes not yet consumed in 'buf', while 'count' is the maximum
>>> +   number of bytes until a reseed.
>>> +
>>> +   Both the initial seed an reseed tries to obtain entropy from the kernel
>>
>> an ->  and
> 
> Ack.
> 
>>> +
>>> +static void
>>> +arc4random_rekey (uint8_t *rnd, size_t rndlen)
>>> +{
>>> +  memset (state->buf, 0, sizeof state->buf);
>>
>> There's no need to clear buf as call to chacha20_crypt() will overwrite it (since it doesn't XOR with it anymore).
>>
>> See https://github.com/openbsd/src/blob/master/lib/libc/crypt/arc4random.c#L121
> 
> Ack, I have removed it.
> 
> 
>>> +
>>> +      /* Extract a bit and append it to c.  c remains less than v and
>>> +         thus 2**33.  */
>>> +      c = (c << 1) | (bits & 1);
>>> +      bits >>= 1;
>>> +      --bits_length;
>>> +
>>> +      /* At this point, c is uniformly distributed on [0, v) again,
>>> +         and v < 2n < 2**33.  */
>>> +    }
>>
>> I'm not familiar with this method.
>>
>> It's not one reviewed at https://www.pcg-random.org/posts/bounded-rands.html
>>
>> In this patch I used what's called by PCG author,the "Bitmask with Rejection (Unbiased) — Apple's Method"
>>
>> https://github.com/Parrot-Developers/libfutils/commit/9dc7243ae2f2059b4590a702be2ca9c03578067f
>>
>> I like it because it doesn't uses modulo at all :)
>>
>> But the OpenBSD's arc4random_uniform() is even more simple in term of C code.
>>
> 
> You can find the reference paper on arxiv [1].  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.
> 
> From the article:
> 
>   But unexpectedly, it turns out that the extra buffering inherent in consuming
>   randomness random-bit-by-random-bit, although time consuming, is more than
>   compensated by the increased efficiency in using random bits compared with most
>   common methods.
> 
> It is specially true if you consider that both chacha20 block generation and
> getting kernel entropy (through either getrandom or /dev/urandom) are way
> more time consuming than bit twiddling. 
> 
> [1] https://arxiv.org/pdf/1304.1916.pdf
> 

And you can see that this method does not use modulo as well.  It does use 
arc4random_buf internally, what might add some overhead. One possible
optimization could to add a internal function to consume only one byte,
but I am not sure if this really pays off.