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)
66 static int rs_initialized;
67 static pid_t rs_stir_pid;
68 static chacha_ctx rs;		/* chacha context for random keystream */
69 static u_char rs_buf[RSBUFSZ];	/* keystream blocks */
70 static size_t rs_have;		/* valid bytes at end of rs_buf */
71 static size_t rs_count;		/* bytes till reseed */
72 
73 static inline void _rs_rekey(u_char *dat, size_t datlen);
74 
75 static inline void
_rs_init(u_char * buf,size_t n)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 */
88 static void
getrnd(u_char * s,size_t len)89 getrnd(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 
116 static void
_rs_stir(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 
143 static inline void
_rs_stir_if_needed(size_t len)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 
155 static inline void
_rs_rekey(u_char * dat,size_t datlen)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 
177 static inline void
_rs_random_buf(void * _buf,size_t n)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 
198 static inline void
_rs_random_u32(u_int32_t * val)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 
210 void
arc4random_stir(void)211 arc4random_stir(void)
212 {
213 	_ARC4_LOCK();
214 	_rs_stir();
215 	_ARC4_UNLOCK();
216 }
217 
218 void
arc4random_addrandom(u_char * dat,int datlen)219 arc4random_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 
235 u_int32_t
arc4random(void)236 arc4random(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
251 void
arc4random_buf(void * buf,size_t n)252 arc4random_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)
263 void
arc4random_buf(void * _buf,size_t n)264 arc4random_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  */
291 u_int32_t
arc4random_uniform(u_int32_t upper_bound)292 arc4random_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>
322 int
323 main(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