xref: /dragonfly/lib/libc/gen/arc4random.c (revision 092c2dd1) 
1 /*
2  * Copyright (c) 1996, David Mazieres <dm@uun.org>
3  * Copyright (c) 2008, Damien Miller <djm@openbsd.org>
4  *
5  * Permission to use, copy, modify, and distribute this software for any
6  * purpose with or without fee is hereby granted, provided that the above
7  * copyright notice and this permission notice appear in all copies.
8  *
9  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
10  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
11  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
12  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
13  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
14  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
15  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
16  */
17 
18 /*
19  * Arc4 random number generator for OpenBSD.
20  *
21  * This code is derived from section 17.1 of Applied Cryptography,
22  * second edition, which describes a stream cipher allegedly
23  * compatible with RSA Labs "RC4" cipher (the actual description of
24  * which is a trade secret).  The same algorithm is used as a stream
25  * cipher called "arcfour" in Tatu Ylonen's ssh package.
26  *
27  * RC4 is a registered trademark of RSA Laboratories.
28  *
29  * $OpenBSD: arc4random.c,v 1.24 2013/06/11 16:59:50 deraadt Exp $
30  * $FreeBSD: src/lib/libc/gen/arc4random.c,v 1.25 2008/09/09 09:46:36 ache Exp $
31  */
32 
33 #include "namespace.h"
34 #include <sys/types.h>
35 #include <sys/time.h>
36 #include <sys/sysctl.h>
37 #include <stdlib.h>
38 #include <fcntl.h>
39 #include <unistd.h>
40 #include <pthread.h>
41 
42 #include "libc_private.h"
43 #include "un-namespace.h"
44 
45 /*
46  * Misc constants
47  */
48 #define	RANDOMDEV	"/dev/random"
49 #define	KEYSIZE		128
50 #define	_ARC4_LOCK()						\
51 	do {							\
52 		if (__isthreaded)				\
53 			_pthread_mutex_lock(&arc4random_mtx);	\
54 	} while (0)
55 
56 #define	_ARC4_UNLOCK()						\
57 	do {							\
58 		if (__isthreaded)				\
59 			_pthread_mutex_unlock(&arc4random_mtx);	\
60 	} while (0)
61 
62 struct arc4_stream {
63 	u_int8_t i;
64 	u_int8_t j;
65 	u_int8_t s[KEYSIZE * 2];
66 };
67 
68 static pthread_mutex_t	arc4random_mtx = PTHREAD_MUTEX_INITIALIZER;
69 
70 static struct arc4_stream rs;
71 static pid_t arc4_stir_pid;
72 static int rs_initialized;
73 static int rs_stired;
74 static int arc4_count;
75 
76 static u_int8_t arc4_getbyte(void);
77 static void arc4_stir(void);
78 
79 static inline void
80 arc4_init(void)
81 {
82 	int     n;
83 
84 	for (n = 0; n < KEYSIZE * 2; n++)
85 		rs.s[n] = n;
86 	rs.i = 0;
87 	rs.j = 0;
88 }
89 
90 static inline void
91 arc4_addrandom(u_char *dat, size_t datlen)
92 {
93 	size_t n;
94 	u_int8_t si;
95 
96 	rs.i--;
97 	for (n = 0; n < KEYSIZE * 2; n++) {
98 		rs.i = (rs.i + 1);
99 		si = rs.s[rs.i];
100 		rs.j = (rs.j + si + dat[n % datlen]);
101 		rs.s[rs.i] = rs.s[rs.j];
102 		rs.s[rs.j] = si;
103 	}
104 	rs.j = rs.i;
105 }
106 
107 struct pray {
108 	struct timeval	tv;
109 	pid_t		pid;
110 };
111 
112 static void
113 arc4_stir(void)
114 {
115 	u_int8_t rnd[KEYSIZE*2];
116 	size_t n;
117 	int fd;
118 
119 	/*
120 	 * NOTE: Don't assume that the garbage on the stack is actually
121 	 *	 random.
122 	 */
123 	n = 0;
124 	fd = _open(RANDOMDEV, O_RDONLY | O_CLOEXEC, 0);
125 	if (fd >= 0) {
126 		n = _read(fd, rnd, sizeof(rnd));
127 		_close(fd);
128 		if ((ssize_t)n < 0)
129 			n = 0;
130 	}
131 
132 	/*
133 	 * Align for added entropy, sysctl back-off for chroots that might
134 	 * not have access to /dev/random.
135 	 */
136 	n = n & ~15;	/* align for added entropy */
137 	if (n < sizeof(rnd)) {
138 		size_t r = sizeof(rnd) - n;
139 		if (sysctlbyname("kern.random", rnd + n, &r, NULL, 0) == 0)
140 			n += r;
141 	}
142 
143 	/*
144 	 * Pray if this code ever gets triggered.
145 	 */
146 	n = n & ~15;
147 	if (n <= sizeof(rnd) - sizeof(struct pray)) {
148 		struct pray *pray = (void *)(rnd + n);
149 		gettimeofday(&pray->tv, NULL);
150 		pray->pid = getpid();
151 		n += sizeof(struct pray);
152 	}
153 	arc4_addrandom((u_char *)rnd, n);
154 
155 	/*
156 	 * Discard early keystream, as per recommendations in:
157 	 * "(Not So) Random Shuffles of RC4" by Ilya Mironov.
158 	 */
159 	for (n = 0; n < 3072; n++)
160 		arc4_getbyte();
161 
162 	/*
163 	 * Theoretically we can set arc4_count to 1600000.  Realistically,
164 	 * it makes no sense to use a number that high.  Use something
165 	 * reasonable.
166 	 */
167 	arc4_count = 65539;
168 }
169 
170 static u_int8_t
171 arc4_getbyte(void)
172 {
173 	u_int8_t si, sj;
174 
175 	rs.i = (rs.i + 1);
176 	si = rs.s[rs.i];
177 	rs.j = (rs.j + si);
178 	sj = rs.s[rs.j];
179 	rs.s[rs.i] = sj;
180 	rs.s[rs.j] = si;
181 
182 	return (rs.s[(si + sj) & 0xff]);
183 }
184 
185 static u_int32_t
186 arc4_getword(void)
187 {
188 	u_int32_t val;
189 
190 	val = arc4_getbyte() << 24;
191 	val |= arc4_getbyte() << 16;
192 	val |= arc4_getbyte() << 8;
193 	val |= arc4_getbyte();
194 
195 	return (val);
196 }
197 
198 static void
199 arc4_check_init(void)
200 {
201 	if (!rs_initialized) {
202 		arc4_init();
203 		rs_initialized = 1;
204 	}
205 }
206 
207 static inline void
208 arc4_check_stir(void)
209 {
210 	pid_t pid = getpid();	/* optimized by upmap */
211 
212 	if (!rs_stired || arc4_count <= 0 || arc4_stir_pid != pid) {
213 		arc4_stir_pid = pid;
214 		arc4_stir();
215 		rs_stired = 1;
216 	}
217 }
218 
219 void
220 arc4random_stir(void)
221 {
222 	_ARC4_LOCK();
223 	arc4_check_init();
224 	arc4_stir();
225 	rs_stired = 1;
226 	_ARC4_UNLOCK();
227 }
228 
229 void
230 arc4random_addrandom(uint8_t *dat, size_t datlen)
231 {
232 	_ARC4_LOCK();
233 	arc4_check_init();
234 	arc4_check_stir();
235 	arc4_addrandom(dat, datlen);
236 	_ARC4_UNLOCK();
237 }
238 
239 u_int32_t
240 arc4random(void)
241 {
242 	u_int32_t rnd;
243 
244 	_ARC4_LOCK();
245 	arc4_check_init();
246 	arc4_check_stir();
247 	rnd = arc4_getword();
248 	arc4_count -= 4;
249 	_ARC4_UNLOCK();
250 
251 	return (rnd);
252 }
253 
254 void
255 arc4random_buf(void *_buf, size_t n)
256 {
257 	u_char *buf = (u_char *)_buf;
258 
259 	_ARC4_LOCK();
260 	arc4_check_init();
261 	while (n--) {
262 		arc4_check_stir();
263 		buf[n] = arc4_getbyte();
264 		arc4_count--;
265 	}
266 	_ARC4_UNLOCK();
267 }
268 
269 /*
270  * Calculate a uniformly distributed random number less than upper_bound
271  * avoiding "modulo bias".
272  *
273  * Uniformity is achieved by generating new random numbers until the one
274  * returned is outside the range [0, 2**32 % upper_bound).  This
275  * guarantees the selected random number will be inside
276  * [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound)
277  * after reduction modulo upper_bound.
278  */
279 u_int32_t
280 arc4random_uniform(u_int32_t upper_bound)
281 {
282 	u_int32_t r, min;
283 
284 	if (upper_bound < 2)
285 		return 0;
286 
287 	/* 2**32 % x == (2**32 - x) % x */
288 	min = -upper_bound % upper_bound;
289 	/*
290 	 * This could theoretically loop forever but each retry has
291 	 * p > 0.5 (worst case, usually far better) of selecting a
292 	 * number inside the range we need, so it should rarely need
293 	 * to re-roll.
294 	 */
295 	for (;;) {
296 		r = arc4random();
297 		if (r >= min)
298 			break;
299 	}
300 
301 	return (r % upper_bound);
302 }
303 
304 #if 0
305 /*-------- Test code for i386 --------*/
306 #include <stdio.h>
307 #include <machine/pctr.h>
308 int
309 main(int argc, char **argv)
310 {
311 	const int iter = 1000000;
312 	int     i;
313 	pctrval v;
314 
315 	v = rdtsc();
316 	for (i = 0; i < iter; i++)
317 		arc4random();
318 	v = rdtsc() - v;
319 	v /= iter;
320 
321 	printf("%qd cycles\n", v);
322 }
323 #endif
324