1 /* $OpenBSD: arc4random.c,v 1.19 2008/06/04 00:50:23 djm 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 * Here the stream cipher has been modified always to include the time
30 * when initializing the state. That makes it impossible to
31 * regenerate the same random sequence twice, so this can't be used
32 * for encryption, but will generate good random numbers.
33 *
34 * RC4 is a registered trademark of RSA Laboratories.
35 */
36
37 #include <fcntl.h>
38 #include <limits.h>
39 #include <stdlib.h>
40 #include <unistd.h>
41 #include <sys/types.h>
42 #include <sys/param.h>
43 #include <sys/time.h>
44 #include "thread_private.h"
45
46 /* BIONIC-BEGIN */
47 /* this lock should protect the global variables in this file */
48 static pthread_mutex_t _arc4_lock = PTHREAD_MUTEX_INITIALIZER;
49 #define _ARC4_LOCK() pthread_mutex_lock(&_arc4_lock)
50 #define _ARC4_UNLOCK() pthread_mutex_unlock(&_arc4_lock)
51 /* BIONIC-END */
52
53 #ifdef __GNUC__
54 #define inline __inline
55 #else /* !__GNUC__ */
56 #define inline
57 #endif /* !__GNUC__ */
58
59 struct arc4_stream {
60 u_int8_t i;
61 u_int8_t j;
62 u_int8_t s[256];
63 };
64
65 static int rs_initialized;
66 static struct arc4_stream rs;
67 static pid_t arc4_stir_pid;
68 static int arc4_count;
69
70 static inline u_int8_t arc4_getbyte(void);
71
72 static inline void
arc4_init(void)73 arc4_init(void)
74 {
75 int n;
76
77 for (n = 0; n < 256; n++)
78 rs.s[n] = n;
79 rs.i = 0;
80 rs.j = 0;
81 }
82
83 static inline void
arc4_addrandom(u_char * dat,int datlen)84 arc4_addrandom(u_char *dat, int datlen)
85 {
86 int n;
87 u_int8_t si;
88
89 rs.i--;
90 for (n = 0; n < 256; n++) {
91 rs.i = (rs.i + 1);
92 si = rs.s[rs.i];
93 rs.j = (rs.j + si + dat[n % datlen]);
94 rs.s[rs.i] = rs.s[rs.j];
95 rs.s[rs.j] = si;
96 }
97 rs.j = rs.i;
98 }
99
100 static void
arc4_stir(void)101 arc4_stir(void)
102 {
103 #if 1 /* BIONIC-BEGIN */
104 int i, fd;
105 union {
106 struct timeval tv;
107 u_int rnd[128 / sizeof(u_int)];
108 } rdat;
109 int n;
110
111 if (!rs_initialized) {
112 arc4_init();
113 rs_initialized = 1;
114 }
115
116 fd = open("/dev/urandom", O_RDONLY);
117 if (fd != -1) {
118 read(fd, rdat.rnd, sizeof(rdat.rnd));
119 close(fd);
120 }
121 else
122 {
123 /* fd < 0 ? Ah, what the heck. We'll just take
124 * whatever was on the stack. just add a little more
125 * time-based randomness though
126 */
127 gettimeofday(&rdat.tv, NULL);
128 }
129
130 arc4_stir_pid = getpid();
131 arc4_addrandom((void *) &rdat, sizeof(rdat));
132 #else /* BIONIC-END */
133 int i, mib[2];
134 size_t len;
135 u_char rnd[128];
136
137 if (!rs_initialized) {
138 arc4_init();
139 rs_initialized = 1;
140 }
141
142 mib[0] = CTL_KERN;
143 mib[1] = KERN_ARND;
144
145 len = sizeof(rnd);
146 sysctl(mib, 2, rnd, &len, NULL, 0);
147
148 arc4_stir_pid = getpid();
149 arc4_addrandom(rnd, sizeof(rnd));
150 #endif
151 /*
152 * Discard early keystream, as per recommendations in:
153 * http://www.wisdom.weizmann.ac.il/~itsik/RC4/Papers/Rc4_ksa.ps
154 */
155 for (i = 0; i < 256; i++)
156 (void)arc4_getbyte();
157 arc4_count = 1600000;
158 }
159
160 static inline u_int8_t
arc4_getbyte(void)161 arc4_getbyte(void)
162 {
163 u_int8_t si, sj;
164
165 rs.i = (rs.i + 1);
166 si = rs.s[rs.i];
167 rs.j = (rs.j + si);
168 sj = rs.s[rs.j];
169 rs.s[rs.i] = sj;
170 rs.s[rs.j] = si;
171 return (rs.s[(si + sj) & 0xff]);
172 }
173
174 u_int8_t
__arc4_getbyte(void)175 __arc4_getbyte(void)
176 {
177 u_int8_t val;
178
179 _ARC4_LOCK();
180 if (--arc4_count == 0 || !rs_initialized)
181 arc4_stir();
182 val = arc4_getbyte();
183 _ARC4_UNLOCK();
184 return val;
185 }
186
187 static inline u_int32_t
arc4_getword(void)188 arc4_getword(void)
189 {
190 u_int32_t val;
191 val = arc4_getbyte() << 24;
192 val |= arc4_getbyte() << 16;
193 val |= arc4_getbyte() << 8;
194 val |= arc4_getbyte();
195 return val;
196 }
197
198 void
arc4random_stir(void)199 arc4random_stir(void)
200 {
201 _ARC4_LOCK();
202 arc4_stir();
203 _ARC4_UNLOCK();
204 }
205
206 void
arc4random_addrandom(u_char * dat,int datlen)207 arc4random_addrandom(u_char *dat, int datlen)
208 {
209 _ARC4_LOCK();
210 if (!rs_initialized)
211 arc4_stir();
212 arc4_addrandom(dat, datlen);
213 _ARC4_UNLOCK();
214 }
215
216 u_int32_t
arc4random(void)217 arc4random(void)
218 {
219 u_int32_t val;
220 _ARC4_LOCK();
221 arc4_count -= 4;
222 if (arc4_count <= 0 || !rs_initialized || arc4_stir_pid != getpid())
223 arc4_stir();
224 val = arc4_getword();
225 _ARC4_UNLOCK();
226 return val;
227 }
228
229 void
arc4random_buf(void * _buf,size_t n)230 arc4random_buf(void *_buf, size_t n)
231 {
232 u_char *buf = (u_char *)_buf;
233 _ARC4_LOCK();
234 if (!rs_initialized || arc4_stir_pid != getpid())
235 arc4_stir();
236 while (n--) {
237 if (--arc4_count <= 0)
238 arc4_stir();
239 buf[n] = arc4_getbyte();
240 }
241 _ARC4_UNLOCK();
242 }
243
244 /*
245 * Calculate a uniformly distributed random number less than upper_bound
246 * avoiding "modulo bias".
247 *
248 * Uniformity is achieved by generating new random numbers until the one
249 * returned is outside the range [0, 2**32 % upper_bound). This
250 * guarantees the selected random number will be inside
251 * [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound)
252 * after reduction modulo upper_bound.
253 */
254 u_int32_t
arc4random_uniform(u_int32_t upper_bound)255 arc4random_uniform(u_int32_t upper_bound)
256 {
257 u_int32_t r, min;
258
259 if (upper_bound < 2)
260 return 0;
261
262 #if (ULONG_MAX > 0xffffffffUL)
263 min = 0x100000000UL % upper_bound;
264 #else
265 /* Calculate (2**32 % upper_bound) avoiding 64-bit math */
266 if (upper_bound > 0x80000000)
267 min = 1 + ~upper_bound; /* 2**32 - upper_bound */
268 else {
269 /* (2**32 - (x * 2)) % x == 2**32 % x when x <= 2**31 */
270 min = ((0xffffffff - (upper_bound * 2)) + 1) % upper_bound;
271 }
272 #endif
273
274 /*
275 * This could theoretically loop forever but each retry has
276 * p > 0.5 (worst case, usually far better) of selecting a
277 * number inside the range we need, so it should rarely need
278 * to re-roll.
279 */
280 for (;;) {
281 r = arc4random();
282 if (r >= min)
283 break;
284 }
285
286 return r % upper_bound;
287 }
288
289 #if 0
290 /*-------- Test code for i386 --------*/
291 #include <stdio.h>
292 #include <machine/pctr.h>
293 int
294 main(int argc, char **argv)
295 {
296 const int iter = 1000000;
297 int i;
298 pctrval v;
299
300 v = rdtsc();
301 for (i = 0; i < iter; i++)
302 arc4random();
303 v = rdtsc() - v;
304 v /= iter;
305
306 printf("%qd cycles\n", v);
307 }
308 #endif
309