1 /* $NetBSD: random.c,v 1.5 2021/02/19 16:42:19 christos Exp $ */ 2 3 /* 4 * Copyright (C) Internet Systems Consortium, Inc. ("ISC") 5 * 6 * This Source Code Form is subject to the terms of the Mozilla Public 7 * License, v. 2.0. If a copy of the MPL was not distributed with this 8 * file, you can obtain one at https://mozilla.org/MPL/2.0/. 9 * 10 * See the COPYRIGHT file distributed with this work for additional 11 * information regarding copyright ownership. 12 */ 13 14 /* 15 * Portions of isc_random_uniform(): 16 * 17 * Copyright (c) 1996, David Mazieres <dm@uun.org> 18 * Copyright (c) 2008, Damien Miller <djm@openbsd.org> 19 * 20 * Permission to use, copy, modify, and distribute this software for any 21 * purpose with or without fee is hereby granted, provided that the above 22 * copyright notice and this permission notice appear in all copies. 23 * 24 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 25 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 26 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 27 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 28 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 29 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 30 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 31 */ 32 33 #include <inttypes.h> 34 #include <stdlib.h> 35 #include <string.h> 36 #include <unistd.h> 37 38 #include <isc/once.h> 39 #include <isc/platform.h> 40 #include <isc/random.h> 41 #include <isc/result.h> 42 #include <isc/thread.h> 43 #include <isc/types.h> 44 #include <isc/util.h> 45 46 #include "entropy_private.h" 47 48 /* 49 * The specific implementation for PRNG is included as a C file 50 * that has to provide a static variable named seed, and a function 51 * uint32_t next(void) that provides next random number. 52 * 53 * The implementation must be thread-safe. 54 */ 55 56 /* 57 * Two contestants have been considered: the xoroshiro family of the 58 * functions by Villa&Blackman, and PCG by O'Neill. After 59 * consideration, the xoshiro128starstar function has been chosen as 60 * the uint32_t random number provider because it is very fast and has 61 * good enough properties for our usage pattern. 62 */ 63 #include "xoshiro128starstar.c" 64 65 ISC_THREAD_LOCAL isc_once_t isc_random_once = ISC_ONCE_INIT; 66 67 static void 68 isc_random_initialize(void) { 69 int useed[4] = { 0, 0, 0, 1 }; 70 #if FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION 71 /* 72 * Set a constant seed to help in problem reproduction should fuzzing 73 * find a crash or a hang. The seed array must be non-zero else 74 * xoshiro128starstar will generate an infinite series of zeroes. 75 */ 76 #else /* if FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION */ 77 isc_entropy_get(useed, sizeof(useed)); 78 #endif /* if FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION */ 79 memmove(seed, useed, sizeof(seed)); 80 } 81 82 uint8_t 83 isc_random8(void) { 84 RUNTIME_CHECK(isc_once_do(&isc_random_once, isc_random_initialize) == 85 ISC_R_SUCCESS); 86 return (next() & 0xff); 87 } 88 89 uint16_t 90 isc_random16(void) { 91 RUNTIME_CHECK(isc_once_do(&isc_random_once, isc_random_initialize) == 92 ISC_R_SUCCESS); 93 return (next() & 0xffff); 94 } 95 96 uint32_t 97 isc_random32(void) { 98 RUNTIME_CHECK(isc_once_do(&isc_random_once, isc_random_initialize) == 99 ISC_R_SUCCESS); 100 return (next()); 101 } 102 103 void 104 isc_random_buf(void *buf, size_t buflen) { 105 int i; 106 uint32_t r; 107 108 REQUIRE(buf != NULL); 109 REQUIRE(buflen > 0); 110 111 RUNTIME_CHECK(isc_once_do(&isc_random_once, isc_random_initialize) == 112 ISC_R_SUCCESS); 113 114 for (i = 0; i + sizeof(r) <= buflen; i += sizeof(r)) { 115 r = next(); 116 memmove((uint8_t *)buf + i, &r, sizeof(r)); 117 } 118 r = next(); 119 memmove((uint8_t *)buf + i, &r, buflen % sizeof(r)); 120 return; 121 } 122 123 uint32_t 124 isc_random_uniform(uint32_t upper_bound) { 125 /* Copy of arc4random_uniform from OpenBSD */ 126 uint32_t r, min; 127 128 RUNTIME_CHECK(isc_once_do(&isc_random_once, isc_random_initialize) == 129 ISC_R_SUCCESS); 130 131 if (upper_bound < 2) { 132 return (0); 133 } 134 135 #if (ULONG_MAX > 0xffffffffUL) 136 min = 0x100000000UL % upper_bound; 137 #else /* if (ULONG_MAX > 0xffffffffUL) */ 138 /* Calculate (2**32 % upper_bound) avoiding 64-bit math */ 139 if (upper_bound > 0x80000000) { 140 min = 1 + ~upper_bound; /* 2**32 - upper_bound */ 141 } else { 142 /* (2**32 - (x * 2)) % x == 2**32 % x when x <= 2**31 */ 143 min = ((0xffffffff - (upper_bound * 2)) + 1) % upper_bound; 144 } 145 #endif /* if (ULONG_MAX > 0xffffffffUL) */ 146 147 /* 148 * This could theoretically loop forever but each retry has 149 * p > 0.5 (worst case, usually far better) of selecting a 150 * number inside the range we need, so it should rarely need 151 * to re-roll. 152 */ 153 for (;;) { 154 r = next(); 155 if (r >= min) { 156 break; 157 } 158 } 159 160 return (r % upper_bound); 161 } 162