diff options
Diffstat (limited to 'stdlib')
| -rw-r--r-- | stdlib/Makefile | 2 | ||||
| -rw-r--r-- | stdlib/Versions | 5 | ||||
| -rw-r--r-- | stdlib/arc4random.c | 208 | ||||
| -rw-r--r-- | stdlib/arc4random.h | 48 | ||||
| -rw-r--r-- | stdlib/arc4random_uniform.c | 140 | ||||
| -rw-r--r-- | stdlib/chacha20.c | 187 | ||||
| -rw-r--r-- | stdlib/stdlib.h | 13 |
7 files changed, 603 insertions, 0 deletions
diff --git a/stdlib/Makefile b/stdlib/Makefile index d4a4d5679a..62f8253225 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..65547e79aa --- /dev/null +++ b/stdlib/arc4random.c @@ -0,0 +1,208 @@ +/* Pseudo Random Number Generator based on ChaCha20. + 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 + <https://www.gnu.org/licenses/>. */ + +#include <arc4random.h> +#include <errno.h> +#include <not-cancel.h> +#include <stdio.h> +#include <stdlib.h> +#include <sys/mman.h> +#include <sys/param.h> +#include <sys/random.h> +#include <tls-internal.h> + +/* 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 minimize + function call overhead. */ + +#include <chacha20.c> + +/* 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 (*state)); + /* 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; + 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; + } + } + 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 optional user provided data. */ + 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); + explicit_bzero (state->buf, CHACHA20_KEY_SIZE + CHACHA20_IV_SIZE); + state->have = sizeof (state->buf) - (CHACHA20_KEY_SIZE + CHACHA20_IV_SIZE); +} + +static void +arc4random_getentropy (void *rnd, size_t len) +{ + if (__getrandom_nocancel (rnd, len, GRND_NONBLOCK) == len) + return; + + int fd = TEMP_FAILURE_RETRY (__open64_nocancel ("/dev/urandom", + O_RDONLY | O_CLOEXEC)); + 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 (); +} + +/* 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 reseeded, otherwise the internal + counter subtract the requested length. */ +static void +arc4random_check_stir (struct arc4random_state_t *state, size_t len) +{ + 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); + + /* Invalidate the buf. */ + state->have = 0; + memset (state->buf, 0, sizeof state->buf); + state->count = CHACHA20_RESEED_SIZE; + } + else + state->count -= len; +} + +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); + explicit_bzero (ks, m); + 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; +} +libc_hidden_def (__arc4random) +weak_alias (__arc4random, arc4random) diff --git a/stdlib/arc4random.h b/stdlib/arc4random.h new file mode 100644 index 0000000000..cd39389c19 --- /dev/null +++ b/stdlib/arc4random.h @@ -0,0 +1,48 @@ +/* Arc4random definition used on TLS. + 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 + <https://www.gnu.org/licenses/>. */ + +#ifndef _CHACHA20_H +#define _CHACHA20_H + +#include <stddef.h> +#include <stdint.h> + +/* Internal ChaCha20 state. */ +#define CHACHA20_STATE_LEN 16 +#define CHACHA20_BLOCK_SIZE 64 + +/* Maximum number bytes until reseed (16 MB). */ +#define CHACHA20_RESEED_SIZE (16 * 1024 * 1024) + +/* 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) + +_Static_assert (CHACHA20_BUFSIZE >= CHACHA20_BLOCK_SIZE + CHACHA20_BLOCK_SIZE, + "CHACHA20_BUFSIZE < CHACHA20_BLOCK_SIZE + CHACHA20_BLOCK_SIZE"); + +struct arc4random_state_t +{ + uint32_t ctx[CHACHA20_STATE_LEN]; + size_t have; + size_t count; + uint8_t buf[CHACHA20_BUFSIZE]; +}; + +#endif diff --git a/stdlib/arc4random_uniform.c b/stdlib/arc4random_uniform.c new file mode 100644 index 0000000000..1326dfa593 --- /dev/null +++ b/stdlib/arc4random_uniform.c @@ -0,0 +1,140 @@ +/* Random pseudo generator number which returns a single 32 bit value + 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 + <https://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 (ptr, byte_count); +} + +uint32_t +__arc4random_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_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..c47b8418f2 --- /dev/null +++ b/stdlib/chacha20.c @@ -0,0 +1,187 @@ +/* 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 + <https://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_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. */ + +enum chacha20_constants +{ + CHACHA20_CONSTANT_EXPA = 0x61707865U, + CHACHA20_CONSTANT_ND_3 = 0x3320646eU, + CHACHA20_CONSTANT_2_BY = 0x79622d32U, + CHACHA20_CONSTANT_TE_K = 0x6b206574U +}; + +static inline uint32_t +read_unaligned_32 (const uint8_t *p) +{ + uint32_t r; + memcpy (&r, p, sizeof (r)); + return r; +} + +static inline void +write_unaligned_32 (uint8_t *p, uint32_t v) +{ + memcpy (p, &v, sizeof (v)); +} + +#if __BYTE_ORDER == __BIG_ENDIAN +# define read_unaligned_le32(p) __builtin_bswap32 (read_unaligned_32 (p)) +# define set_state(v) __builtin_bswap32 ((v)) +#else +# define read_unaligned_le32(p) read_unaligned_32 ((p)) +# define set_state(v) (v) +#endif + +static inline void +chacha20_init (uint32_t *state, const uint8_t *key, const uint8_t *iv) +{ + state[0] = CHACHA20_CONSTANT_EXPA; + state[1] = CHACHA20_CONSTANT_ND_3; + state[2] = CHACHA20_CONSTANT_2_BY; + state[3] = CHACHA20_CONSTANT_TE_K; + + state[4] = read_unaligned_le32 (key + 0 * sizeof (uint32_t)); + state[5] = read_unaligned_le32 (key + 1 * sizeof (uint32_t)); + state[6] = read_unaligned_le32 (key + 2 * sizeof (uint32_t)); + state[7] = read_unaligned_le32 (key + 3 * sizeof (uint32_t)); + state[8] = read_unaligned_le32 (key + 4 * sizeof (uint32_t)); + state[9] = read_unaligned_le32 (key + 5 * sizeof (uint32_t)); + state[10] = read_unaligned_le32 (key + 6 * sizeof (uint32_t)); + state[11] = read_unaligned_le32 (key + 7 * sizeof (uint32_t)); + + state[12] = read_unaligned_le32 (iv + 0 * sizeof (uint32_t)); + state[13] = read_unaligned_le32 (iv + 1 * sizeof (uint32_t)); + state[14] = read_unaligned_le32 (iv + 2 * sizeof (uint32_t)); + state[15] = read_unaligned_le32 (iv + 3 * sizeof (uint32_t)); +} + +static inline uint32_t +rotl32 (unsigned int shift, uint32_t word) +{ + return (word << (shift & 31)) | (word >> ((-shift) & 31)); +} + +static void +state_final (const uint8_t *src, uint8_t *dst, uint32_t v) +{ +#ifdef CHACHA20_XOR_FINAL + v ^= read_unaligned_32 (src); +#endif + write_unaligned_32 (dst, v); +} + +static inline void +chacha20_block (uint32_t *state, uint8_t *dst, const uint8_t *src) +{ + uint32_t x0, x1, x2, x3, x4, x5, x6, x7; + uint32_t x8, x9, x10, x11, x12, x13, x14, x15; + + x0 = state[0]; + x1 = state[1]; + x2 = state[2]; + x3 = state[3]; + x4 = state[4]; + x5 = state[5]; + x6 = state[6]; + x7 = state[7]; + x8 = state[8]; + x9 = state[9]; + x10 = state[10]; + x11 = state[11]; + x12 = state[12]; + x13 = state[13]; + x14 = state[14]; + x15 = state[15]; + + for (int i = 0; i < 20; i += 2) + { +#define QROUND(_x0, _x1, _x2, _x3) \ + do { \ + _x0 = _x0 + _x1; _x3 = rotl32 (16, (_x0 ^ _x3)); \ + _x2 = _x2 + _x3; _x1 = rotl32 (12, (_x1 ^ _x2)); \ + _x0 = _x0 + _x1; _x3 = rotl32 (8, (_x0 ^ _x3)); \ + _x2 = _x2 + _x3; _x1 = rotl32 (7, (_x1 ^ _x2)); \ + } while(0) + + QROUND (x0, x4, x8, x12); + QROUND (x1, x5, x9, x13); + QROUND (x2, x6, x10, x14); + QROUND (x3, x7, x11, x15); + + QROUND (x0, x5, x10, x15); + QROUND (x1, x6, x11, x12); + QROUND (x2, x7, x8, x13); + QROUND (x3, x4, x9, x14); + } + + state_final (&src[0], &dst[0], set_state (x0 + state[0])); + state_final (&src[4], &dst[4], set_state (x1 + state[1])); + state_final (&src[8], &dst[8], set_state (x2 + state[2])); + state_final (&src[12], &dst[12], set_state (x3 + state[3])); + state_final (&src[16], &dst[16], set_state (x4 + state[4])); + state_final (&src[20], &dst[20], set_state (x5 + state[5])); + state_final (&src[24], &dst[24], set_state (x6 + state[6])); + state_final (&src[28], &dst[28], set_state (x7 + state[7])); + state_final (&src[32], &dst[32], set_state (x8 + state[8])); + state_final (&src[36], &dst[36], set_state (x9 + state[9])); + state_final (&src[40], &dst[40], set_state (x10 + state[10])); + state_final (&src[44], &dst[44], set_state (x11 + state[11])); + state_final (&src[48], &dst[48], set_state (x12 + state[12])); + state_final (&src[52], &dst[52], set_state (x13 + state[13])); + state_final (&src[56], &dst[56], set_state (x14 + state[14])); + state_final (&src[60], &dst[60], set_state (x15 + state[15])); + + state[12]++; +} + +static void +chacha20_crypt (uint32_t *state, uint8_t *dst, const uint8_t *src, + size_t bytes) +{ + while (bytes >= CHACHA20_BLOCK_SIZE) + { + chacha20_block (state, dst, src); + + bytes -= CHACHA20_BLOCK_SIZE; + dst += CHACHA20_BLOCK_SIZE; + src += CHACHA20_BLOCK_SIZE; + } + + if (__glibc_unlikely (bytes != 0)) + { + uint8_t stream[CHACHA20_BLOCK_SIZE]; + chacha20_block (state, stream, src); + memcpy (dst, stream, bytes); + explicit_bzero (stream, sizeof stream); + } +} diff --git a/stdlib/stdlib.h b/stdlib/stdlib.h index bf7cd438e1..3a630a0ce8 100644 --- a/stdlib/stdlib.h +++ b/stdlib/stdlib.h @@ -533,6 +533,19 @@ extern int seed48_r (unsigned short int __seed16v[3], extern int lcong48_r (unsigned short int __param[7], struct drand48_data *__buffer) __THROW __nonnull ((1, 2)); + +/* Return a random integer between zero and 2**32-1 (inclusive). */ +extern __uint32_t arc4random (void) + __THROW __wur; + +/* Fill the buffer with random data. */ +extern void arc4random_buf (void *__buf, size_t __size) + __THROW __nonnull ((1)); + +/* 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. */ |