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

[Adhemerval Zanella]

On 19/04/2022 18:52, H.J. Lu wrote:
> On Tue, Apr 19, 2022 at 2:29 PM Adhemerval Zanella via Libc-alpha
> <libc-alpha@sourceware.org> wrote:
>>
>>
>> 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.
>                                          ^^^^^^^^ Typo.
>>
>>  Deprecated and removed features, and other changes affecting compatibility:

Ack.


>> +
>> +/* 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
>                                          ^^^^^^^^^^^^^^^^ Typo?
>> +   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
>                                                               ^^^^^^^^^^^^ Typo?

Ack.

>> +
>> +  /* 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
>                                than

Ack.

>> +     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)
>> diff --git a/stdlib/chacha20.c b/stdlib/chacha20.c
>> new file mode 100644
>> index 0000000000..af4ffa9860
>> --- /dev/null
>> +++ b/stdlib/chacha20.c
>> @@ -0,0 +1,163 @@
>> +/* Generic ChaCha20 implementation (used on arc4random).
>> +   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 <array_length.h>
>> +#include <endian.h>
>> +#include <stddef.h>
>> +#include <stdint.h>
>> +#include <string.h>
>> +
>> +/* 32-bit stream position, then 96-bit nonce.  */
>> +#define CHACHA20_IV_SIZE       16
>> +#define CHACHA20_KEY_SIZE      32
>> +
>> +#define CHACHA20_BLOCK_SIZE     64
>> +#define CHACHA20_BLOCK_WORDS    (CHACHA20_BLOCK_SIZE / sizeof (uint32_t))
>> +
>> +#define CHACHA20_STATE_LEN     16
>> +
>> +/* Defining CHACHA20_XOR_FINAL issues the final XOR using the input as defined
>> +   Sby RFC8439.  Since the input stream will either zero bytes (initial state)
>          by

Ack.