xref: /dragonfly/lib/libc/gen/arc4random.c (revision a68e0df0) 
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  * Here the stream cipher has been modified always to include the time
28  * when initializing the state.  That makes it impossible to
29  * regenerate the same random sequence twice, so this can't be used
30  * for encryption, but will generate good random numbers.
31  *
32  * RC4 is a registered trademark of RSA Laboratories.
33  *
34  * $FreeBSD: src/lib/libc/gen/arc4random.c,v 1.25 2008/09/09 09:46:36 ache Exp $
35  * $DragonFly: src/lib/libc/gen/arc4random.c,v 1.7 2005/11/13 00:07:42 swildner Exp $
36  */
37 
38 #include "namespace.h"
39 #include <sys/types.h>
40 #include <sys/time.h>
41 #include <stdlib.h>
42 #include <fcntl.h>
43 #include <unistd.h>
44 #include <pthread.h>
45 
46 #include "libc_private.h"
47 #include "un-namespace.h"
48 
49 struct arc4_stream {
50 	u_int8_t i;
51 	u_int8_t j;
52 	u_int8_t s[256];
53 };
54 
55 static pthread_mutex_t	arc4random_mtx = PTHREAD_MUTEX_INITIALIZER;
56 
57 #define	RANDOMDEV	"/dev/random"
58 #define KEYSIZE		128
59 #define	THREAD_LOCK()						\
60 	do {							\
61 		if (__isthreaded)				\
62 			_pthread_mutex_lock(&arc4random_mtx);	\
63 	} while (0)
64 
65 #define	THREAD_UNLOCK()						\
66 	do {							\
67 		if (__isthreaded)				\
68 			_pthread_mutex_unlock(&arc4random_mtx);	\
69 	} while (0)
70 
71 static struct arc4_stream rs;
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 < 256; 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 < 256; 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 static void
108 arc4_stir(void)
109 {
110 	int done, fd, n;
111 	struct {
112 		struct timeval	tv;
113 		pid_t 		pid;
114 		u_int8_t 	rnd[KEYSIZE];
115 	} rdat;
116 
117 	fd = _open(RANDOMDEV, O_RDONLY, 0);
118 	done = 0;
119 	if (fd >= 0) {
120 		if (_read(fd, &rdat, KEYSIZE) == KEYSIZE)
121 			done = 1;
122 		_close(fd);
123 	}
124 	if (!done) {
125 		gettimeofday(&rdat.tv, NULL);
126 		rdat.pid = getpid();
127 		/* We'll just take whatever was on the stack too... */
128 	}
129 
130 	arc4_addrandom((u_char *)&rdat, KEYSIZE);
131 
132 	/*
133 	 * Throw away the first N bytes of output, as suggested in the
134 	 * paper "Weaknesses in the Key Scheduling Algorithm of RC4"
135 	 * by Fluher, Mantin, and Shamir.  N=1024 is based on
136 	 * suggestions in the paper "(Not So) Random Shuffles of RC4"
137 	 * by Ilya Mironov.
138 	 */
139 	for (n = 0; n < 1024; n++)
140 		arc4_getbyte();
141 	arc4_count = 1600000;
142 }
143 
144 static u_int8_t
145 arc4_getbyte(void)
146 {
147 	u_int8_t si, sj;
148 
149 	rs.i = (rs.i + 1);
150 	si = rs.s[rs.i];
151 	rs.j = (rs.j + si);
152 	sj = rs.s[rs.j];
153 	rs.s[rs.i] = sj;
154 	rs.s[rs.j] = si;
155 
156 	return (rs.s[(si + sj) & 0xff]);
157 }
158 
159 static u_int32_t
160 arc4_getword(void)
161 {
162 	u_int32_t val;
163 
164 	val = arc4_getbyte() << 24;
165 	val |= arc4_getbyte() << 16;
166 	val |= arc4_getbyte() << 8;
167 	val |= arc4_getbyte();
168 
169 	return (val);
170 }
171 
172 static void
173 arc4_check_init(void)
174 {
175 	if (!rs_initialized) {
176 		arc4_init();
177 		rs_initialized = 1;
178 	}
179 }
180 
181 static inline void
182 arc4_check_stir(void)
183 {
184 	if (!rs_stired || arc4_count <= 0) {
185 		arc4_stir();
186 		rs_stired = 1;
187 	}
188 }
189 
190 void
191 arc4random_stir(void)
192 {
193 	THREAD_LOCK();
194 	arc4_check_init();
195 	arc4_stir();
196 	rs_stired = 1;
197 	THREAD_UNLOCK();
198 }
199 
200 void
201 arc4random_addrandom(uint8_t *dat, size_t datlen)
202 {
203 	THREAD_LOCK();
204 	arc4_check_init();
205 	arc4_check_stir();
206 	arc4_addrandom(dat, datlen);
207 	THREAD_UNLOCK();
208 }
209 
210 u_int32_t
211 arc4random(void)
212 {
213 	u_int32_t rnd;
214 
215 	THREAD_LOCK();
216 	arc4_check_init();
217 	arc4_check_stir();
218 	rnd = arc4_getword();
219 	arc4_count -= 4;
220 	THREAD_UNLOCK();
221 
222 	return (rnd);
223 }
224 
225 void
226 arc4random_buf(void *_buf, size_t n)
227 {
228 	u_char *buf = (u_char *)_buf;
229 
230 	THREAD_LOCK();
231 	arc4_check_init();
232 	while (n--) {
233 		arc4_check_stir();
234 		buf[n] = arc4_getbyte();
235 		arc4_count--;
236 	}
237 	THREAD_UNLOCK();
238 }
239 
240 /*
241  * Calculate a uniformly distributed random number less than upper_bound
242  * avoiding "modulo bias".
243  *
244  * Uniformity is achieved by generating new random numbers until the one
245  * returned is outside the range [0, 2**32 % upper_bound).  This
246  * guarantees the selected random number will be inside
247  * [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound)
248  * after reduction modulo upper_bound.
249  */
250 u_int32_t
251 arc4random_uniform(u_int32_t upper_bound)
252 {
253 	u_int32_t r, min;
254 
255 	if (upper_bound < 2)
256 		return (0);
257 
258 #if (ULONG_MAX > 0xffffffffUL)
259 	min = 0x100000000UL % upper_bound;
260 #else
261 	/* Calculate (2**32 % upper_bound) avoiding 64-bit math */
262 	if (upper_bound > 0x80000000)
263 		min = 1 + ~upper_bound;		/* 2**32 - upper_bound */
264 	else {
265 		/* (2**32 - (x * 2)) % x == 2**32 % x when x <= 2**31 */
266 		min = ((0xffffffff - (upper_bound * 2)) + 1) % upper_bound;
267 	}
268 #endif
269 
270 	/*
271 	 * This could theoretically loop forever but each retry has
272 	 * p > 0.5 (worst case, usually far better) of selecting a
273 	 * number inside the range we need, so it should rarely need
274 	 * to re-roll.
275 	 */
276 	for (;;) {
277 		r = arc4random();
278 		if (r >= min)
279 			break;
280 	}
281 
282 	return (r % upper_bound);
283 }
284 
285 #if 0
286 /*-------- Test code for i386 --------*/
287 #include <stdio.h>
288 #include <machine/pctr.h>
289 int
290 main(int argc, char **argv)
291 {
292 	const int iter = 1000000;
293 	int     i;
294 	pctrval v;
295 
296 	v = rdtsc();
297 	for (i = 0; i < iter; i++)
298 		arc4random();
299 	v = rdtsc() - v;
300 	v /= iter;
301 
302 	printf("%qd cycles\n", v);
303 }
304 #endif
305