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