From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp5-g21.free.fr (smtp5-g21.free.fr [IPv6:2a01:e0c:1:1599::14]) by sourceware.org (Postfix) with ESMTPS id 2ED8F3858C2C for ; Fri, 22 Apr 2022 13:54:16 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 2ED8F3858C2C Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=opteya.com Authentication-Results: sourceware.org; spf=fail smtp.mailfrom=opteya.com Received: from [IPV6:2a01:e35:39f2:1220:a594:78ec:7cc0:11b3] (unknown [IPv6:2a01:e35:39f2:1220:a594:78ec:7cc0:11b3]) by smtp5-g21.free.fr (Postfix) with ESMTPS id BF3415FFC4; Fri, 22 Apr 2022 15:54:11 +0200 (CEST) Message-ID: <9b6f8e87-9226-7828-3569-cff0e3575f9a@opteya.com> Date: Fri, 22 Apr 2022 15:54:11 +0200 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:91.0) Gecko/20100101 Thunderbird/91.7.0 Subject: Re: [PATCH v3 1/9] stdlib: Add arc4random, arc4random_buf, and arc4random_uniform (BZ #4417) Content-Language: fr-FR To: Adhemerval Zanella , libc-alpha@sourceware.org Cc: Florian Weimer References: <20220419212812.2688764-1-adhemerval.zanella@linaro.org> <20220419212812.2688764-2-adhemerval.zanella@linaro.org> From: Yann Droneaud Organization: OPTEYA In-Reply-To: <20220419212812.2688764-2-adhemerval.zanella@linaro.org> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit X-Spam-Status: No, score=-9.8 required=5.0 tests=BAYES_00, GIT_PATCH_0, KAM_DMARC_STATUS, KAM_SHORT, NICE_REPLY_A, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_SOFTFAIL, TXREP autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on server2.sourceware.org X-BeenThere: libc-alpha@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Libc-alpha mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 22 Apr 2022 13:54:19 -0000 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 > > [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 > + . */ > + > +#include > +#include > +#include > +#include > +#include > +#include > +#include > +#include > + > +/* 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 > + > +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 > + . */ > + > +#include > +#include > +#include > +#include > + > +/* 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