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