1/* OPENBSD ORIGINAL: lib/libc/crypto/arc4random.c */
2
3/*	$OpenBSD: arc4random.c,v 1.25 2013/10/01 18:34:57 markus Exp $	*/
4
5/*
6 * Copyright (c) 1996, David Mazieres <dm@uun.org>
7 * Copyright (c) 2008, Damien Miller <djm@openbsd.org>
8 * Copyright (c) 2013, Markus Friedl <markus@openbsd.org>
9 *
10 * Permission to use, copy, modify, and distribute this software for any
11 * purpose with or without fee is hereby granted, provided that the above
12 * copyright notice and this permission notice appear in all copies.
13 *
14 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
15 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
16 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
17 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
18 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
19 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
20 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
21 */
22
23/*
24 * ChaCha based random number generator for OpenBSD.
25 */
26
27#include "includes.h"
28
29#include <sys/types.h>
30
31#include <fcntl.h>
32#include <stdlib.h>
33#include <string.h>
34#include <unistd.h>
35
36#ifdef HAVE_SYS_RANDOM_H
37# include <sys/random.h>
38#endif
39
40#ifndef HAVE_ARC4RANDOM
41
42#ifdef WITH_OPENSSL
43#include <openssl/rand.h>
44#include <openssl/err.h>
45#endif
46
47#include "log.h"
48
49#define KEYSTREAM_ONLY
50#include "chacha_private.h"
51
52#ifdef __GNUC__
53#define inline __inline
54#else				/* !__GNUC__ */
55#define inline
56#endif				/* !__GNUC__ */
57
58/* OpenSSH isn't multithreaded */
59#define _ARC4_LOCK()
60#define _ARC4_UNLOCK()
61
62#define KEYSZ	32
63#define IVSZ	8
64#define BLOCKSZ	64
65#define RSBUFSZ	(16*BLOCKSZ)
66static int rs_initialized;
67static pid_t rs_stir_pid;
68static chacha_ctx rs;		/* chacha context for random keystream */
69static u_char rs_buf[RSBUFSZ];	/* keystream blocks */
70static size_t rs_have;		/* valid bytes at end of rs_buf */
71static size_t rs_count;		/* bytes till reseed */
72
73static inline void _rs_rekey(u_char *dat, size_t datlen);
74
75static inline void
76_rs_init(u_char *buf, size_t n)
77{
78	if (n < KEYSZ + IVSZ)
79		return;
80	chacha_keysetup(&rs, buf, KEYSZ * 8, 0);
81	chacha_ivsetup(&rs, buf + KEYSZ);
82}
83
84#ifndef WITH_OPENSSL
85# ifndef SSH_RANDOM_DEV
86#  define SSH_RANDOM_DEV "/dev/urandom"
87# endif /* SSH_RANDOM_DEV */
88static void
89getrnd(u_char *s, size_t len)
90{
91	int fd;
92	ssize_t r;
93	size_t o = 0;
94
95#ifdef HAVE_GETRANDOM
96	if ((r = getrandom(s, len, 0)) > 0 && (size_t)r == len)
97		return;
98#endif /* HAVE_GETRANDOM */
99
100	if ((fd = open(SSH_RANDOM_DEV, O_RDONLY)) == -1)
101		fatal("Couldn't open %s: %s", SSH_RANDOM_DEV, strerror(errno));
102	while (o < len) {
103		r = read(fd, s + o, len - o);
104		if (r < 0) {
105			if (errno == EAGAIN || errno == EINTR ||
106			    errno == EWOULDBLOCK)
107				continue;
108			fatal("read %s: %s", SSH_RANDOM_DEV, strerror(errno));
109		}
110		o += r;
111	}
112	close(fd);
113}
114#endif /* WITH_OPENSSL */
115
116static void
117_rs_stir(void)
118{
119	u_char rnd[KEYSZ + IVSZ];
120
121#ifdef WITH_OPENSSL
122	if (RAND_bytes(rnd, sizeof(rnd)) <= 0)
123		fatal("Couldn't obtain random bytes (error 0x%lx)",
124		    (unsigned long)ERR_get_error());
125#else
126	getrnd(rnd, sizeof(rnd));
127#endif
128
129	if (!rs_initialized) {
130		rs_initialized = 1;
131		_rs_init(rnd, sizeof(rnd));
132	} else
133		_rs_rekey(rnd, sizeof(rnd));
134	explicit_bzero(rnd, sizeof(rnd));
135
136	/* invalidate rs_buf */
137	rs_have = 0;
138	memset(rs_buf, 0, RSBUFSZ);
139
140	rs_count = 1600000;
141}
142
143static inline void
144_rs_stir_if_needed(size_t len)
145{
146	pid_t pid = getpid();
147
148	if (rs_count <= len || !rs_initialized || rs_stir_pid != pid) {
149		rs_stir_pid = pid;
150		_rs_stir();
151	} else
152		rs_count -= len;
153}
154
155static inline void
156_rs_rekey(u_char *dat, size_t datlen)
157{
158#ifndef KEYSTREAM_ONLY
159	memset(rs_buf, 0,RSBUFSZ);
160#endif
161	/* fill rs_buf with the keystream */
162	chacha_encrypt_bytes(&rs, rs_buf, rs_buf, RSBUFSZ);
163	/* mix in optional user provided data */
164	if (dat) {
165		size_t i, m;
166
167		m = MIN(datlen, KEYSZ + IVSZ);
168		for (i = 0; i < m; i++)
169			rs_buf[i] ^= dat[i];
170	}
171	/* immediately reinit for backtracking resistance */
172	_rs_init(rs_buf, KEYSZ + IVSZ);
173	memset(rs_buf, 0, KEYSZ + IVSZ);
174	rs_have = RSBUFSZ - KEYSZ - IVSZ;
175}
176
177static inline void
178_rs_random_buf(void *_buf, size_t n)
179{
180	u_char *buf = (u_char *)_buf;
181	size_t m;
182
183	_rs_stir_if_needed(n);
184	while (n > 0) {
185		if (rs_have > 0) {
186			m = MIN(n, rs_have);
187			memcpy(buf, rs_buf + RSBUFSZ - rs_have, m);
188			memset(rs_buf + RSBUFSZ - rs_have, 0, m);
189			buf += m;
190			n -= m;
191			rs_have -= m;
192		}
193		if (rs_have == 0)
194			_rs_rekey(NULL, 0);
195	}
196}
197
198static inline void
199_rs_random_u32(u_int32_t *val)
200{
201	_rs_stir_if_needed(sizeof(*val));
202	if (rs_have < sizeof(*val))
203		_rs_rekey(NULL, 0);
204	memcpy(val, rs_buf + RSBUFSZ - rs_have, sizeof(*val));
205	memset(rs_buf + RSBUFSZ - rs_have, 0, sizeof(*val));
206	rs_have -= sizeof(*val);
207	return;
208}
209
210void
211arc4random_stir(void)
212{
213	_ARC4_LOCK();
214	_rs_stir();
215	_ARC4_UNLOCK();
216}
217
218void
219arc4random_addrandom(u_char *dat, int datlen)
220{
221	int m;
222
223	_ARC4_LOCK();
224	if (!rs_initialized)
225		_rs_stir();
226	while (datlen > 0) {
227		m = MIN(datlen, KEYSZ + IVSZ);
228		_rs_rekey(dat, m);
229		dat += m;
230		datlen -= m;
231	}
232	_ARC4_UNLOCK();
233}
234
235u_int32_t
236arc4random(void)
237{
238	u_int32_t val;
239
240	_ARC4_LOCK();
241	_rs_random_u32(&val);
242	_ARC4_UNLOCK();
243	return val;
244}
245
246/*
247 * If we are providing arc4random, then we can provide a more efficient
248 * arc4random_buf().
249 */
250# ifndef HAVE_ARC4RANDOM_BUF
251void
252arc4random_buf(void *buf, size_t n)
253{
254	_ARC4_LOCK();
255	_rs_random_buf(buf, n);
256	_ARC4_UNLOCK();
257}
258# endif /* !HAVE_ARC4RANDOM_BUF */
259#endif /* !HAVE_ARC4RANDOM */
260
261/* arc4random_buf() that uses platform arc4random() */
262#if !defined(HAVE_ARC4RANDOM_BUF) && defined(HAVE_ARC4RANDOM)
263void
264arc4random_buf(void *_buf, size_t n)
265{
266	size_t i;
267	u_int32_t r = 0;
268	char *buf = (char *)_buf;
269
270	for (i = 0; i < n; i++) {
271		if (i % 4 == 0)
272			r = arc4random();
273		buf[i] = r & 0xff;
274		r >>= 8;
275	}
276	explicit_bzero(&r, sizeof(r));
277}
278#endif /* !defined(HAVE_ARC4RANDOM_BUF) && defined(HAVE_ARC4RANDOM) */
279
280#ifndef HAVE_ARC4RANDOM_UNIFORM
281/*
282 * Calculate a uniformly distributed random number less than upper_bound
283 * avoiding "modulo bias".
284 *
285 * Uniformity is achieved by generating new random numbers until the one
286 * returned is outside the range [0, 2**32 % upper_bound).  This
287 * guarantees the selected random number will be inside
288 * [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound)
289 * after reduction modulo upper_bound.
290 */
291u_int32_t
292arc4random_uniform(u_int32_t upper_bound)
293{
294	u_int32_t r, min;
295
296	if (upper_bound < 2)
297		return 0;
298
299	/* 2**32 % x == (2**32 - x) % x */
300	min = -upper_bound % upper_bound;
301
302	/*
303	 * This could theoretically loop forever but each retry has
304	 * p > 0.5 (worst case, usually far better) of selecting a
305	 * number inside the range we need, so it should rarely need
306	 * to re-roll.
307	 */
308	for (;;) {
309		r = arc4random();
310		if (r >= min)
311			break;
312	}
313
314	return r % upper_bound;
315}
316#endif /* !HAVE_ARC4RANDOM_UNIFORM */
317
318#if 0
319/*-------- Test code for i386 --------*/
320#include <stdio.h>
321#include <machine/pctr.h>
322int
323main(int argc, char **argv)
324{
325	const int iter = 1000000;
326	int     i;
327	pctrval v;
328
329	v = rdtsc();
330	for (i = 0; i < iter; i++)
331		arc4random();
332	v = rdtsc() - v;
333	v /= iter;
334
335	printf("%qd cycles\n", v);
336	exit(0);
337}
338#endif
339