1/*	$NetBSD: arc4random.c,v 1.5 2020/05/25 20:47:33 christos Exp $	*/
2
3/* Portable arc4random.c based on arc4random.c from OpenBSD.
4 * Portable version by Chris Davis, adapted for Libevent by Nick Mathewson
5 * Copyright (c) 2010 Chris Davis, Niels Provos, and Nick Mathewson
6 * Copyright (c) 2010-2012 Niels Provos and Nick Mathewson
7 *
8 * Note that in Libevent, this file isn't compiled directly.  Instead,
9 * it's included from evutil_rand.c
10 */
11
12/*
13 * Copyright (c) 1996, David Mazieres <dm@uun.org>
14 * Copyright (c) 2008, Damien Miller <djm@openbsd.org>
15 *
16 * Permission to use, copy, modify, and distribute this software for any
17 * purpose with or without fee is hereby granted, provided that the above
18 * copyright notice and this permission notice appear in all copies.
19 *
20 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
21 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
22 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
23 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
24 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
25 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
26 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
27 */
28
29/*
30 * Arc4 random number generator for OpenBSD.
31 *
32 * This code is derived from section 17.1 of Applied Cryptography,
33 * second edition, which describes a stream cipher allegedly
34 * compatible with RSA Labs "RC4" cipher (the actual description of
35 * which is a trade secret).  The same algorithm is used as a stream
36 * cipher called "arcfour" in Tatu Ylonen's ssh package.
37 *
38 * Here the stream cipher has been modified always to include the time
39 * when initializing the state.  That makes it impossible to
40 * regenerate the same random sequence twice, so this can't be used
41 * for encryption, but will generate good random numbers.
42 *
43 * RC4 is a registered trademark of RSA Laboratories.
44 */
45
46#ifndef ARC4RANDOM_EXPORT
47#define ARC4RANDOM_EXPORT
48#endif
49
50#ifndef ARC4RANDOM_UINT32
51#define ARC4RANDOM_UINT32 uint32_t
52#endif
53
54#ifndef ARC4RANDOM_NO_INCLUDES
55#include "evconfig-private.h"
56#ifdef _WIN32
57#include <wincrypt.h>
58#include <process.h>
59#else
60#include <fcntl.h>
61#include <unistd.h>
62#include <sys/param.h>
63#include <sys/time.h>
64#ifdef EVENT__HAVE_SYS_SYSCTL_H
65#include <sys/sysctl.h>
66#endif
67#endif
68#include <limits.h>
69#include <stdlib.h>
70#include <string.h>
71#endif
72
73/* Add platform entropy 32 bytes (256 bits) at a time. */
74#define ADD_ENTROPY 32
75
76/* Re-seed from the platform RNG after generating this many bytes. */
77#define BYTES_BEFORE_RESEED 1600000
78
79struct arc4_stream {
80	unsigned char i;
81	unsigned char j;
82	unsigned char s[256];
83};
84
85#ifdef _WIN32
86#define getpid _getpid
87#define pid_t int
88#endif
89
90static int rs_initialized;
91static struct arc4_stream rs;
92static pid_t arc4_stir_pid;
93static int arc4_count;
94static int arc4_seeded_ok;
95
96static inline unsigned char arc4_getbyte(void);
97
98static inline void
99arc4_init(void)
100{
101	int     n;
102
103	for (n = 0; n < 256; n++)
104		rs.s[n] = n;
105	rs.i = 0;
106	rs.j = 0;
107}
108
109static inline void
110arc4_addrandom(const unsigned char *dat, int datlen)
111{
112	int     n;
113	unsigned char si;
114
115	rs.i--;
116	for (n = 0; n < 256; n++) {
117		rs.i = (rs.i + 1);
118		si = rs.s[rs.i];
119		rs.j = (rs.j + si + dat[n % datlen]);
120		rs.s[rs.i] = rs.s[rs.j];
121		rs.s[rs.j] = si;
122	}
123	rs.j = rs.i;
124}
125
126#ifndef _WIN32
127static ssize_t
128read_all(int fd, unsigned char *buf, size_t count)
129{
130	size_t numread = 0;
131	ssize_t result;
132
133	while (numread < count) {
134		result = read(fd, buf+numread, count-numread);
135		if (result<0)
136			return -1;
137		else if (result == 0)
138			break;
139		numread += result;
140	}
141
142	return (ssize_t)numread;
143}
144#endif
145
146#ifdef _WIN32
147#define TRY_SEED_WIN32
148static int
149arc4_seed_win32(void)
150{
151	/* This is adapted from Tor's crypto_seed_rng() */
152	static int provider_set = 0;
153	static HCRYPTPROV provider;
154	unsigned char buf[ADD_ENTROPY];
155
156	if (!provider_set) {
157		if (!CryptAcquireContext(&provider, NULL, NULL, PROV_RSA_FULL,
158		    CRYPT_VERIFYCONTEXT)) {
159			if (GetLastError() != (DWORD)NTE_BAD_KEYSET)
160				return -1;
161		}
162		provider_set = 1;
163	}
164	if (!CryptGenRandom(provider, sizeof(buf), buf))
165		return -1;
166	arc4_addrandom(buf, sizeof(buf));
167	evutil_memclear_(buf, sizeof(buf));
168	arc4_seeded_ok = 1;
169	return 0;
170}
171#endif
172
173#if defined(EVENT__HAVE_SYS_SYSCTL_H) && defined(EVENT__HAVE_SYSCTL)
174#if EVENT__HAVE_DECL_CTL_KERN && EVENT__HAVE_DECL_KERN_RANDOM && EVENT__HAVE_DECL_RANDOM_UUID
175#define TRY_SEED_SYSCTL_LINUX
176static int
177arc4_seed_sysctl_linux(void)
178{
179	/* Based on code by William Ahern, this function tries to use the
180	 * RANDOM_UUID sysctl to get entropy from the kernel.  This can work
181	 * even if /dev/urandom is inaccessible for some reason (e.g., we're
182	 * running in a chroot). */
183	int mib[] = { CTL_KERN, KERN_RANDOM, RANDOM_UUID };
184	unsigned char buf[ADD_ENTROPY];
185	size_t len, n;
186	unsigned i;
187	int any_set;
188
189	memset(buf, 0, sizeof(buf));
190
191	for (len = 0; len < sizeof(buf); len += n) {
192		n = sizeof(buf) - len;
193
194		if (0 != sysctl(mib, 3, &buf[len], &n, NULL, 0))
195			return -1;
196	}
197	/* make sure that the buffer actually got set. */
198	for (i=0,any_set=0; i<sizeof(buf); ++i) {
199		any_set |= buf[i];
200	}
201	if (!any_set)
202		return -1;
203
204	arc4_addrandom(buf, sizeof(buf));
205	evutil_memclear_(buf, sizeof(buf));
206	arc4_seeded_ok = 1;
207	return 0;
208}
209#endif
210
211#if EVENT__HAVE_DECL_CTL_KERN && EVENT__HAVE_DECL_KERN_ARND
212#define TRY_SEED_SYSCTL_BSD
213static int
214arc4_seed_sysctl_bsd(void)
215{
216	/* Based on code from William Ahern and from OpenBSD, this function
217	 * tries to use the KERN_ARND syscall to get entropy from the kernel.
218	 * This can work even if /dev/urandom is inaccessible for some reason
219	 * (e.g., we're running in a chroot). */
220	int mib[] = { CTL_KERN, KERN_ARND };
221	unsigned char buf[ADD_ENTROPY];
222	size_t len, n;
223	int i, any_set;
224
225	memset(buf, 0, sizeof(buf));
226
227	len = sizeof(buf);
228	if (sysctl(mib, 2, buf, &len, NULL, 0) == -1) {
229		for (len = 0; len < sizeof(buf); len += sizeof(unsigned)) {
230			n = sizeof(unsigned);
231			if (n + len > sizeof(buf))
232			    n = len - sizeof(buf);
233			if (sysctl(mib, 2, &buf[len], &n, NULL, 0) == -1)
234				return -1;
235		}
236	}
237	/* make sure that the buffer actually got set. */
238	for (i=any_set=0; i<sizeof(buf); ++i) {
239		any_set |= buf[i];
240	}
241	if (!any_set)
242		return -1;
243
244	arc4_addrandom(buf, sizeof(buf));
245	evutil_memclear_(buf, sizeof(buf));
246	arc4_seeded_ok = 1;
247	return 0;
248}
249#endif
250#endif /* defined(EVENT__HAVE_SYS_SYSCTL_H) */
251
252#ifdef __linux__
253#define TRY_SEED_PROC_SYS_KERNEL_RANDOM_UUID
254static int
255arc4_seed_proc_sys_kernel_random_uuid(void)
256{
257	/* Occasionally, somebody will make /proc/sys accessible in a chroot,
258	 * but not /dev/urandom.  Let's try /proc/sys/kernel/random/uuid.
259	 * Its format is stupid, so we need to decode it from hex.
260	 */
261	int fd;
262	char buf[128];
263	unsigned char entropy[64];
264	int bytes, n, i, nybbles;
265	for (bytes = 0; bytes<ADD_ENTROPY; ) {
266		fd = evutil_open_closeonexec_("/proc/sys/kernel/random/uuid", O_RDONLY, 0);
267		if (fd < 0)
268			return -1;
269		n = read(fd, buf, sizeof(buf));
270		close(fd);
271		if (n<=0)
272			return -1;
273		memset(entropy, 0, sizeof(entropy));
274		for (i=nybbles=0; i<n; ++i) {
275			if (EVUTIL_ISXDIGIT_(buf[i])) {
276				int nyb = evutil_hex_char_to_int_(buf[i]);
277				if (nybbles & 1) {
278					entropy[nybbles/2] |= nyb;
279				} else {
280					entropy[nybbles/2] |= nyb<<4;
281				}
282				++nybbles;
283			}
284		}
285		if (nybbles < 2)
286			return -1;
287		arc4_addrandom(entropy, nybbles/2);
288		bytes += nybbles/2;
289	}
290	evutil_memclear_(entropy, sizeof(entropy));
291	evutil_memclear_(buf, sizeof(buf));
292	arc4_seeded_ok = 1;
293	return 0;
294}
295#endif
296
297#ifndef _WIN32
298#define TRY_SEED_URANDOM
299static char *arc4random_urandom_filename = NULL;
300
301static int arc4_seed_urandom_helper_(const char *fname)
302{
303	unsigned char buf[ADD_ENTROPY];
304	int fd;
305	size_t n;
306
307	fd = evutil_open_closeonexec_(fname, O_RDONLY, 0);
308	if (fd<0)
309		return -1;
310	n = read_all(fd, buf, sizeof(buf));
311	close(fd);
312	if (n != sizeof(buf))
313		return -1;
314	arc4_addrandom(buf, sizeof(buf));
315	evutil_memclear_(buf, sizeof(buf));
316	arc4_seeded_ok = 1;
317	return 0;
318}
319
320static int
321arc4_seed_urandom(void)
322{
323	/* This is adapted from Tor's crypto_seed_rng() */
324	static const char *filenames[] = {
325		"/dev/srandom", "/dev/urandom", "/dev/random", NULL
326	};
327	int i;
328	if (arc4random_urandom_filename)
329		return arc4_seed_urandom_helper_(arc4random_urandom_filename);
330
331	for (i = 0; filenames[i]; ++i) {
332		if (arc4_seed_urandom_helper_(filenames[i]) == 0) {
333			return 0;
334		}
335	}
336
337	return -1;
338}
339#endif
340
341static int
342arc4_seed(void)
343{
344	int ok = 0;
345	/* We try every method that might work, and don't give up even if one
346	 * does seem to work.  There's no real harm in over-seeding, and if
347	 * one of these sources turns out to be broken, that would be bad. */
348#ifdef TRY_SEED_WIN32
349	if (0 == arc4_seed_win32())
350		ok = 1;
351#endif
352#ifdef TRY_SEED_URANDOM
353	if (0 == arc4_seed_urandom())
354		ok = 1;
355#endif
356#ifdef TRY_SEED_PROC_SYS_KERNEL_RANDOM_UUID
357	if (arc4random_urandom_filename == NULL &&
358	    0 == arc4_seed_proc_sys_kernel_random_uuid())
359		ok = 1;
360#endif
361#ifdef TRY_SEED_SYSCTL_LINUX
362	/* Apparently Linux is deprecating sysctl, and spewing warning
363	 * messages when you try to use it. */
364	if (!ok && 0 == arc4_seed_sysctl_linux())
365		ok = 1;
366#endif
367#ifdef TRY_SEED_SYSCTL_BSD
368	if (0 == arc4_seed_sysctl_bsd())
369		ok = 1;
370#endif
371	return ok ? 0 : -1;
372}
373
374static int
375arc4_stir(void)
376{
377	int     i;
378
379	if (!rs_initialized) {
380		arc4_init();
381		rs_initialized = 1;
382	}
383
384	arc4_seed();
385	if (!arc4_seeded_ok)
386		return -1;
387
388	/*
389	 * Discard early keystream, as per recommendations in
390	 * "Weaknesses in the Key Scheduling Algorithm of RC4" by
391	 * Scott Fluhrer, Itsik Mantin, and Adi Shamir.
392	 * http://www.wisdom.weizmann.ac.il/~itsik/RC4/Papers/Rc4_ksa.ps
393	 *
394	 * Ilya Mironov's "(Not So) Random Shuffles of RC4" suggests that
395	 * we drop at least 2*256 bytes, with 12*256 as a conservative
396	 * value.
397	 *
398	 * RFC4345 says to drop 6*256.
399	 *
400	 * At least some versions of this code drop 4*256, in a mistaken
401	 * belief that "words" in the Fluhrer/Mantin/Shamir paper refers
402	 * to processor words.
403	 *
404	 * We add another sect to the cargo cult, and choose 12*256.
405	 */
406	for (i = 0; i < 12*256; i++)
407		(void)arc4_getbyte();
408
409	arc4_count = BYTES_BEFORE_RESEED;
410
411	return 0;
412}
413
414
415static void
416arc4_stir_if_needed(void)
417{
418	pid_t pid = getpid();
419
420	if (arc4_count <= 0 || !rs_initialized || arc4_stir_pid != pid)
421	{
422		arc4_stir_pid = pid;
423		arc4_stir();
424	}
425}
426
427static inline unsigned char
428arc4_getbyte(void)
429{
430	unsigned char si, sj;
431
432	rs.i = (rs.i + 1);
433	si = rs.s[rs.i];
434	rs.j = (rs.j + si);
435	sj = rs.s[rs.j];
436	rs.s[rs.i] = sj;
437	rs.s[rs.j] = si;
438	return (rs.s[(si + sj) & 0xff]);
439}
440
441static inline unsigned int
442arc4_getword(void)
443{
444	unsigned int val;
445
446	val = arc4_getbyte() << 24;
447	val |= arc4_getbyte() << 16;
448	val |= arc4_getbyte() << 8;
449	val |= arc4_getbyte();
450
451	return val;
452}
453
454#ifndef ARC4RANDOM_NOSTIR
455ARC4RANDOM_EXPORT int
456arc4random_stir(void)
457{
458	int val;
459	ARC4_LOCK_();
460	val = arc4_stir();
461	ARC4_UNLOCK_();
462	return val;
463}
464#endif
465
466#ifndef ARC4RANDOM_NOADDRANDOM
467ARC4RANDOM_EXPORT void
468arc4random_addrandom(const unsigned char *dat, int datlen)
469{
470	int j;
471	ARC4_LOCK_();
472	if (!rs_initialized)
473		arc4_stir();
474	for (j = 0; j < datlen; j += 256) {
475		/* arc4_addrandom() ignores all but the first 256 bytes of
476		 * its input.  We want to make sure to look at ALL the
477		 * data in 'dat', just in case the user is doing something
478		 * crazy like passing us all the files in /var/log. */
479		arc4_addrandom(dat + j, datlen - j);
480	}
481	ARC4_UNLOCK_();
482}
483#endif
484
485#ifndef ARC4RANDOM_NORANDOM
486ARC4RANDOM_EXPORT ARC4RANDOM_UINT32
487arc4random(void)
488{
489	ARC4RANDOM_UINT32 val;
490	ARC4_LOCK_();
491	arc4_count -= 4;
492	arc4_stir_if_needed();
493	val = arc4_getword();
494	ARC4_UNLOCK_();
495	return val;
496}
497#endif
498
499ARC4RANDOM_EXPORT void
500arc4random_buf(void *buf_, size_t n)
501{
502	unsigned char *buf = buf_;
503	ARC4_LOCK_();
504	arc4_stir_if_needed();
505	while (n--) {
506		if (--arc4_count <= 0)
507			arc4_stir();
508		buf[n] = arc4_getbyte();
509	}
510	ARC4_UNLOCK_();
511}
512
513#ifndef ARC4RANDOM_NOUNIFORM
514/*
515 * Calculate a uniformly distributed random number less than upper_bound
516 * avoiding "modulo bias".
517 *
518 * Uniformity is achieved by generating new random numbers until the one
519 * returned is outside the range [0, 2**32 % upper_bound).  This
520 * guarantees the selected random number will be inside
521 * [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound)
522 * after reduction modulo upper_bound.
523 */
524ARC4RANDOM_EXPORT unsigned int
525arc4random_uniform(unsigned int upper_bound)
526{
527	ARC4RANDOM_UINT32 r, min;
528
529	if (upper_bound < 2)
530		return 0;
531
532#if (UINT_MAX > 0xffffffffUL)
533	min = 0x100000000UL % upper_bound;
534#else
535	/* Calculate (2**32 % upper_bound) avoiding 64-bit math */
536	if (upper_bound > 0x80000000)
537		min = 1 + ~upper_bound;		/* 2**32 - upper_bound */
538	else {
539		/* (2**32 - (x * 2)) % x == 2**32 % x when x <= 2**31 */
540		min = ((0xffffffff - (upper_bound * 2)) + 1) % upper_bound;
541	}
542#endif
543
544	/*
545	 * This could theoretically loop forever but each retry has
546	 * p > 0.5 (worst case, usually far better) of selecting a
547	 * number inside the range we need, so it should rarely need
548	 * to re-roll.
549	 */
550	for (;;) {
551		r = arc4random();
552		if (r >= min)
553			break;
554	}
555
556	return r % upper_bound;
557}
558#endif
559