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