random.c revision 1.2 
1/*	$NetBSD: random.c,v 1.2 2018/08/12 13:02:37 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 * ChaCha based random number generator derived from OpenBSD.
16 *
17 * The original copyright follows:
18 * Copyright (c) 1996, David Mazieres <dm@uun.org>
19 * Copyright (c) 2008, Damien Miller <djm@openbsd.org>
20 * Copyright (c) 2013, Markus Friedl <markus@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/*! \file */
36
37#include <config.h>
38
39#include <stdlib.h>
40#include <time.h>		/* Required for time(). */
41#ifdef HAVE_SYS_TYPES_H
42#include <sys/types.h>
43#endif
44#ifdef HAVE_UNISTD_H
45#include <unistd.h>
46#endif
47
48#include <isc/magic.h>
49#include <isc/mutex.h>
50#include <isc/once.h>
51#include <isc/mem.h>
52#include <isc/entropy.h>
53#include <isc/random.h>
54#include <isc/safe.h>
55#include <isc/string.h>
56#include <isc/util.h>
57
58#define RNG_MAGIC			ISC_MAGIC('R', 'N', 'G', 'x')
59#define VALID_RNG(r)			ISC_MAGIC_VALID(r, RNG_MAGIC)
60
61#define KEYSTREAM_ONLY
62#include "chacha_private.h"
63
64#define CHACHA_KEYSIZE 32U
65#define CHACHA_IVSIZE 8U
66#define CHACHA_BLOCKSIZE 64
67#define CHACHA_BUFFERSIZE (16 * CHACHA_BLOCKSIZE)
68#define CHACHA_MAXHAVE (CHACHA_BUFFERSIZE - CHACHA_KEYSIZE - CHACHA_IVSIZE)
69/*
70 * Derived from OpenBSD's implementation.  The rationale is not clear,
71 * but should be conservative enough in safety, and reasonably large for
72 * efficiency.
73 */
74#define CHACHA_MAXLENGTH 1600000
75
76/* ChaCha RNG state */
77struct isc_rng {
78	unsigned int	magic;
79	isc_mem_t	*mctx;
80	chacha_ctx	cpctx;
81	isc_uint8_t	buffer[CHACHA_BUFFERSIZE];
82	size_t		have;
83	unsigned int	references;
84	int		count;
85	isc_entropy_t	*entropy;	/*%< entropy source */
86	isc_mutex_t	lock;
87};
88
89static isc_once_t once = ISC_ONCE_INIT;
90
91static void
92initialize_rand(void) {
93#ifndef HAVE_ARC4RANDOM
94	unsigned int pid = getpid();
95
96	/*
97	 * The low bits of pid generally change faster.
98	 * Xor them with the high bits of time which change slowly.
99	 */
100	pid = ((pid << 16) & 0xffff0000) | ((pid >> 16) & 0xffff);
101
102	srand((unsigned)time(NULL) ^ pid);
103#endif
104}
105
106static void
107initialize(void) {
108	RUNTIME_CHECK(isc_once_do(&once, initialize_rand) == ISC_R_SUCCESS);
109}
110
111void
112isc_random_seed(isc_uint32_t seed) {
113	initialize();
114
115#ifndef HAVE_ARC4RANDOM
116	srand(seed);
117#elif defined(HAVE_ARC4RANDOM_STIR)
118	/* Formally not necessary... */
119	UNUSED(seed);
120	arc4random_stir();
121#elif defined(HAVE_ARC4RANDOM_ADDRANDOM)
122	arc4random_addrandom((u_char *) &seed, sizeof(isc_uint32_t));
123#else
124       /*
125	* If arc4random() is available and no corresponding seeding
126	* function arc4random_addrandom() is available, no seeding is
127	* done on such platforms (e.g., OpenBSD 5.5).  This is because
128	* the OS itself is supposed to seed the RNG and it is assumed
129	* that no explicit seeding is required.
130	*/
131       UNUSED(seed);
132#endif
133}
134
135void
136isc_random_get(isc_uint32_t *val) {
137	REQUIRE(val != NULL);
138
139	initialize();
140
141#ifndef HAVE_ARC4RANDOM
142	/*
143	 * rand()'s lower bits are not random.
144	 * rand()'s upper bit is zero.
145	 */
146#if RAND_MAX >= 0xfffff
147	/* We have at least 20 bits.  Use lower 16 excluding lower most 4 */
148	*val = ((((unsigned int)rand()) & 0xffff0) >> 4) |
149	       ((((unsigned int)rand()) & 0xffff0) << 12);
150#elif RAND_MAX >= 0x7fff
151	/* We have at least 15 bits.  Use lower 10/11 excluding lower most 4 */
152	*val = ((rand() >> 4) & 0x000007ff) | ((rand() << 7) & 0x003ff800) |
153		((rand() << 18) & 0xffc00000);
154#else
155#error RAND_MAX is too small
156#endif
157#else
158	*val = arc4random();
159#endif
160}
161
162isc_uint32_t
163isc_random_jitter(isc_uint32_t max, isc_uint32_t jitter) {
164	isc_uint32_t rnd;
165
166	REQUIRE(jitter < max || (jitter == 0 && max == 0));
167
168	if (jitter == 0)
169		return (max);
170
171	isc_random_get(&rnd);
172	return (max - rnd % jitter);
173}
174
175static void
176chacha_reinit(isc_rng_t *rng, isc_uint8_t *buffer, size_t n) {
177	REQUIRE(rng != NULL);
178
179	if (n < CHACHA_KEYSIZE + CHACHA_IVSIZE)
180		return;
181
182	chacha_keysetup(&rng->cpctx, buffer, CHACHA_KEYSIZE * 8, 0);
183	chacha_ivsetup(&rng->cpctx, buffer + CHACHA_KEYSIZE);
184}
185
186isc_result_t
187isc_rng_create(isc_mem_t *mctx, isc_entropy_t *entropy, isc_rng_t **rngp) {
188	union {
189		unsigned char rnd[128];
190		isc_uint32_t rnd32[32];
191	} rnd;
192	isc_result_t result;
193	isc_rng_t *rng;
194
195	REQUIRE(mctx != NULL);
196	REQUIRE(rngp != NULL && *rngp == NULL);
197
198	if (entropy != NULL) {
199		/*
200		 * We accept any quality of random data to avoid blocking.
201		 */
202		result = isc_entropy_getdata(entropy, rnd.rnd,
203					     sizeof(rnd), NULL, 0);
204		RUNTIME_CHECK(result == ISC_R_SUCCESS);
205	} else {
206		int i;
207		for (i = 0; i < 32; i++)
208			isc_random_get(&rnd.rnd32[i]);
209	}
210
211	rng = isc_mem_get(mctx, sizeof(*rng));
212	if (rng == NULL)
213		return (ISC_R_NOMEMORY);
214
215	chacha_reinit(rng, rnd.rnd, sizeof(rnd.rnd));
216
217	rng->have = 0;
218	memset(rng->buffer, 0, CHACHA_BUFFERSIZE);
219
220	/* Create lock */
221	result = isc_mutex_init(&rng->lock);
222	if (result != ISC_R_SUCCESS) {
223		isc_mem_put(mctx, rng, sizeof(*rng));
224		return (result);
225	}
226
227	/* Attach to memory context */
228	rng->mctx = NULL;
229	isc_mem_attach(mctx, &rng->mctx);
230
231	/* Local non-algorithm initializations. */
232	rng->count = 0;
233	rng->entropy = entropy; /* don't have to attach */
234	rng->references = 1;
235	rng->magic = RNG_MAGIC;
236
237	*rngp = rng;
238
239	return (ISC_R_SUCCESS);
240}
241
242void
243isc_rng_attach(isc_rng_t *source, isc_rng_t **targetp) {
244
245	REQUIRE(VALID_RNG(source));
246	REQUIRE(targetp != NULL && *targetp == NULL);
247
248	LOCK(&source->lock);
249	source->references++;
250	UNLOCK(&source->lock);
251
252	*targetp = (isc_rng_t *)source;
253}
254
255static void
256destroy(isc_rng_t *rng) {
257
258	REQUIRE(VALID_RNG(rng));
259
260	rng->magic = 0;
261	isc_mutex_destroy(&rng->lock);
262	isc_mem_putanddetach(&rng->mctx, rng, sizeof(isc_rng_t));
263}
264
265void
266isc_rng_detach(isc_rng_t **rngp) {
267	isc_rng_t *rng;
268	isc_boolean_t dest = ISC_FALSE;
269
270	REQUIRE(rngp != NULL && VALID_RNG(*rngp));
271
272	rng = *rngp;
273	*rngp = NULL;
274
275	LOCK(&rng->lock);
276
277	INSIST(rng->references > 0);
278	rng->references--;
279	if (rng->references == 0)
280		dest = ISC_TRUE;
281	UNLOCK(&rng->lock);
282
283	if (dest)
284		destroy(rng);
285}
286
287static void
288chacha_rekey(isc_rng_t *rng, u_char *dat, size_t datlen) {
289	REQUIRE(VALID_RNG(rng));
290
291#ifndef KEYSTREAM_ONLY
292	memset(rng->buffer, 0, CHACHA_BUFFERSIZE);
293#endif
294
295	/* Fill buffer with the keystream. */
296	chacha_encrypt_bytes(&rng->cpctx, rng->buffer, rng->buffer,
297			     CHACHA_BUFFERSIZE);
298
299	/* Mix in optional user provided data. */
300	if (dat != NULL) {
301		size_t i, m;
302
303		m = ISC_MIN(datlen, CHACHA_KEYSIZE + CHACHA_IVSIZE);
304		for (i = 0; i < m; i++)
305			rng->buffer[i] ^= dat[i];
306	}
307
308	/* Immediately reinit for backtracking resistance. */
309	chacha_reinit(rng, rng->buffer,
310		      CHACHA_KEYSIZE + CHACHA_IVSIZE);
311	memset(rng->buffer, 0, CHACHA_KEYSIZE + CHACHA_IVSIZE);
312	rng->have = CHACHA_MAXHAVE;
313}
314
315static void
316chacha_getbytes(isc_rng_t *rng, isc_uint8_t *output, size_t length) {
317	REQUIRE(VALID_RNG(rng));
318
319	while (ISC_UNLIKELY(length > CHACHA_MAXHAVE)) {
320		chacha_rekey(rng, NULL, 0);
321		memmove(output, rng->buffer + CHACHA_BUFFERSIZE - rng->have,
322			CHACHA_MAXHAVE);
323		output += CHACHA_MAXHAVE;
324		length -= CHACHA_MAXHAVE;
325		rng->have = 0;
326	}
327
328	if (rng->have < length)
329		chacha_rekey(rng, NULL, 0);
330
331	memmove(output, rng->buffer + CHACHA_BUFFERSIZE - rng->have, length);
332	/* Clear the copied region. */
333	memset(rng->buffer + CHACHA_BUFFERSIZE - rng->have, 0, length);
334	rng->have -= length;
335}
336
337static void
338chacha_stir(isc_rng_t *rng) {
339	union {
340		unsigned char rnd[128];
341		isc_uint32_t rnd32[32];
342	} rnd;
343	isc_result_t result;
344
345	REQUIRE(VALID_RNG(rng));
346
347	if (rng->entropy != NULL) {
348		/*
349		 * We accept any quality of random data to avoid blocking.
350		 */
351		result = isc_entropy_getdata(rng->entropy, rnd.rnd,
352					     sizeof(rnd), NULL, 0);
353		RUNTIME_CHECK(result == ISC_R_SUCCESS);
354	} else {
355		int i;
356		for (i = 0; i < 32; i++)
357			isc_random_get(&rnd.rnd32[i]);
358	}
359
360	chacha_rekey(rng, rnd.rnd, sizeof(rnd.rnd));
361
362	isc_safe_memwipe(rnd.rnd, sizeof(rnd.rnd));
363
364	/* Invalidate the buffer too. */
365	rng->have = 0;
366	memset(rng->buffer, 0, CHACHA_BUFFERSIZE);
367
368	/*
369	 * Derived from OpenBSD's implementation.  The rationale is not clear,
370	 * but should be conservative enough in safety, and reasonably large
371	 * for efficiency.
372	 */
373	rng->count = CHACHA_MAXLENGTH;
374}
375
376void
377isc_rng_randombytes(isc_rng_t *rng, void *output, size_t length) {
378	isc_uint8_t *ptr = output;
379
380	REQUIRE(VALID_RNG(rng));
381	REQUIRE(output != NULL && length > 0);
382
383	LOCK(&rng->lock);
384
385	while (ISC_UNLIKELY(length > CHACHA_MAXLENGTH)) {
386		chacha_stir(rng);
387		chacha_getbytes(rng, ptr, CHACHA_MAXLENGTH);
388		ptr += CHACHA_MAXLENGTH;
389		length -= CHACHA_MAXLENGTH;
390		rng->count = 0;
391	}
392
393	rng->count -= length;
394	if (rng->count <= 0)
395		chacha_stir(rng);
396
397	chacha_getbytes(rng, ptr, length);
398
399	UNLOCK(&rng->lock);
400}
401
402isc_uint16_t
403isc_rng_random(isc_rng_t *rng) {
404	isc_uint16_t result;
405
406	isc_rng_randombytes(rng, &result, sizeof(result));
407
408	return (result);
409}
410
411isc_uint16_t
412isc_rng_uniformrandom(isc_rng_t *rng, isc_uint16_t upper_bound) {
413	isc_uint16_t min, r;
414
415	REQUIRE(VALID_RNG(rng));
416
417	if (upper_bound < 2)
418		return (0);
419
420	/*
421	 * Ensure the range of random numbers [min, 0xffff] be a multiple of
422	 * upper_bound and contain at least a half of the 16 bit range.
423	 */
424
425	if (upper_bound > 0x8000)
426		min = 1 + ~upper_bound; /* 0x8000 - upper_bound */
427	else
428		min = (isc_uint16_t)(0x10000 % (isc_uint32_t)upper_bound);
429
430	/*
431	 * This could theoretically loop forever but each retry has
432	 * p > 0.5 (worst case, usually far better) of selecting a
433	 * number inside the range we need, so it should rarely need
434	 * to re-roll.
435	 */
436	for (;;) {
437		isc_rng_randombytes(rng, &r, sizeof(r));
438		if (r >= min)
439			break;
440	}
441
442	return (r % upper_bound);
443}
444