xref: /dflybsd-src/lib/libc/gen/arc4random.c (revision e5e174adcc2678e90a7ffbe469dfe34d9989aa09) 
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 int rs_initialized;
72 static int rs_stired;
73 static int arc4_count;
74 
75 static u_int8_t arc4_getbyte(void);
76 static void arc4_stir(void);
77 
78 static inline void
79 arc4_init(void)
80 {
81 	int     n;
82 
83 	for (n = 0; n < KEYSIZE * 2; n++)
84 		rs.s[n] = n;
85 	rs.i = 0;
86 	rs.j = 0;
87 }
88 
89 static inline void
90 arc4_addrandom(u_char *dat, size_t datlen)
91 {
92 	size_t n;
93 	u_int8_t si;
94 
95 	rs.i--;
96 	for (n = 0; n < KEYSIZE * 2; n++) {
97 		rs.i = (rs.i + 1);
98 		si = rs.s[rs.i];
99 		rs.j = (rs.j + si + dat[n % datlen]);
100 		rs.s[rs.i] = rs.s[rs.j];
101 		rs.s[rs.j] = si;
102 	}
103 	rs.j = rs.i;
104 }
105 
106 struct pray {
107 	struct timeval	tv;
108 	pid_t		pid;
109 };
110 
111 static void
112 arc4_stir(void)
113 {
114 	u_int8_t rnd[KEYSIZE*2];
115 	size_t n;
116 	int fd;
117 
118 	/*
119 	 * NOTE: Don't assume that the garbage on the stack is actually
120 	 *	 random.
121 	 */
122 	n = 0;
123 	fd = _open(RANDOMDEV, O_RDONLY | O_CLOEXEC, 0);
124 	if (fd >= 0) {
125 		n = _read(fd, rnd, sizeof(rnd));
126 		_close(fd);
127 		if ((ssize_t)n < 0)
128 			n = 0;
129 	}
130 
131 	/*
132 	 * Align for added entropy, sysctl back-off for chroots that might
133 	 * not have access to /dev/random.
134 	 */
135 	n = n & ~15;	/* align for added entropy */
136 	if (n < sizeof(rnd)) {
137 		size_t r = sizeof(rnd) - n;
138 		if (sysctlbyname("kern.random", rnd + n, &r, NULL, 0) == 0)
139 			n += r;
140 	}
141 
142 	/*
143 	 * Pray if this code ever gets triggered.
144 	 */
145 	n = n & ~15;
146 	if (n <= sizeof(rnd) - sizeof(struct pray)) {
147 		struct pray *pray = (void *)(rnd + n);
148 		gettimeofday(&pray->tv, NULL);
149 		pray->pid = getpid();
150 		n += sizeof(struct pray);
151 	}
152 	arc4_addrandom((u_char *)rnd, n);
153 
154 	/*
155 	 * Throw away the first N bytes of output, as suggested in the
156 	 * paper "Weaknesses in the Key Scheduling Algorithm of RC4"
157 	 * by Fluher, Mantin, and Shamir.  N=1024 is based on
158 	 * suggestions in the paper "(Not So) Random Shuffles of RC4"
159 	 * by Ilya Mironov.
160 	 */
161 	for (n = 0; n < 1024; n++)
162 		arc4_getbyte();
163 
164 	/*
165 	 * Theoretically we can set arc4_count to 1600000.  Realistically,
166 	 * it makes no sense to use a number that high.  Use something
167 	 * reasonable.
168 	 */
169 	arc4_count = 65539;
170 }
171 
172 static u_int8_t
173 arc4_getbyte(void)
174 {
175 	u_int8_t si, sj;
176 
177 	rs.i = (rs.i + 1);
178 	si = rs.s[rs.i];
179 	rs.j = (rs.j + si);
180 	sj = rs.s[rs.j];
181 	rs.s[rs.i] = sj;
182 	rs.s[rs.j] = si;
183 
184 	return (rs.s[(si + sj) & 0xff]);
185 }
186 
187 static u_int32_t
188 arc4_getword(void)
189 {
190 	u_int32_t val;
191 
192 	val = arc4_getbyte() << 24;
193 	val |= arc4_getbyte() << 16;
194 	val |= arc4_getbyte() << 8;
195 	val |= arc4_getbyte();
196 
197 	return (val);
198 }
199 
200 static void
201 arc4_check_init(void)
202 {
203 	if (!rs_initialized) {
204 		arc4_init();
205 		rs_initialized = 1;
206 	}
207 }
208 
209 static inline void
210 arc4_check_stir(void)
211 {
212 	if (!rs_stired || arc4_count <= 0) {
213 		arc4_stir();
214 		rs_stired = 1;
215 	}
216 }
217 
218 void
219 arc4random_stir(void)
220 {
221 	_ARC4_LOCK();
222 	arc4_check_init();
223 	arc4_stir();
224 	rs_stired = 1;
225 	_ARC4_UNLOCK();
226 }
227 
228 void
229 arc4random_addrandom(uint8_t *dat, size_t datlen)
230 {
231 	_ARC4_LOCK();
232 	arc4_check_init();
233 	arc4_check_stir();
234 	arc4_addrandom(dat, datlen);
235 	_ARC4_UNLOCK();
236 }
237 
238 u_int32_t
239 arc4random(void)
240 {
241 	u_int32_t rnd;
242 
243 	_ARC4_LOCK();
244 	arc4_check_init();
245 	arc4_check_stir();
246 	rnd = arc4_getword();
247 	arc4_count -= 4;
248 	_ARC4_UNLOCK();
249 
250 	return (rnd);
251 }
252 
253 void
254 arc4random_buf(void *_buf, size_t n)
255 {
256 	u_char *buf = (u_char *)_buf;
257 
258 	_ARC4_LOCK();
259 	arc4_check_init();
260 	while (n--) {
261 		arc4_check_stir();
262 		buf[n] = arc4_getbyte();
263 		arc4_count--;
264 	}
265 	_ARC4_UNLOCK();
266 }
267 
268 /*
269  * Calculate a uniformly distributed random number less than upper_bound
270  * avoiding "modulo bias".
271  *
272  * Uniformity is achieved by generating new random numbers until the one
273  * returned is outside the range [0, 2**32 % upper_bound).  This
274  * guarantees the selected random number will be inside
275  * [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound)
276  * after reduction modulo upper_bound.
277  */
278 u_int32_t
279 arc4random_uniform(u_int32_t upper_bound)
280 {
281 	u_int32_t r, min;
282 
283 	if (upper_bound < 2)
284 		return 0;
285 
286 	/* 2**32 % x == (2**32 - x) % x */
287 	min = -upper_bound % upper_bound;
288 	/*
289 	 * This could theoretically loop forever but each retry has
290 	 * p > 0.5 (worst case, usually far better) of selecting a
291 	 * number inside the range we need, so it should rarely need
292 	 * to re-roll.
293 	 */
294 	for (;;) {
295 		r = arc4random();
296 		if (r >= min)
297 			break;
298 	}
299 
300 	return (r % upper_bound);
301 }
302 
303 #if 0
304 /*-------- Test code for i386 --------*/
305 #include <stdio.h>
306 #include <machine/pctr.h>
307 int
308 main(int argc, char **argv)
309 {
310 	const int iter = 1000000;
311 	int     i;
312 	pctrval v;
313 
314 	v = rdtsc();
315 	for (i = 0; i < iter; i++)
316 		arc4random();
317 	v = rdtsc() - v;
318 	v /= iter;
319 
320 	printf("%qd cycles\n", v);
321 }
322 #endif
323