random.c revision 1.4 
1/*	$NetBSD: random.c,v 1.4 2020/05/24 19:46:26 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 http://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
65ISC_THREAD_LOCAL isc_once_t isc_random_once = ISC_ONCE_INIT;
66
67static void
68isc_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
82uint8_t
83isc_random8(void) {
84	RUNTIME_CHECK(isc_once_do(&isc_random_once, isc_random_initialize) ==
85		      ISC_R_SUCCESS);
86	return (next() & 0xff);
87}
88
89uint16_t
90isc_random16(void) {
91	RUNTIME_CHECK(isc_once_do(&isc_random_once, isc_random_initialize) ==
92		      ISC_R_SUCCESS);
93	return (next() & 0xffff);
94}
95
96uint32_t
97isc_random32(void) {
98	RUNTIME_CHECK(isc_once_do(&isc_random_once, isc_random_initialize) ==
99		      ISC_R_SUCCESS);
100	return (next());
101}
102
103void
104isc_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
123uint32_t
124isc_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