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

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

On 12/07/22 05:57, Florian Weimer wrote:
> * Adhemerval Zanella:
> 
>> diff --git a/NEWS b/NEWS
>> index b0a3d7e512..f9dc316ead 100644
>> --- a/NEWS
>> +++ b/NEWS
>> @@ -46,6 +46,10 @@ Major new features:
>>     to more flexibly configure and operate on filesystem mounts.  The new
>>     mount APIs are specifically designed to work with namespaces.
>>   
>> +* The functions arc4random, arc4random_buf, and arc4random_uniform have been
>> +  added.  The functions use a cryptographic pseudo-random number generator
>> +  based on ChaCha20 initilized with entropy from the kernel.
> 
> This implies that the generator is cryptographically strong.  Maybe it
> should not mention ChaCha20 and “cryptographic”.

Ack, I changed to:

   * The functions arc4random, arc4random_buf, and arc4random_uniform 
have been
   added.  The functions use a pseudo-random number generator along with
   entropy from the kernel.

> 
>> diff --git a/include/stdlib.h b/include/stdlib.h
>> index 1c6f70b082..c5f5628f22 100644
>> --- a/include/stdlib.h
>> +++ b/include/stdlib.h
> 
>> +/* Called from the fork function to reinitialize the internal lock in the
>> +   child process.  This avoids deadlocks if fork is called in multi-threaded
>> +   processes.  */
>> +extern void __arc4random_fork_subprocess (void) attribute_hidden;
> 
> Looks like the comment is outdated.  There isn't a lock anymore.

Indeed, I changed to:

/* Called from the fork function to reinitialize the internal cipher state
   in child process.  */

> 
>> diff --git a/nptl/allocatestack.c b/nptl/allocatestack.c
>> index 01a282f3f6..ada65d40c2 100644
>> --- a/nptl/allocatestack.c
>> +++ b/nptl/allocatestack.c
> 
>> @@ -559,6 +560,8 @@ allocate_stack (const struct pthread_attr *attr, struct pthread **pdp,
>>   #endif
>>     pd->robust_head.list = &pd->robust_head;
>>   
>> +  __glibc_tls_internal_init (&pd->tls_state);
> 
> I think this is a bit confusing because it's not aligned with the main
> thread.  memset would probably be clearer because it mirrors setup for
> the main thread (zeroed implicitly).

Alright, I have added it on previous version because it required non
zero initialization.  I will change memset.

> 
>> diff --git a/stdlib/arc4random.c b/stdlib/arc4random.c
>> new file mode 100644
>> index 0000000000..92d1da92cc
>> --- /dev/null
>> +++ b/stdlib/arc4random.c
>> @@ -0,0 +1,207 @@
>> +/* Pseudo Random Number Generator based on ChaCha20.
>> +   Copyright (C) 2020 Free Software Foundation, Inc.
> 
> Copyright year 2022.  Please check the other files, too.

Ack.

> 
>> +/* arc4random 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 and reseed try to obtain entropy from the kernel
>> +   and abort the process if none could be obtained.
>> +
>> +   The state 'buf' improves the usage of the cipher calls, allowing to call
>> +   optimized implementations (if the architecture provides it) and optimize
>> +   arc4random calls (since only multiple calls it will encrypt the next
>> +   block).  */
> 
> I don't understand the “since only multiple calls it will encrypt the
> next block” part.

I changed to 'and minimize function call overhead'.  Using the generic
implementation, a 8 times the chacha20 blocks buffer shows about 2x more
throughput um aarch64.

A buffer with 4x the chacha20 block size shows slight less performance,
so one option might to make the buffer sizes arch-specific (since AVX2,
and potentially AVX512 requires large block size for the arch-specific
implementations).

> 
>> +/* Called from the fork function to reset the state.  */
>> +void
>> +__arc4random_fork_subprocess (void)
>> +{
>> +  struct arc4random_state_t *state = __glibc_tls_internal()->rand_state;
>> +  if (state != NULL)
>> +    {
>> +      explicit_bzero (state, sizeof (struct arc4random_state_t));
> 
> sizeof (*state)?

Ack.

> 
>> +      /* Force key init.  */
>> +      state->count = -1;
>> +    }
>> +}
>> +
>> +/* Return the current thread random state or try to create one if there is
>> +   none available.  In the case malloc can not allocate a state, arc4random
>> +   will try to get entropy with arc4random_getentropy.  */
>> +static struct arc4random_state_t *
>> +arc4random_get_state (void)
>> +{
>> +  struct arc4random_state_t *state = __glibc_tls_internal()->rand_state;
> 
> Missing space before ().

Ack.

> 
>> +  if (state == NULL)
>> +    {
>> +      state = malloc (sizeof (struct arc4random_state_t));
>> +      if (state != NULL)
>> +	{
>> +	  /* Force key initialization on first call.  */
>> +	  state->count = -1;
>> +	  __glibc_tls_internal()->rand_state = state;
> 
> Missing space before ().

Ack.

> 
>> +	}
>> +    }
>> +  return state;
>> +}
>> +
>> +static void
>> +arc4random_getrandom_failure (void)
>> +{
>> +  __libc_fatal ("Fatal glibc error: cannot get entropy for arc4random\n");
>> +}
>> +
>> +static void
>> +arc4random_rekey (struct arc4random_state_t *state, uint8_t *rnd, size_t rndlen)
>> +{
>> +  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);
>> +}
> 
> Should that memset be explicit_bzero for clarity?

