arc4random.c revision 295367 
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#ifndef HAVE_ARC4RANDOM
37
38#ifdef WITH_OPENSSL
39#include <openssl/rand.h>
40#include <openssl/err.h>
41#endif
42
43#include "log.h"
44
45#define KEYSTREAM_ONLY
46#include "chacha_private.h"
47
48#ifdef __GNUC__
49#define inline __inline
50#else				/* !__GNUC__ */
51#define inline
52#endif				/* !__GNUC__ */
53
54/* OpenSSH isn't multithreaded */
55#define _ARC4_LOCK()
56#define _ARC4_UNLOCK()
57
58#define KEYSZ	32
59#define IVSZ	8
60#define BLOCKSZ	64
61#define RSBUFSZ	(16*BLOCKSZ)
62static int rs_initialized;
63static pid_t rs_stir_pid;
64static chacha_ctx rs;		/* chacha context for random keystream */
65static u_char rs_buf[RSBUFSZ];	/* keystream blocks */
66static size_t rs_have;		/* valid bytes at end of rs_buf */
67static size_t rs_count;		/* bytes till reseed */
68
69static inline void _rs_rekey(u_char *dat, size_t datlen);
70
71static inline void
72_rs_init(u_char *buf, size_t n)
73{
74	if (n < KEYSZ + IVSZ)
75		return;
76	chacha_keysetup(&rs, buf, KEYSZ * 8, 0);
77	chacha_ivsetup(&rs, buf + KEYSZ);
78}
79
80#ifndef WITH_OPENSSL
81#define SSH_RANDOM_DEV "/dev/urandom"
82/* XXX use getrandom() if supported on Linux */
83static void
84getrnd(u_char *s, size_t len)
85{
86	int fd;
87	ssize_t r;
88	size_t o = 0;
89
90	if ((fd = open(SSH_RANDOM_DEV, O_RDONLY)) == -1)
91		fatal("Couldn't open %s: %s", SSH_RANDOM_DEV, strerror(errno));
92	while (o < len) {
93		r = read(fd, s + o, len - o);
94		if (r < 0) {
95			if (errno == EAGAIN || errno == EINTR ||
96			    errno == EWOULDBLOCK)
97				continue;
98			fatal("read %s: %s", SSH_RANDOM_DEV, strerror(errno));
99		}
100		o += r;
101	}
102	close(fd);
103}
104#endif
105
106static void
107_rs_stir(void)
108{
109	u_char rnd[KEYSZ + IVSZ];
110
111#ifdef WITH_OPENSSL
112	if (RAND_bytes(rnd, sizeof(rnd)) <= 0)
113		fatal("Couldn't obtain random bytes (error %ld)",
114		    ERR_get_error());
115#else
116	getrnd(rnd, sizeof(rnd));
117#endif
118
119	if (!rs_initialized) {
120		rs_initialized = 1;
121		_rs_init(rnd, sizeof(rnd));
122	} else
123		_rs_rekey(rnd, sizeof(rnd));
124	explicit_bzero(rnd, sizeof(rnd));
125
126	/* invalidate rs_buf */
127	rs_have = 0;
128	memset(rs_buf, 0, RSBUFSZ);
129
130	rs_count = 1600000;
131}
132
133static inline void
134_rs_stir_if_needed(size_t len)
135{
136	pid_t pid = getpid();
137
138	if (rs_count <= len || !rs_initialized || rs_stir_pid != pid) {
139		rs_stir_pid = pid;
140		_rs_stir();
141	} else
142		rs_count -= len;
143}
144
145static inline void
146_rs_rekey(u_char *dat, size_t datlen)
147{
148#ifndef KEYSTREAM_ONLY
149	memset(rs_buf, 0,RSBUFSZ);
150#endif
151	/* fill rs_buf with the keystream */
152	chacha_encrypt_bytes(&rs, rs_buf, rs_buf, RSBUFSZ);
153	/* mix in optional user provided data */
154	if (dat) {
155		size_t i, m;
156
157		m = MIN(datlen, KEYSZ + IVSZ);
158		for (i = 0; i < m; i++)
159			rs_buf[i] ^= dat[i];
160	}
161	/* immediately reinit for backtracking resistance */
162	_rs_init(rs_buf, KEYSZ + IVSZ);
163	memset(rs_buf, 0, KEYSZ + IVSZ);
164	rs_have = RSBUFSZ - KEYSZ - IVSZ;
165}
166
167static inline void
168_rs_random_buf(void *_buf, size_t n)
169{
170	u_char *buf = (u_char *)_buf;
171	size_t m;
172
173	_rs_stir_if_needed(n);
174	while (n > 0) {
175		if (rs_have > 0) {
176			m = MIN(n, rs_have);
177			memcpy(buf, rs_buf + RSBUFSZ - rs_have, m);
178			memset(rs_buf + RSBUFSZ - rs_have, 0, m);
179			buf += m;
180			n -= m;
181			rs_have -= m;
182		}
183		if (rs_have == 0)
184			_rs_rekey(NULL, 0);
185	}
186}
187
188static inline void
189_rs_random_u32(u_int32_t *val)
190{
191	_rs_stir_if_needed(sizeof(*val));
192	if (rs_have < sizeof(*val))
193		_rs_rekey(NULL, 0);
194	memcpy(val, rs_buf + RSBUFSZ - rs_have, sizeof(*val));
195	memset(rs_buf + RSBUFSZ - rs_have, 0, sizeof(*val));
196	rs_have -= sizeof(*val);
197	return;
198}
199
200void
201arc4random_stir(void)
202{
203	_ARC4_LOCK();
204	_rs_stir();
205	_ARC4_UNLOCK();
206}
207
208void
209arc4random_addrandom(u_char *dat, int datlen)
210{
211	int m;
212
213	_ARC4_LOCK();
214	if (!rs_initialized)
215		_rs_stir();
216	while (datlen > 0) {
217		m = MIN(datlen, KEYSZ + IVSZ);
218		_rs_rekey(dat, m);
219		dat += m;
220		datlen -= m;
221	}
222	_ARC4_UNLOCK();
223}
224
225u_int32_t
226arc4random(void)
227{
228	u_int32_t val;
229
230	_ARC4_LOCK();
231	_rs_random_u32(&val);
232	_ARC4_UNLOCK();
233	return val;
234}
235
236/*
237 * If we are providing arc4random, then we can provide a more efficient
238 * arc4random_buf().
239 */
240# ifndef HAVE_ARC4RANDOM_BUF
241void
242arc4random_buf(void *buf, size_t n)
243{
244	_ARC4_LOCK();
245	_rs_random_buf(buf, n);
246	_ARC4_UNLOCK();
247}
248# endif /* !HAVE_ARC4RANDOM_BUF */
249#endif /* !HAVE_ARC4RANDOM */
250
251/* arc4random_buf() that uses platform arc4random() */
252#if !defined(HAVE_ARC4RANDOM_BUF) && defined(HAVE_ARC4RANDOM)
253void
254arc4random_buf(void *_buf, size_t n)
255{
256	size_t i;
257	u_int32_t r = 0;
258	char *buf = (char *)_buf;
259
260	for (i = 0; i < n; i++) {
261		if (i % 4 == 0)
262			r = arc4random();
263		buf[i] = r & 0xff;
264		r >>= 8;
265	}
266	explicit_bzero(&r, sizeof(r));
267}
268#endif /* !defined(HAVE_ARC4RANDOM_BUF) && defined(HAVE_ARC4RANDOM) */
269
270#ifndef HAVE_ARC4RANDOM_UNIFORM
271/*
272 * Calculate a uniformly distributed random number less than upper_bound
273 * avoiding "modulo bias".
274 *
275 * Uniformity is achieved by generating new random numbers until the one
276 * returned is outside the range [0, 2**32 % upper_bound).  This
277 * guarantees the selected random number will be inside
278 * [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound)
279 * after reduction modulo upper_bound.
280 */
281u_int32_t
282arc4random_uniform(u_int32_t upper_bound)
283{
284	u_int32_t r, min;
285
286	if (upper_bound < 2)
287		return 0;
288
289	/* 2**32 % x == (2**32 - x) % x */
290	min = -upper_bound % upper_bound;
291
292	/*
293	 * This could theoretically loop forever but each retry has
294	 * p > 0.5 (worst case, usually far better) of selecting a
295	 * number inside the range we need, so it should rarely need
296	 * to re-roll.
297	 */
298	for (;;) {
299		r = arc4random();
300		if (r >= min)
301			break;
302	}
303
304	return r % upper_bound;
305}
306#endif /* !HAVE_ARC4RANDOM_UNIFORM */
307
308#if 0
309/*-------- Test code for i386 --------*/
310#include <stdio.h>
311#include <machine/pctr.h>
312int
313main(int argc, char **argv)
314{
315	const int iter = 1000000;
316	int     i;
317	pctrval v;
318
319	v = rdtsc();
320	for (i = 0; i < iter; i++)
321		arc4random();
322	v = rdtsc() - v;
323	v /= iter;
324
325	printf("%qd cycles\n", v);
326	exit(0);
327}
328#endif
329