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

[Yann Droneaud <ydroneaud@opteya.com>]

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.


> The arc4random_uniform is based on previous work by Florian Weimer.
>
> 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
> ---
>   NEWS                                          |   4 +-
>   include/stdlib.h                              |  13 +
>   posix/fork.c                                  |   2 +
>   stdlib/Makefile                               |   2 +
>   stdlib/Versions                               |   5 +
>   stdlib/arc4random.c                           | 245 ++++++++++++++++++
>   stdlib/arc4random_uniform.c                   | 152 +++++++++++
>   stdlib/chacha20.c                             | 163 ++++++++++++
>   stdlib/stdlib.h                               |  14 +
>   sysdeps/generic/not-cancel.h                  |   2 +
>   sysdeps/mach/hurd/i386/libc.abilist           |   3 +
>   sysdeps/mach/hurd/not-cancel.h                |   3 +
>   sysdeps/unix/sysv/linux/aarch64/libc.abilist  |   3 +
>   sysdeps/unix/sysv/linux/alpha/libc.abilist    |   3 +
>   sysdeps/unix/sysv/linux/arc/libc.abilist      |   3 +
>   sysdeps/unix/sysv/linux/arm/be/libc.abilist   |   3 +
>   sysdeps/unix/sysv/linux/arm/le/libc.abilist   |   3 +
>   sysdeps/unix/sysv/linux/csky/libc.abilist     |   3 +
>   sysdeps/unix/sysv/linux/hppa/libc.abilist     |   3 +
>   sysdeps/unix/sysv/linux/i386/libc.abilist     |   3 +
>   sysdeps/unix/sysv/linux/ia64/libc.abilist     |   3 +
>   .../sysv/linux/m68k/coldfire/libc.abilist     |   3 +
>   .../unix/sysv/linux/m68k/m680x0/libc.abilist  |   3 +
>   .../sysv/linux/microblaze/be/libc.abilist     |   3 +
>   .../sysv/linux/microblaze/le/libc.abilist     |   3 +
>   .../sysv/linux/mips/mips32/fpu/libc.abilist   |   3 +
>   .../sysv/linux/mips/mips32/nofpu/libc.abilist |   3 +
>   .../sysv/linux/mips/mips64/n32/libc.abilist   |   3 +
>   .../sysv/linux/mips/mips64/n64/libc.abilist   |   3 +
>   sysdeps/unix/sysv/linux/nios2/libc.abilist    |   3 +
>   sysdeps/unix/sysv/linux/not-cancel.h          |   7 +
>   sysdeps/unix/sysv/linux/or1k/libc.abilist     |   3 +
>   .../linux/powerpc/powerpc32/fpu/libc.abilist  |   3 +
>   .../powerpc/powerpc32/nofpu/libc.abilist      |   3 +
>   .../linux/powerpc/powerpc64/be/libc.abilist   |   3 +
>   .../linux/powerpc/powerpc64/le/libc.abilist   |   3 +
>   .../unix/sysv/linux/riscv/rv32/libc.abilist   |   3 +
>   .../unix/sysv/linux/riscv/rv64/libc.abilist   |   3 +
>   .../unix/sysv/linux/s390/s390-32/libc.abilist |   3 +
>   .../unix/sysv/linux/s390/s390-64/libc.abilist |   3 +
>   sysdeps/unix/sysv/linux/sh/be/libc.abilist    |   3 +
>   sysdeps/unix/sysv/linux/sh/le/libc.abilist    |   3 +
>   .../sysv/linux/sparc/sparc32/libc.abilist     |   3 +
>   .../sysv/linux/sparc/sparc64/libc.abilist     |   3 +
>   .../unix/sysv/linux/x86_64/64/libc.abilist    |   3 +
>   .../unix/sysv/linux/x86_64/x32/libc.abilist   |   3 +
>   46 files changed, 713 insertions(+), 1 deletion(-)
>   create mode 100644 stdlib/arc4random.c
>   create mode 100644 stdlib/arc4random_uniform.c
>   create mode 100644 stdlib/chacha20.c
>
> diff --git a/NEWS b/NEWS
> index 4b6d9de2b5..4d9d95b35b 100644
> --- a/NEWS
> +++ b/NEWS
> @@ -9,7 +9,9 @@ Version 2.36
>   
>   Major new features:
>   
> -  [Add new features here]
> +* The functions arc4random, arc4random_buf, arc4random_uniform have been
> +  added.  The functions use a cryptographic pseudo-random number generator
> +  based on ChaCha20 initilized with entropy from kernel.
>   
>   Deprecated and removed features, and other changes affecting compatibility:
>   
> diff --git a/include/stdlib.h b/include/stdlib.h
> index 1c6f70b082..055f9d2965 100644
> --- a/include/stdlib.h
> +++ b/include/stdlib.h
> @@ -144,6 +144,19 @@ libc_hidden_proto (__ptsname_r)
>   libc_hidden_proto (grantpt)
>   libc_hidden_proto (unlockpt)
>   
> +__typeof (arc4random) __arc4random;
> +libc_hidden_proto (__arc4random);
> +__typeof (arc4random_buf) __arc4random_buf;
> +libc_hidden_proto (__arc4random_buf);
> +__typeof (arc4random_uniform) __arc4random_uniform;
> +libc_hidden_proto (__arc4random_uniform);
> +extern void __arc4random_buf_internal (void *buffer, size_t len)
> +     attribute_hidden;
> +/* Called from the fork function to reinitialize the internal lock in thte
> +   child process.  This avoids deadlocks if fork is called in multi-threaded
> +   processes.  */
> +extern void __arc4random_fork_subprocess (void) attribute_hidden;
> +
>   extern double __strtod_internal (const char *__restrict __nptr,
>   				 char **__restrict __endptr, int __group)
>        __THROW __nonnull ((1)) __wur;
> diff --git a/posix/fork.c b/posix/fork.c
> index 6b50c091f9..87d8329b46 100644
> --- a/posix/fork.c
> +++ b/posix/fork.c
> @@ -96,6 +96,8 @@ __libc_fork (void)
>   				     &nss_database_data);
>   	}
>   
> +      call_function_static_weak (__arc4random_fork_subprocess);
> +
>         /* Reset the lock the dynamic loader uses to protect its data.  */
>         __rtld_lock_initialize (GL(dl_load_lock));
>   
> diff --git a/stdlib/Makefile b/stdlib/Makefile
> index 60fc59c12c..9f9cc1bd7f 100644
> --- a/stdlib/Makefile
> +++ b/stdlib/Makefile
> @@ -53,6 +53,8 @@ routines := \
>     a64l \
>     abort \
>     abs \
> +  arc4random \
> +  arc4random_uniform \
>     at_quick_exit \
>     atof \
>     atoi \
> diff --git a/stdlib/Versions b/stdlib/Versions
> index 5e9099a153..d09a308fb5 100644
> --- a/stdlib/Versions
> +++ b/stdlib/Versions
> @@ -136,6 +136,11 @@ libc {
>       strtof32; strtof64; strtof32x;
>       strtof32_l; strtof64_l; strtof32x_l;
>     }
> +  GLIBC_2.36 {
> +    arc4random;
> +    arc4random_buf;
> +    arc4random_uniform;
> +  }
>     GLIBC_PRIVATE {
>       # functions which have an additional interface since they are
>       # are cancelable.
> diff --git a/stdlib/arc4random.c b/stdlib/arc4random.c
> new file mode 100644
> index 0000000000..cddb0e405a
> --- /dev/null
> +++ b/stdlib/arc4random.c
> @@ -0,0 +1,245 @@
> +/* Pseudo Random Number Generator based on ChaCha20.
> +   Copyright (C) 2020 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 <errno.h>
> +#include <libc-lock.h>
> +#include <not-cancel.h>
> +#include <stdio.h>
> +#include <stdlib.h>
> +#include <sys/mman.h>
> +#include <sys/param.h>
> +#include <sys/random.h>
> +
> +/* 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


> +   and abort the process if none could be obtained.
> +
> +   The state 'buf' improves the usage of the cipher call, allowing to call
> +   optimized implementations (if the archictecture provides it) and optimize
> +   arc4random calls (since only multiple call it will encrypt the next block).
> + */
> +
> +/* Maximum number bytes until reseed (16 MB).  */
> +#define CHACHE_RESEED_SIZE	(16 * 1024 * 1024)
> +/* Internal buffer size in bytes (1KB).  */
> +#define CHACHA20_BUFSIZE        (8 * CHACHA20_BLOCK_SIZE)
> +
> +#include <chacha20.c>
> +
> +static struct arc4random_state
> +{
> +  uint32_t ctx[CHACHA20_STATE_LEN];
> +  size_t have;
> +  size_t count;
> +  uint8_t buf[CHACHA20_BUFSIZE];
> +} *state;
> +
> +/* Indicate that MADV_WIPEONFORK is supported by the kernel and thus
> +   it does not require to clear the internal state.  */
> +static bool __arc4random_wipeonfork = false;
> +
> +__libc_lock_define_initialized (, __arc4random_lock);
> +
> +/* Called from the fork function to reset the state if MADV_WIPEONFORK is
> +   not supported and to reinit the internal lock.  */
> +void
> +__arc4random_fork_subprocess (void)
> +{
> +  if (__arc4random_wipeonfork && state != NULL)
> +    memset (state, 0, sizeof (struct arc4random_state));
> +
> +  __libc_lock_init (__arc4random_lock);
> +}
> +
> +static void
> +arc4random_allocate_failure (void)
> +{
> +  __libc_fatal ("Fatal glibc error: Cannot allocate memory for arc4random\n");
> +}
> +
> +static void
> +arc4random_getrandom_failure (void)
> +{
> +  __libc_fatal ("Fatal glibc error: Cannot get entropy for arc4random\n");
> +}
> +
> +/* Fork detection is done by checking if MADV_WIPEONFORK supported.  If not
> +   the fork callback will reset the state on the fork call.  It does not
> +   handle direct clone calls, nor vfork or _Fork (arc4random is not
> +   async-signal-safe due the internal lock usage).  */
> +static void
> +arc4random_init (uint8_t *buf, size_t len)
> +{
> +  state = __mmap (NULL, sizeof (struct arc4random_state),
> +		  PROT_READ | PROT_WRITE, MAP_ANONYMOUS | MAP_PRIVATE, -1, 0);
> +  if (state == MAP_FAILED)
> +    arc4random_allocate_failure ();
> +
> +#ifdef MADV_WIPEONFORK
> +  int r = __madvise (state, sizeof (struct arc4random_state), MADV_WIPEONFORK);
> +  if (r == 0)
> +    __arc4random_wipeonfork = true;
> +  else if (errno != EINVAL)
> +    arc4random_allocate_failure ();
> +#endif
> +
> +  chacha20_init (state->ctx, buf, buf + CHACHA20_KEY_SIZE);
> +}
> +
> +#define min(x,y) (((x) > (y)) ? (y) : (x))
> +
> +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


> +  chacha20_crypt (state->ctx, state->buf, state->buf, sizeof state->buf);
> +
> +  /* Mix some extra entropy if provided.  */
> +  if (rnd != NULL)
> +    {
> +      size_t m = min (rndlen, CHACHA20_KEY_SIZE + CHACHA20_IV_SIZE);
> +      for (size_t i = 0; i < m; i++)
> +	state->buf[i] ^= rnd[i];
> +    }
> +
> +  /* Immediately reinit for backtracking resistance.  */
> +  chacha20_init (state->ctx, state->buf, state->buf + CHACHA20_KEY_SIZE);
> +  memset (state->buf, 0, CHACHA20_KEY_SIZE + CHACHA20_IV_SIZE);
> +  state->have = sizeof (state->buf) - (CHACHA20_KEY_SIZE + CHACHA20_IV_SIZE);
> +}
> +
> +static void
> +arc4random_getentropy (uint8_t *rnd, size_t len)
> +{
> +  if (__getrandomn_nocancel (rnd, len, GRND_NONBLOCK) == len)
> +    return;
> +
> +  int fd = __open64_nocancel ("/dev/urandom", O_RDONLY);
> +  if (fd != -1)
> +    {
> +      unsigned char *p = rnd;
> +      unsigned char *end = p + len;
> +      do
> +	{
> +	  ssize_t ret = TEMP_FAILURE_RETRY (__read_nocancel (fd, p, end - p));
> +	  if (ret <= 0)
> +	    arc4random_getrandom_failure ();
> +	  p += ret;
> +	}
> +      while (p < end);
> +
> +      if (__close_nocancel (fd) != 0)
> +	return;
> +    }
> +  arc4random_getrandom_failure ();
> +}
> +
> +/* Either allocates the state buffer or reinit it by reseeding the cipher
> +   state with kernel entropy.  */
> +static void
> +arc4random_stir (void)
> +{
> +  uint8_t rnd[CHACHA20_KEY_SIZE + CHACHA20_IV_SIZE];
> +  arc4random_getentropy (rnd, sizeof rnd);
> +
> +  if (state == NULL)
> +    arc4random_init (rnd, sizeof rnd);
> +  else
> +    arc4random_rekey (rnd, sizeof rnd);
> +
> +  explicit_bzero (rnd, sizeof rnd);
> +
> +  state->have = 0;
> +  memset (state->buf, 0, sizeof state->buf);
> +  state->count = CHACHE_RESEED_SIZE;
> +}
> +
> +static void
> +arc4random_check_stir (size_t len)
> +{
> +  if (state == NULL || state->count < len)
> +    arc4random_stir ();
> +  if (state->count <= len)
> +    state->count = 0;
> +  else
> +    state->count -= len;
> +}
> +
> +void
> +__arc4random_buf_internal (void *buffer, size_t len)
> +{
> +  arc4random_check_stir (len);
> +
> +  while (len > 0)
> +    {
> +      if (state->have > 0)
> +	{
> +	  size_t m = min (len, state->have);
> +	  uint8_t *ks = state->buf + sizeof (state->buf) - state->have;
> +	  memcpy (buffer, ks, m);
> +	  memset (ks, 0, m);
> +	  buffer += m;
> +	  len -= m;
> +	  state->have -= m;
> +	}
> +      if (state->have == 0)
> +	arc4random_rekey (NULL, 0);
> +    }
> +}
> +
> +void
> +__arc4random_buf (void *buffer, size_t len)
> +{
> +  __libc_lock_lock (__arc4random_lock);
> +  __arc4random_buf_internal (buffer, len);
> +  __libc_lock_unlock (__arc4random_lock);
> +}
> +libc_hidden_def (__arc4random_buf)
> +weak_alias (__arc4random_buf, arc4random_buf)
> +
> +
> +static uint32_t
> +__arc4random_internal (void)
> +{
> +  uint32_t r;
> +
> +  arc4random_check_stir (sizeof (uint32_t));
> +  if (state->have < sizeof (uint32_t))
> +    arc4random_rekey (NULL, 0);
> +  uint8_t *ks = state->buf + sizeof (state->buf) - state->have;
> +  memcpy (&r, ks, sizeof (uint32_t));
> +  memset (ks, 0, sizeof (uint32_t));
> +  state->have -= sizeof (uint32_t);
> +
> +  return r;
> +}
> +
> +uint32_t
> +__arc4random (void)
> +{
> +  uint32_t r;
> +  __libc_lock_lock (__arc4random_lock);
> +  r = __arc4random_internal ();
> +  __libc_lock_unlock (__arc4random_lock);
> +  return r;
> +}
> +libc_hidden_def (__arc4random)
> +weak_alias (__arc4random, arc4random)
> diff --git a/stdlib/arc4random_uniform.c b/stdlib/arc4random_uniform.c
> new file mode 100644
> index 0000000000..96ffe62df1
> --- /dev/null
> +++ b/stdlib/arc4random_uniform.c
> @@ -0,0 +1,152 @@
> +/* Random pseudo generator numbers between 0 and 2**-31 (inclusive)
> +   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.  */
> +  unsigned 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 that 33 bits.  This ensures the code 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.  */
> +    }

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.


> +}
> +
> +__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)


-- 

Yann Droneaud

OPTEYA