From ea648e70a989cca190cd7403fe892fd2dcc290b4 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sun, 5 May 2024 20:37:14 +0200 Subject: Adding upstream version 1:9.11.5.P4+dfsg. Signed-off-by: Daniel Baumann --- lib/isc/random.c | 415 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 415 insertions(+) create mode 100644 lib/isc/random.c (limited to 'lib/isc/random.c') diff --git a/lib/isc/random.c b/lib/isc/random.c new file mode 100644 index 0000000..b79b689 --- /dev/null +++ b/lib/isc/random.c @@ -0,0 +1,415 @@ +/* + * Copyright (C) Internet Systems Consortium, Inc. ("ISC") + * + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. + * + * See the COPYRIGHT file distributed with this work for additional + * information regarding copyright ownership. + */ + +/*% + * ChaCha based random number generator derived from OpenBSD. + * + * The original copyright follows: + * Copyright (c) 1996, David Mazieres + * Copyright (c) 2008, Damien Miller + * Copyright (c) 2013, Markus Friedl + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +/*! \file */ + +#include + +#include +#include +#include /* Required for time(). */ +#ifdef HAVE_SYS_TYPES_H +#include +#endif +#ifdef HAVE_UNISTD_H +#include +#endif + +#include +#include +#include +#include +#include +#include +#include +#include +#include + +#define RNG_MAGIC ISC_MAGIC('R', 'N', 'G', 'x') +#define VALID_RNG(r) ISC_MAGIC_VALID(r, RNG_MAGIC) + +#define KEYSTREAM_ONLY +#include "chacha_private.h" + +#define CHACHA_KEYSIZE 32U +#define CHACHA_IVSIZE 8U +#define CHACHA_BLOCKSIZE 64 +#define CHACHA_BUFFERSIZE (16 * CHACHA_BLOCKSIZE) + +/* ChaCha RNG state */ +struct isc_rng { + unsigned int magic; + isc_mem_t *mctx; + chacha_ctx cpctx; + uint8_t buffer[CHACHA_BUFFERSIZE]; + size_t have; + unsigned int references; + int count; + isc_entropy_t *entropy; /*%< entropy source */ + isc_mutex_t lock; +}; + +static isc_once_t once = ISC_ONCE_INIT; + +static void +initialize_rand(void) { +#ifndef HAVE_ARC4RANDOM + unsigned int pid = getpid(); + + /* + * The low bits of pid generally change faster. + * Xor them with the high bits of time which change slowly. + */ + pid = ((pid << 16) & 0xffff0000) | ((pid >> 16) & 0xffff); + + srand((unsigned)time(NULL) ^ pid); +#endif +} + +static void +initialize(void) { + RUNTIME_CHECK(isc_once_do(&once, initialize_rand) == ISC_R_SUCCESS); +} + +void +isc_random_seed(uint32_t seed) { + initialize(); + +#ifndef HAVE_ARC4RANDOM + srand(seed); +#elif defined(HAVE_ARC4RANDOM_STIR) + /* Formally not necessary... */ + UNUSED(seed); + arc4random_stir(); +#elif defined(HAVE_ARC4RANDOM_ADDRANDOM) + arc4random_addrandom((u_char *) &seed, sizeof(uint32_t)); +#else + /* + * If arc4random() is available and no corresponding seeding + * function arc4random_addrandom() is available, no seeding is + * done on such platforms (e.g., OpenBSD 5.5). This is because + * the OS itself is supposed to seed the RNG and it is assumed + * that no explicit seeding is required. + */ + UNUSED(seed); +#endif +} + +void +isc_random_get(uint32_t *val) { + REQUIRE(val != NULL); + + initialize(); + +#ifndef HAVE_ARC4RANDOM + /* + * rand()'s lower bits are not random. + * rand()'s upper bit is zero. + */ +#if RAND_MAX >= 0xfffff + /* We have at least 20 bits. Use lower 16 excluding lower most 4 */ + *val = ((((unsigned int)rand()) & 0xffff0) >> 4) | + ((((unsigned int)rand()) & 0xffff0) << 12); +#elif RAND_MAX >= 0x7fff + /* We have at least 15 bits. Use lower 10/11 excluding lower most 4 */ + *val = ((rand() >> 4) & 0x000007ff) | ((rand() << 7) & 0x003ff800) | + ((rand() << 18) & 0xffc00000); +#else +#error RAND_MAX is too small +#endif +#else + *val = arc4random(); +#endif +} + +uint32_t +isc_random_jitter(uint32_t max, uint32_t jitter) { + uint32_t rnd; + + REQUIRE(jitter < max || (jitter == 0 && max == 0)); + + if (jitter == 0) + return (max); + + isc_random_get(&rnd); + return (max - rnd % jitter); +} + +static void +chacha_reinit(isc_rng_t *rng, uint8_t *buffer, size_t n) { + REQUIRE(rng != NULL); + + if (n < CHACHA_KEYSIZE + CHACHA_IVSIZE) + return; + + chacha_keysetup(&rng->cpctx, buffer, CHACHA_KEYSIZE * 8, 0); + chacha_ivsetup(&rng->cpctx, buffer + CHACHA_KEYSIZE); +} + +isc_result_t +isc_rng_create(isc_mem_t *mctx, isc_entropy_t *entropy, isc_rng_t **rngp) { + union { + unsigned char rnd[128]; + uint32_t rnd32[32]; + } rnd; + isc_result_t result; + isc_rng_t *rng; + + REQUIRE(mctx != NULL); + REQUIRE(rngp != NULL && *rngp == NULL); + + if (entropy != NULL) { + /* + * We accept any quality of random data to avoid blocking. + */ + result = isc_entropy_getdata(entropy, rnd.rnd, + sizeof(rnd), NULL, 0); + RUNTIME_CHECK(result == ISC_R_SUCCESS); + } else { + int i; + for (i = 0; i < 32; i++) + isc_random_get(&rnd.rnd32[i]); + } + + rng = isc_mem_get(mctx, sizeof(*rng)); + if (rng == NULL) + return (ISC_R_NOMEMORY); + + chacha_reinit(rng, rnd.rnd, sizeof(rnd.rnd)); + + rng->have = 0; + memset(rng->buffer, 0, CHACHA_BUFFERSIZE); + + /* Create lock */ + result = isc_mutex_init(&rng->lock); + if (result != ISC_R_SUCCESS) { + isc_mem_put(mctx, rng, sizeof(*rng)); + return (result); + } + + /* Attach to memory context */ + rng->mctx = NULL; + isc_mem_attach(mctx, &rng->mctx); + + /* Local non-algorithm initializations. */ + rng->count = 0; + rng->entropy = entropy; /* don't have to attach */ + rng->references = 1; + rng->magic = RNG_MAGIC; + + *rngp = rng; + + return (ISC_R_SUCCESS); +} + +void +isc_rng_attach(isc_rng_t *source, isc_rng_t **targetp) { + + REQUIRE(VALID_RNG(source)); + REQUIRE(targetp != NULL && *targetp == NULL); + + LOCK(&source->lock); + source->references++; + UNLOCK(&source->lock); + + *targetp = (isc_rng_t *)source; +} + +static void +destroy(isc_rng_t *rng) { + + REQUIRE(VALID_RNG(rng)); + + rng->magic = 0; + isc_mutex_destroy(&rng->lock); + isc_mem_putanddetach(&rng->mctx, rng, sizeof(isc_rng_t)); +} + +void +isc_rng_detach(isc_rng_t **rngp) { + isc_rng_t *rng; + bool dest = false; + + REQUIRE(rngp != NULL && VALID_RNG(*rngp)); + + rng = *rngp; + *rngp = NULL; + + LOCK(&rng->lock); + + INSIST(rng->references > 0); + rng->references--; + if (rng->references == 0) + dest = true; + UNLOCK(&rng->lock); + + if (dest) + destroy(rng); +} + +static void +chacha_rekey(isc_rng_t *rng, u_char *dat, size_t datlen) { + REQUIRE(VALID_RNG(rng)); + +#ifndef KEYSTREAM_ONLY + memset(rng->buffer, 0, CHACHA_BUFFERSIZE); +#endif + + /* Fill buffer with the keystream. */ + chacha_encrypt_bytes(&rng->cpctx, rng->buffer, rng->buffer, + CHACHA_BUFFERSIZE); + + /* Mix in optional user provided data. */ + if (dat != NULL) { + size_t i, m; + + m = ISC_MIN(datlen, CHACHA_KEYSIZE + CHACHA_IVSIZE); + for (i = 0; i < m; i++) + rng->buffer[i] ^= dat[i]; + } + + /* Immediately reinit for backtracking resistance. */ + chacha_reinit(rng, rng->buffer, + CHACHA_KEYSIZE + CHACHA_IVSIZE); + memset(rng->buffer, 0, CHACHA_KEYSIZE + CHACHA_IVSIZE); + rng->have = CHACHA_BUFFERSIZE - CHACHA_KEYSIZE - CHACHA_IVSIZE; +} + +static inline uint16_t +chacha_getuint16(isc_rng_t *rng) { + uint16_t val; + + REQUIRE(VALID_RNG(rng)); + + if (rng->have < sizeof(val)) + chacha_rekey(rng, NULL, 0); + + memmove(&val, rng->buffer + CHACHA_BUFFERSIZE - rng->have, + sizeof(val)); + /* Clear the copied region. */ + memset(rng->buffer + CHACHA_BUFFERSIZE - rng->have, + 0, sizeof(val)); + rng->have -= sizeof(val); + + return (val); +} + +static void +chacha_stir(isc_rng_t *rng) { + union { + unsigned char rnd[128]; + uint32_t rnd32[32]; + } rnd; + isc_result_t result; + + REQUIRE(VALID_RNG(rng)); + + if (rng->entropy != NULL) { + /* + * We accept any quality of random data to avoid blocking. + */ + result = isc_entropy_getdata(rng->entropy, rnd.rnd, + sizeof(rnd), NULL, 0); + RUNTIME_CHECK(result == ISC_R_SUCCESS); + } else { + int i; + for (i = 0; i < 32; i++) + isc_random_get(&rnd.rnd32[i]); + } + + chacha_rekey(rng, rnd.rnd, sizeof(rnd.rnd)); + + isc_safe_memwipe(rnd.rnd, sizeof(rnd.rnd)); + + /* Invalidate the buffer too. */ + rng->have = 0; + memset(rng->buffer, 0, CHACHA_BUFFERSIZE); + + /* + * Derived from OpenBSD's implementation. The rationale is not clear, + * but should be conservative enough in safety, and reasonably large + * for efficiency. + */ + rng->count = 1600000; +} + +uint16_t +isc_rng_random(isc_rng_t *rng) { + uint16_t result; + + REQUIRE(VALID_RNG(rng)); + + LOCK(&rng->lock); + + rng->count -= sizeof(uint16_t); + if (rng->count <= 0) + chacha_stir(rng); + result = chacha_getuint16(rng); + + UNLOCK(&rng->lock); + + return (result); +} + +uint16_t +isc_rng_uniformrandom(isc_rng_t *rng, uint16_t upper_bound) { + uint16_t min, r; + + REQUIRE(VALID_RNG(rng)); + + if (upper_bound < 2) + return (0); + + /* + * Ensure the range of random numbers [min, 0xffff] be a multiple of + * upper_bound and contain at least a half of the 16 bit range. + */ + + if (upper_bound > 0x8000) + min = 1 + ~upper_bound; /* 0x8000 - upper_bound */ + else + min = (uint16_t)(0x10000 % (uint32_t)upper_bound); + + /* + * This could theoretically loop forever but each retry has + * p > 0.5 (worst case, usually far better) of selecting a + * number inside the range we need, so it should rarely need + * to re-roll. + */ + for (;;) { + r = isc_rng_random(rng); + if (r >= min) + break; + } + + return (r % upper_bound); +} -- cgit v1.2.3