Ack, it makes sense.

> 
>> +static void
>> +arc4random_getentropy (void *rnd, size_t len)
>> +{
>> +  if (__getrandom_nocancel (rnd, len, GRND_NONBLOCK) == len)
>> +    return;
>> +
>> +  int fd = __open64_nocancel ("/dev/urandom", O_RDONLY | O_CLOEXEC);
> 
> This could use TEMP_FAILURE_RETRY, too.

Hum, it makes sense since we abort on a failure.

> 
>> +  if (fd != -1)
>> +    {
>> +      uint8_t *p = rnd;
>> +      uint8_t *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 ();
>> +}
>> +
>> +/* Reinit the thread context by reseeding the cipher state with kernel
>> +   entropy.  */
>> +static void
>> +arc4random_check_stir (struct arc4random_state_t *state, size_t len)
> 
> Could you add a comment describing the len parameter?

I changed to:

/* Check if the thread context STATE should be reseed with kernel entropy
    depending of requested LEN bytes.  If there is less than requested,
    the state is either initialized or reseed, otherwise the internal
    counter subtract the requested lenght.  */


> 
>> +{
>> +  if (state->count < len || state->count == -1)
>> +    {
>> +      uint8_t rnd[CHACHA20_KEY_SIZE + CHACHA20_IV_SIZE];
>> +      arc4random_getentropy (rnd, sizeof rnd);
>> +
>> +      if (state->count == -1)
>> +	chacha20_init (state->ctx, rnd, rnd + CHACHA20_KEY_SIZE);
>> +      else
>> +	arc4random_rekey (state, rnd, sizeof rnd);
>> +
>> +      explicit_bzero (rnd, sizeof rnd);
>> +
>> +      state->have = 0;
>> +      memset (state->buf, 0, sizeof state->buf);
>> +      state->count = CHACHA20_RESEED_SIZE;
>> +    }
>> +  if (state->count <= len)
>> +    state->count = 0;
>> +  else
>> +    state->count -= len;
>> +}
> 
> It's not clear to me if we want to enter the true branch of the second
> if statement if we already executed the true branch of the first if
> statement.

It is not needed, neither we need to set the count to 0 since we
already reinitalized it.

> 
>> +void
>> +__arc4random_buf (void *buffer, size_t len)
>> +{
>> +  struct arc4random_state_t *state = arc4random_get_state ();
>> +  if (__glibc_unlikely (state == NULL))
>> +    {
>> +      arc4random_getentropy (buffer, len);
>> +      return;
>> +    }
>> +
>> +  arc4random_check_stir (state, 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);
> 
> Should be explicit_bzero, I think.

Ack.

> 
>> +	  buffer += m;
>> +	  len -= m;
>> +	  state->have -= m;
>> +	}
>> +      if (state->have == 0)
>> +	arc4random_rekey (state, NULL, 0);
>> +    }
>> +}
>> +libc_hidden_def (__arc4random_buf)
>> +weak_alias (__arc4random_buf, arc4random_buf)
>> +
>> +uint32_t
>> +__arc4random (void)
>> +{
>> +  uint32_t r;
>> +
>> +  struct arc4random_state_t *state = arc4random_get_state ();
>> +  if (__glibc_unlikely (state == NULL))
>> +    {
>> +      arc4random_getentropy (&r, sizeof (uint32_t));
>> +      return r;
>> +    }
>> +
>> +  arc4random_check_stir (state, sizeof (uint32_t));
>> +  if (state->have < sizeof (uint32_t))
>> +    arc4random_rekey (state, 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;
>> +}
> 
> Why not simply call __arc4random_buf?  If you want to retain the
> optimization, turn the implementation of __arc4random_buf into an inline
> function and call it here and from __arc4random_buf.

I actually tried in some interation and I recall that it yield some
worse throughput.  I just tested again and it holds true, on
an aarch64 system current approach with generic implementation yields
290 MB/s while calling arc4random_buf shows 172 MB/s.

I am trying to decompose the function to eliminate the need of the
loop (which I think compiler can't optimize away for arc4random)
but I don't think it would be simpler than open code the logic
on both functions.

> 
>> +libc_hidden_def (__arc4random)
>> +weak_alias (__arc4random, arc4random)
>> diff --git a/stdlib/arc4random.h b/stdlib/arc4random.h
>> new file mode 100644
>> index 0000000000..cdca639d9d
>> --- /dev/null
>> +++ b/stdlib/arc4random.h
>> @@ -0,0 +1,45 @@
> 
>> +/* Internal arc4random buffer, used on each feedback step so offer some
>> +   backtracking protection and to allow better used of vectorized
>> +   chacha20 implementations.  */
>> +#define CHACHA20_BUFSIZE        (8 * CHACHA20_BLOCK_SIZE)
> 
> Please add a _Static_assert that this is larger than CHACHA20_KEY_SIZE +
> CHACHA20_IV_SIZE because the implementation assumes this.

Ack.

> 
>> diff --git a/stdlib/chacha20.c b/stdlib/chacha20.c
>> new file mode 100644
>> index 0000000000..4549fc780f
>> --- /dev/null
>> +++ b/stdlib/chacha20.c
>> @@ -0,0 +1,187 @@
> 
>> +/* 32-bit stream position, then 96-bit nonce.  */
>> +#define CHACHA20_IV_SIZE	16
>> +#define CHACHA20_KEY_SIZE	32
>> +
>> +#define CHACHA20_STATE_LEN	16
>> +
>> +/* 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.  */
> 
> You can also remove the byte swapping because the key is random and
> discarded, so we don't care about its precise value.  You can do the
> swapping in the ChaCha20 test instead, to get reproducible test vectors.
> 
> Hmm, given that this impacts the assembler implementations as well,
> maybe we can do this at a later stage.

Right, I would prefer indeed to optimize it later. But it a good
suggestion.

> 
>> diff --git a/stdlib/stdlib.h b/stdlib/stdlib.h
>> index bf7cd438e1..f02a713a7b 100644
>> --- a/stdlib/stdlib.h
>> +++ b/stdlib/stdlib.h
>> @@ -485,6 +485,7 @@ extern unsigned short int *seed48 (unsigned short int __seed16v[3])
>>   extern void lcong48 (unsigned short int __param[7]) __THROW __nonnull ((1));
>>   
>>   # ifdef __USE_MISC
>> +#  include <bits/stdint-uintn.h>
>>   /* Data structure for communication with thread safe versions.  This
>>      type is to be regarded as opaque.  It's only exported because users
>>      have to allocate objects of this type.  */
> 
>> +/* Return a random number between zero (inclusive) and the specified
>> +   limit (exclusive).  */
>> +extern uint32_t arc4random_uniform (uint32_t __upper_bound)
>> +     __THROW __wur;
>>   # endif	/* Use misc.  */
>>   #endif	/* Use misc or X/Open.  */
> 
> I'm a bit worried about that <bits/stdint-uintn.h> inclusion.  It will
> be a bit confusing if these types become available via <stdlib.h> in
> some glibc versions.  Maybe use __uint32_t instead?

Hum ok, __uint32_t might work indeed.

> 
>> diff --git a/sysdeps/generic/tls-internal-struct.h b/sysdeps/generic/tls-internal-struct.h
>> index d76c715a96..81a71ac54b 100644
>> --- a/sysdeps/generic/tls-internal-struct.h
>> +++ b/sysdeps/generic/tls-internal-struct.h
>> @@ -19,10 +19,13 @@
>>   #ifndef _TLS_INTERNAL_STRUCT_H
>>   #define _TLS_INTERNAL_STRUCT_H 1
>>   
>> +#include <stdlib/arc4random.h>
>> +
> 
> You can use a forward declaration instead.  Minimizing <descr.h>
> dependencies seems desirable to me.
> 
>>   struct tls_internal_t
>>   {
>>     char *strsignal_buf;
>>     char *strerror_l_buf;
>> +  struct arc4random_state_t *rand_state;
>>   };
> 

Ack.

> 
>> diff --git a/sysdeps/generic/tls-internal.c b/sysdeps/generic/tls-internal.c
>> index 898c20b61c..ec0ceeebd1 100644
>> --- a/sysdeps/generic/tls-internal.c
>> +++ b/sysdeps/generic/tls-internal.c
>> @@ -16,6 +16,23 @@
>>      License along with the GNU C Library; if not, see
>>      <https://www.gnu.org/licenses/>.  */
>>   
>> +#include <string.h>
>>   #include <tls-internal.h>
>>   
>>   __thread struct tls_internal_t __tls_internal;
>> +
>> +void
>> +__glibc_tls_internal_free (void)
>> +{
>> +  free (__tls_internal.strsignal_buf);
>> +  free (__tls_internal.strerror_l_buf);
>> +
>> +  if (__tls_internal.rand_state != NULL)
>> +    {
>> +      /* Clear any lingering random state prior so if the thread stack is
>> +	 cached it won't leak any data.  */
>> +      explicit_bzero (__tls_internal.rand_state,
>> +		      sizeof (struct arc4random_state_t));
>> +      free (__tls_internal.rand_state);
>> +    }
> 
> sizeof (*__tls_internal.rand_state)?

Ack.

> 
>> diff --git a/sysdeps/mach/hurd/_Fork.c b/sysdeps/mach/hurd/_Fork.c
>> index e60b86fab1..1c44b39c5b 100644
>> --- a/sysdeps/mach/hurd/_Fork.c
>> +++ b/sysdeps/mach/hurd/_Fork.c
>> @@ -665,6 +665,8 @@ retry:
>>         /* Run things that want to run in the child task to set up.  */
>>         RUN_HOOK (_hurd_fork_child_hook, ());
>>   
>> +      call_function_static_weak (__arc4random_fork_subprocess);
>> +
> 
> Hmm, is the ordering correct?  Can _hurd_fork_child_hook run user code?
> (This probably needs review from Hurd developers.)

I don think so, in any case I moved it before _hurd_fork_child_hook.
Hurd developers can certify later if this in the correct place.

> 
>> diff --git a/sysdeps/unix/sysv/linux/tls-internal.c b/sysdeps/unix/sysv/linux/tls-internal.c
>> index 6e25b021ab..045176197e 100644
>> --- a/sysdeps/unix/sysv/linux/tls-internal.c
>> +++ b/sysdeps/unix/sysv/linux/tls-internal.c
>> @@ -1 +1,37 @@
> 
>> +void
>> +__glibc_tls_internal_free (void)
>> +{
>> +  struct pthread *self = THREAD_SELF;
>> +  free (self->tls_state.strsignal_buf);
>> +  free (self->tls_state.strerror_l_buf);
>> +
>> +  if (self->tls_state.rand_state != NULL)
>> +    {
>> +      /* Clear any lingering random state prior so if the thread stack is
>> +         cached it won't leak any data.  */
>> +      explicit_bzero (self->tls_state.rand_state,
>> +		      sizeof (struct arc4random_state_t));
> 
> sizeof (self->tls_state.rand_state)?

Ack.

> 
>> diff --git a/sysdeps/unix/sysv/linux/tls-internal.h b/sysdeps/unix/sysv/linux/tls-internal.h
>> index f7a1a62135..f268a2d43b 100644
>> --- a/sysdeps/unix/sysv/linux/tls-internal.h
>> +++ b/sysdeps/unix/sysv/linux/tls-internal.h
>> @@ -22,17 +22,21 @@
>>   #include <stdlib.h>
>>   #include <pthreadP.h>
>>   
>> +static inline void
>> +__glibc_tls_internal_init (struct tls_internal_t *tls_state)
>> +{
>> +  tls_state->strsignal_buf = NULL;
>> +  tls_state->strerror_l_buf = NULL;
>> +  tls_state->rand_state = NULL;
>> +}
> 
> See the comment about using memset earlier.

Ack.

> 
> Thanks,
> Florian
>