[PATCH v6 01/10] stdlib: Add arc4random, arc4random_buf, and arc4random_uniform (BZ #4417)

[Adhemerval Zanella]

On 02/06/2022 06:44, Yann Droneaud wrote:
> Hi,
> 
> Found some time to review arc4random_uniform() implementation this time.
> 
> 
> Le 18/05/2022 à 21:14, 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 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
>> ---
>>
>> diff --git a/stdlib/arc4random_uniform.c b/stdlib/arc4random_uniform.c
>> new file mode 100644
>> index 0000000000..722e92b3a7
>> --- /dev/null
>> +++ b/stdlib/arc4random_uniform.c
>> @@ -0,0 +1,152 @@
>> +/* Random pseudo generator numbers between 0 and 2**-31 (inclusive)
> upper bound is incorrect

Right, I changed to:

/* Random pseudo generator number which returns a single 32 bit value
   uniformly distributed but with an upper_bound.


>> +   uniformly distributed but with an upper_bound.
>> +   Copyright (C) 2022 Free Software Foundation, Inc.
>> +   This file is part of the GNU C Library.
>> +
>> +   The GNU C Library is free software; you can redistribute it and/or
>> +   modify it under the terms of the GNU Lesser General Public
>> +   License as published by the Free Software Foundation; either
>> +   version 2.1 of the License, or (at your option) any later version.
>> +
>> +   The GNU C Library is distributed in the hope that it will be useful,
>> +   but WITHOUT ANY WARRANTY; without even the implied warranty of
>> +   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
>> +   Lesser General Public License for more details.
>> +
>> +   You should have received a copy of the GNU Lesser General Public
>> +   License along with the GNU C Library; if not, see
>> +   <http://www.gnu.org/licenses/>.  */
>> +
>> +#include <endian.h>
>> +#include <libc-lock.h>
>> +#include <stdlib.h>
>> +#include <sys/param.h>
>> +
>> +/* Return the number of bytes which cover values up to the limit.  */
>> +__attribute__ ((const))
>> +static uint32_t
>> +byte_count (uint32_t n)
>> +{
>> +  if (n < (1U << 8))
>> +    return 1;
>> +  else if (n < (1U << 16))
>> +    return 2;
>> +  else if (n < (1U << 24))
>> +    return 3;
>> +  else
>> +    return 4;
>> +}
>> +
>> +/* Fill the lower bits of the result with randomness, according to the
>> +   number of bytes requested.  */
>> +static void
>> +random_bytes (uint32_t *result, uint32_t byte_count)
>> +{
>> +  *result = 0;
>> +  unsigned char *ptr = (unsigned char *) result;
>> +  if (__BYTE_ORDER == __BIG_ENDIAN)
>> +    ptr += 4 - byte_count;
>> +  __arc4random_buf_internal (ptr, byte_count);
>> +}
>> +
>> +static uint32_t
>> +compute_uniform (uint32_t n)
>> +{
>> +  if (n <= 1)
>> +    /* There is no valid return value for a zero limit, and 0 is the
>> +       only possible result for limit 1.  */
>> +    return 0;
>> +
>> +  /* The bits variable serves as a source for bits.  Prefetch the
>> +     minimum number of bytes needed.  */
>> +  uint32_t count = byte_count (n);
>> +  uint32_t bits_length = count * CHAR_BIT;
>> +  uint32_t bits;
>> +  random_bytes (&bits, count);
>> +
>> +  /* Powers of two are easy.  */
>> +  if (powerof2 (n))
>> +    return bits & (n - 1);
>> +
>> +  /* The general case.  This algorithm follows Jérémie Lumbroso,
>> +     Optimal Discrete Uniform Generation from Coin Flips, and
>> +     Applications (2013), who credits Donald E. Knuth and Andrew
>> +     C. Yao, The complexity of nonuniform random number generation
>> +     (1976), for solving the general case.
>> +
>> +     The implementation below unrolls the initialization stage of the
>> +     loop, where v is less than n.  */
>> +
>> +  /* Use 64-bit variables even though the intermediate results are
>> +     never larger than 33 bits.  This ensures the code is easier to
>> +     compile on 64-bit architectures.  */
>> +  uint64_t v;
>> +  uint64_t c;
>> +
>> +  /* Initialize v and c.  v is the smallest power of 2 which is larger
>> +     than n.*/
>> +  {
>> +    uint32_t log2p1 = 32 - __builtin_clz (n);
>> +    v = 1ULL << log2p1;
>> +    c = bits & (v - 1);
>> +    bits >>= log2p1;
>> +    bits_length -= log2p1;
>> +  }
>> +
>> +  /* At the start of the loop, c is uniformly distributed within the
>> +     half-open interval [0, v), and v < 2n < 2**33.  */
>> +  while (true)
>> +    {
>> +      if (v >= n)
>> +        {
>> +          /* If the candidate is less than n, accept it.  */
>> +          if (c < n)
>> +            /* c is uniformly distributed on [0, n).  */
>> +            return c;
>> +          else
>> +            {
>> +              /* c is uniformly distributed on [n, v).  */
>> +              v -= n;
>> +              c -= n;
>> +              /* The distribution was shifted, so c is uniformly
>> +                 distributed on [0, v) again.  */
>> +            }
>> +        }
>> +      /* v < n here.  */
>> +
>> +      /* Replenish the bit source if necessary.  */
>> +      if (bits_length == 0)
>> +        {
>> +          /* Overwrite the least significant byte.  */
>> +      random_bytes (&bits, 1);
>> +      bits_length = CHAR_BIT;
>> +        }
>> +
>> +      /* Double the range.  No overflow because v < n < 2**32.  */
>> +      v *= 2;
>> +      /* v < 2n here.  */
>> +
>> +      /* 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.  */
>> +    }
>> +}
>> +
>> +__libc_lock_define (extern , __arc4random_lock attribute_hidden)
>> +
>> +uint32_t
>> +__arc4random_uniform (uint32_t upper_bound)
>> +{
>> +  uint32_t r;
>> +  __libc_lock_lock (__arc4random_lock);
>> +  r = compute_uniform (upper_bound);
>> +  __libc_lock_unlock (__arc4random_lock);
>> +  return r;
>> +}
>> +libc_hidden_def (__arc4random_uniform)
>> +weak_alias (__arc4random_uniform, arc4random_uniform)
> 
> Seems fine from a computation point of view.
> 
> So for what it worth:
> 
> LGTM
> 
> Reviewed-by: Yann Droneaud <ydroneaud@opteya.com>

Thanks.

> 
> 
> Regards.
>