xref: /dragonfly/lib/libc/gen/arc4random.c (revision 6ab64ab6) 
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 	 * Throw away the first N bytes of output, as suggested in the
157 	 * paper "Weaknesses in the Key Scheduling Algorithm of RC4"
158 	 * by Fluher, Mantin, and Shamir.  N=1024 is based on
159 	 * suggestions in the paper "(Not So) Random Shuffles of RC4"
160 	 * by Ilya Mironov.
161 	 */
162 	for (n = 0; n < 1024; n++)
163 		arc4_getbyte();
164 
165 	/*
166 	 * Theoretically we can set arc4_count to 1600000.  Realistically,
167 	 * it makes no sense to use a number that high.  Use something
168 	 * reasonable.
169 	 */
170 	arc4_count = 65539;
171 }
172 
173 static u_int8_t
174 arc4_getbyte(void)
175 {
176 	u_int8_t si, sj;
177 
178 	rs.i = (rs.i + 1);
179 	si = rs.s[rs.i];
180 	rs.j = (rs.j + si);
181 	sj = rs.s[rs.j];
182 	rs.s[rs.i] = sj;
183 	rs.s[rs.j] = si;
184 
185 	return (rs.s[(si + sj) & 0xff]);
186 }
187 
188 static u_int32_t
189 arc4_getword(void)
190 {
191 	u_int32_t val;
192 
193 	val = arc4_getbyte() << 24;
194 	val |= arc4_getbyte() << 16;
195 	val |= arc4_getbyte() << 8;
196 	val |= arc4_getbyte();
197 
198 	return (val);
199 }
200 
201 static void
202 arc4_check_init(void)
203 {
204 	if (!rs_initialized) {
205 		arc4_init();
206 		rs_initialized = 1;
207 	}
208 }
209 
210 static inline void
211 arc4_check_stir(void)
212 {
213 	pid_t pid = getpid();	/* optimized by upmap */
214 
215 	if (!rs_stired || arc4_count <= 0 || arc4_stir_pid != pid) {
216 		arc4_stir_pid = pid;
217 		arc4_stir();
218 		rs_stired = 1;
219 	}
220 }
221 
222 void
223 arc4random_stir(void)
224 {
225 	_ARC4_LOCK();
226 	arc4_check_init();
227 	arc4_stir();
228 	rs_stired = 1;
229 	_ARC4_UNLOCK();
230 }
231 
232 void
233 arc4random_addrandom(uint8_t *dat, size_t datlen)
234 {
235 	_ARC4_LOCK();
236 	arc4_check_init();
237 	arc4_check_stir();
238 	arc4_addrandom(dat, datlen);
239 	_ARC4_UNLOCK();
240 }
241 
242 u_int32_t
243 arc4random(void)
244 {
245 	u_int32_t rnd;
246 
247 	_ARC4_LOCK();
248 	arc4_check_init();
249 	arc4_check_stir();
250 	rnd = arc4_getword();
251 	arc4_count -= 4;
252 	_ARC4_UNLOCK();
253 
254 	return (rnd);
255 }
256 
257 void
258 arc4random_buf(void *_buf, size_t n)
259 {
260 	u_char *buf = (u_char *)_buf;
261 
262 	_ARC4_LOCK();
263 	arc4_check_init();
264 	while (n--) {
265 		arc4_check_stir();
266 		buf[n] = arc4_getbyte();
267 		arc4_count--;
268 	}
269 	_ARC4_UNLOCK();
270 }
271 
272 /*
273  * Calculate a uniformly distributed random number less than upper_bound
274  * avoiding "modulo bias".
275  *
276  * Uniformity is achieved by generating new random numbers until the one
277  * returned is outside the range [0, 2**32 % upper_bound).  This
278  * guarantees the selected random number will be inside
279  * [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound)
280  * after reduction modulo upper_bound.
281  */
282 u_int32_t
283 arc4random_uniform(u_int32_t upper_bound)
284 {
285 	u_int32_t r, min;
286 
287 	if (upper_bound < 2)
288 		return 0;
289 
290 	/* 2**32 % x == (2**32 - x) % x */
291 	min = -upper_bound % upper_bound;
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 
307 #if 0
308 /*-------- Test code for i386 --------*/
309 #include <stdio.h>
310 #include <machine/pctr.h>
311 int
312 main(int argc, char **argv)
313 {
314 	const int iter = 1000000;
315 	int     i;
316 	pctrval v;
317 
318 	v = rdtsc();
319 	for (i = 0; i < iter; i++)
320 		arc4random();
321 	v = rdtsc() - v;
322 	v /= iter;
323 
324 	printf("%qd cycles\n", v);
325 }
326 #endif
327