xref: /freebsd/lib/libc/gen/arc4random.c (revision ba00ec3d539f213abbda3a45ef8c539306cac098)
1 /*	$OpenBSD: arc4random.c,v 1.22 2010/12/22 08:23:42 otto 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/types.h>
41 #include <sys/param.h>
42 #include <sys/sysctl.h>
43 #include <sys/time.h>
44 #include <pthread.h>
45 
46 #include "libc_private.h"
47 #include "un-namespace.h"
48 
49 #ifdef __GNUC__
50 #define inline __inline
51 #else				/* !__GNUC__ */
52 #define inline
53 #endif				/* !__GNUC__ */
54 
55 struct arc4_stream {
56 	u_int8_t i;
57 	u_int8_t j;
58 	u_int8_t s[256];
59 };
60 
61 static pthread_mutex_t	arc4random_mtx = PTHREAD_MUTEX_INITIALIZER;
62 
63 #define	RANDOMDEV	"/dev/random"
64 #define	KEYSIZE		128
65 #define	_ARC4_LOCK()						\
66 	do {							\
67 		if (__isthreaded)				\
68 			_pthread_mutex_lock(&arc4random_mtx);	\
69 	} while (0)
70 
71 #define	_ARC4_UNLOCK()						\
72 	do {							\
73 		if (__isthreaded)				\
74 			_pthread_mutex_unlock(&arc4random_mtx);	\
75 	} while (0)
76 
77 static int rs_initialized;
78 static struct arc4_stream rs;
79 static pid_t arc4_stir_pid;
80 static int arc4_count;
81 
82 extern int __sysctl(int *name, u_int namelen, void *oldp, size_t *oldlenp,
83     void *newp, size_t newlen);
84 
85 static inline u_int8_t arc4_getbyte(void);
86 static void arc4_stir(void);
87 
88 static inline void
89 arc4_init(void)
90 {
91 	int     n;
92 
93 	for (n = 0; n < 256; n++)
94 		rs.s[n] = n;
95 	rs.i = 0;
96 	rs.j = 0;
97 }
98 
99 static inline void
100 arc4_addrandom(u_char *dat, int datlen)
101 {
102 	int     n;
103 	u_int8_t si;
104 
105 	rs.i--;
106 	for (n = 0; n < 256; n++) {
107 		rs.i = (rs.i + 1);
108 		si = rs.s[rs.i];
109 		rs.j = (rs.j + si + dat[n % datlen]);
110 		rs.s[rs.i] = rs.s[rs.j];
111 		rs.s[rs.j] = si;
112 	}
113 	rs.j = rs.i;
114 }
115 
116 static size_t
117 arc4_sysctl(u_char *buf, size_t size)
118 {
119 	int mib[2];
120 	size_t len, done;
121 
122 	mib[0] = CTL_KERN;
123 	mib[1] = KERN_ARND;
124 	done = 0;
125 
126 	do {
127 		len = size;
128 		if (__sysctl(mib, 2, buf, &len, NULL, 0) == -1)
129 			return (done);
130 		done += len;
131 		buf += len;
132 		size -= len;
133 	} while (size > 0);
134 
135 	return (done);
136 }
137 
138 static void
139 arc4_stir(void)
140 {
141 	int done, fd, i;
142 	struct {
143 		struct timeval	tv;
144 		pid_t		pid;
145 		u_char	 	rnd[KEYSIZE];
146 	} rdat;
147 
148 	if (!rs_initialized) {
149 		arc4_init();
150 		rs_initialized = 1;
151 	}
152 	done = 0;
153 	if (arc4_sysctl((u_char *)&rdat, KEYSIZE) == KEYSIZE)
154 		done = 1;
155 	if (!done) {
156 		fd = _open(RANDOMDEV, O_RDONLY | O_CLOEXEC, 0);
157 		if (fd >= 0) {
158 			if (_read(fd, &rdat, KEYSIZE) == KEYSIZE)
159 				done = 1;
160 			(void)_close(fd);
161 		}
162 	}
163 	if (!done) {
164 		(void)gettimeofday(&rdat.tv, NULL);
165 		rdat.pid = getpid();
166 		/* We'll just take whatever was on the stack too... */
167 	}
168 
169 	arc4_addrandom((u_char *)&rdat, KEYSIZE);
170 
171 	/*
172 	 * Discard early keystream, as per recommendations in:
173 	 * "(Not So) Random Shuffles of RC4" by Ilya Mironov.
174 	 */
175 	for (i = 0; i < 1024; i++)
176 		(void)arc4_getbyte();
177 	arc4_count = 1600000;
178 }
179 
180 static void
181 arc4_stir_if_needed(void)
182 {
183 	pid_t pid = getpid();
184 
185 	if (arc4_count <= 0 || !rs_initialized || arc4_stir_pid != pid)
186 	{
187 		arc4_stir_pid = pid;
188 		arc4_stir();
189 	}
190 }
191 
192 static inline u_int8_t
193 arc4_getbyte(void)
194 {
195 	u_int8_t si, sj;
196 
197 	rs.i = (rs.i + 1);
198 	si = rs.s[rs.i];
199 	rs.j = (rs.j + si);
200 	sj = rs.s[rs.j];
201 	rs.s[rs.i] = sj;
202 	rs.s[rs.j] = si;
203 	return (rs.s[(si + sj) & 0xff]);
204 }
205 
206 static inline u_int32_t
207 arc4_getword(void)
208 {
209 	u_int32_t val;
210 	val = arc4_getbyte() << 24;
211 	val |= arc4_getbyte() << 16;
212 	val |= arc4_getbyte() << 8;
213 	val |= arc4_getbyte();
214 	return val;
215 }
216 
217 void
218 arc4random_stir(void)
219 {
220 	_ARC4_LOCK();
221 	arc4_stir();
222 	_ARC4_UNLOCK();
223 }
224 
225 void
226 arc4random_addrandom(u_char *dat, int datlen)
227 {
228 	_ARC4_LOCK();
229 	if (!rs_initialized)
230 		arc4_stir();
231 	arc4_addrandom(dat, datlen);
232 	_ARC4_UNLOCK();
233 }
234 
235 u_int32_t
236 arc4random(void)
237 {
238 	u_int32_t val;
239 	_ARC4_LOCK();
240 	arc4_count -= 4;
241 	arc4_stir_if_needed();
242 	val = arc4_getword();
243 	_ARC4_UNLOCK();
244 	return val;
245 }
246 
247 void
248 arc4random_buf(void *_buf, size_t n)
249 {
250 	u_char *buf = (u_char *)_buf;
251 	_ARC4_LOCK();
252 	arc4_stir_if_needed();
253 	while (n--) {
254 		if (--arc4_count <= 0)
255 			arc4_stir();
256 		buf[n] = arc4_getbyte();
257 	}
258 	_ARC4_UNLOCK();
259 }
260 
261 /*
262  * Calculate a uniformly distributed random number less than upper_bound
263  * avoiding "modulo bias".
264  *
265  * Uniformity is achieved by generating new random numbers until the one
266  * returned is outside the range [0, 2**32 % upper_bound).  This
267  * guarantees the selected random number will be inside
268  * [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound)
269  * after reduction modulo upper_bound.
270  */
271 u_int32_t
272 arc4random_uniform(u_int32_t upper_bound)
273 {
274 	u_int32_t r, min;
275 
276 	if (upper_bound < 2)
277 		return 0;
278 
279 #if (ULONG_MAX > 0xffffffffUL)
280 	min = 0x100000000UL % upper_bound;
281 #else
282 	/* Calculate (2**32 % upper_bound) avoiding 64-bit math */
283 	if (upper_bound > 0x80000000)
284 		min = 1 + ~upper_bound;		/* 2**32 - upper_bound */
285 	else {
286 		/* (2**32 - (x * 2)) % x == 2**32 % x when x <= 2**31 */
287 		min = ((0xffffffff - (upper_bound * 2)) + 1) % upper_bound;
288 	}
289 #endif
290 
291 	/*
292 	 * This could theoretically loop forever but each retry has
293 	 * p > 0.5 (worst case, usually far better) of selecting a
294 	 * number inside the range we need, so it should rarely need
295 	 * to re-roll.
296 	 */
297 	for (;;) {
298 		r = arc4random();
299 		if (r >= min)
300 			break;
301 	}
302 
303 	return r % upper_bound;
304 }
305 
306 #if 0
307 /*-------- Test code for i386 --------*/
308 #include <stdio.h>
309 #include <machine/pctr.h>
310 int
311 main(int argc, char **argv)
312 {
313 	const int iter = 1000000;
314 	int     i;
315 	pctrval v;
316 
317 	v = rdtsc();
318 	for (i = 0; i < iter; i++)
319 		arc4random();
320 	v = rdtsc() - v;
321 	v /= iter;
322 
323 	printf("%qd cycles\n", v);
324 }
325 #endif
326