1 /* Portable arc4random.c based on arc4random.c from OpenBSD.
2 * Portable version by Chris Davis, adapted for Libevent by Nick Mathewson
3 * Copyright (c) 2010 Chris Davis, Niels Provos, and Nick Mathewson
4 * Copyright (c) 2010-2012 Niels Provos and Nick Mathewson
5 *
6 * Note that in Libevent, this file isn't compiled directly. Instead,
7 * it's included from evutil_rand.c
8 */
9
10 /*
11 * Copyright (c) 1996, David Mazieres <dm@uun.org>
12 * Copyright (c) 2008, Damien Miller <djm@openbsd.org>
13 *
14 * Permission to use, copy, modify, and distribute this software for any
15 * purpose with or without fee is hereby granted, provided that the above
16 * copyright notice and this permission notice appear in all copies.
17 *
18 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
19 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
20 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
21 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
22 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
23 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
24 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
25 */
26
27 /*
28 * Arc4 random number generator for OpenBSD.
29 *
30 * This code is derived from section 17.1 of Applied Cryptography,
31 * second edition, which describes a stream cipher allegedly
32 * compatible with RSA Labs "RC4" cipher (the actual description of
33 * which is a trade secret). The same algorithm is used as a stream
34 * cipher called "arcfour" in Tatu Ylonen's ssh package.
35 *
36 * Here the stream cipher has been modified always to include the time
37 * when initializing the state. That makes it impossible to
38 * regenerate the same random sequence twice, so this can't be used
39 * for encryption, but will generate good random numbers.
40 *
41 * RC4 is a registered trademark of RSA Laboratories.
42 */
43
44 #ifndef ARC4RANDOM_EXPORT
45 #define ARC4RANDOM_EXPORT
46 #endif
47
48 #ifndef ARC4RANDOM_UINT32
49 #define ARC4RANDOM_UINT32 uint32_t
50 #endif
51
52 #ifndef ARC4RANDOM_NO_INCLUDES
53 #include "evconfig-private.h"
54 #ifdef _WIN32
55 #include <wincrypt.h>
56 #include <process.h>
57 #include <winerror.h>
58 #else
59 #include <fcntl.h>
60 #include <unistd.h>
61 #include <sys/param.h>
62 #include <sys/time.h>
63 #ifdef EVENT__HAVE_SYS_SYSCTL_H
64 #include <sys/sysctl.h>
65 #endif
66 #ifdef EVENT__HAVE_SYS_RANDOM_H
67 #include <sys/random.h>
68 #endif
69 #endif
70 #include <limits.h>
71 #include <stdlib.h>
72 #include <string.h>
73 #endif
74
75 /* Add platform entropy 32 bytes (256 bits) at a time. */
76 #define ADD_ENTROPY 32
77
78 /* Re-seed from the platform RNG after generating this many bytes. */
79 #define BYTES_BEFORE_RESEED 1600000
80
81 struct arc4_stream {
82 unsigned char i;
83 unsigned char j;
84 unsigned char s[256];
85 };
86
87 #ifdef _WIN32
88 #define getpid _getpid
89 #define pid_t int
90 #endif
91
92 static int rs_initialized;
93 static struct arc4_stream rs;
94 static pid_t arc4_stir_pid;
95 static int arc4_count;
96
97 static inline unsigned char arc4_getbyte(void);
98
99 static inline void
arc4_init(void)100 arc4_init(void)
101 {
102 int n;
103
104 for (n = 0; n < 256; n++)
105 rs.s[n] = n;
106 rs.i = 0;
107 rs.j = 0;
108 }
109
110 static inline void
arc4_addrandom(const unsigned char * dat,int datlen)111 arc4_addrandom(const unsigned char *dat, int datlen)
112 {
113 int n;
114 unsigned char si;
115
116 rs.i--;
117 for (n = 0; n < 256; n++) {
118 rs.i = (rs.i + 1);
119 si = rs.s[rs.i];
120 rs.j = (rs.j + si + dat[n % datlen]);
121 rs.s[rs.i] = rs.s[rs.j];
122 rs.s[rs.j] = si;
123 }
124 rs.j = rs.i;
125 }
126
127 #ifndef _WIN32
128 static ssize_t
read_all(int fd,unsigned char * buf,size_t count)129 read_all(int fd, unsigned char *buf, size_t count)
130 {
131 size_t numread = 0;
132 ssize_t result;
133
134 while (numread < count) {
135 result = read(fd, buf+numread, count-numread);
136 if (result<0)
137 return -1;
138 else if (result == 0)
139 break;
140 numread += result;
141 }
142
143 return (ssize_t)numread;
144 }
145 #endif
146
147 #ifdef _WIN32
148 #define TRY_SEED_WIN32
149 static int
arc4_seed_win32(void)150 arc4_seed_win32(void)
151 {
152 /* This is adapted from Tor's crypto_seed_rng() */
153 static int provider_set = 0;
154 static HCRYPTPROV provider;
155 unsigned char buf[ADD_ENTROPY];
156
157 if (!provider_set) {
158 if (!CryptAcquireContext(&provider, NULL, NULL, PROV_RSA_FULL,
159 CRYPT_VERIFYCONTEXT)) {
160 if (GetLastError() != (DWORD)NTE_BAD_KEYSET)
161 return -1;
162 }
163 provider_set = 1;
164 }
165 if (!CryptGenRandom(provider, sizeof(buf), buf))
166 return -1;
167 arc4_addrandom(buf, sizeof(buf));
168 evutil_memclear_(buf, sizeof(buf));
169 return 0;
170 }
171 #endif
172
173 #if defined(EVENT__HAVE_GETRANDOM)
174 #define TRY_SEED_GETRANDOM
175 static int
arc4_seed_getrandom(void)176 arc4_seed_getrandom(void)
177 {
178 unsigned char buf[ADD_ENTROPY];
179 size_t len, n;
180 unsigned i;
181 int any_set;
182
183 memset(buf, 0, sizeof(buf));
184
185 for (len = 0; len < sizeof(buf); len += n) {
186 n = sizeof(buf) - len;
187
188 if (0 == getrandom(&buf[len], n, 0))
189 return -1;
190 }
191 /* make sure that the buffer actually got set. */
192 for (i=0,any_set=0; i<sizeof(buf); ++i) {
193 any_set |= buf[i];
194 }
195 if (!any_set)
196 return -1;
197
198 arc4_addrandom(buf, sizeof(buf));
199 evutil_memclear_(buf, sizeof(buf));
200 return 0;
201 }
202 #endif /* EVENT__HAVE_GETRANDOM */
203
204 #if defined(EVENT__HAVE_SYS_SYSCTL_H) && defined(EVENT__HAVE_SYSCTL)
205 #if EVENT__HAVE_DECL_CTL_KERN && EVENT__HAVE_DECL_KERN_ARND
206 #define TRY_SEED_SYSCTL_BSD
207 static int
arc4_seed_sysctl_bsd(void)208 arc4_seed_sysctl_bsd(void)
209 {
210 /* Based on code from William Ahern and from OpenBSD, this function
211 * tries to use the KERN_ARND syscall to get entropy from the kernel.
212 * This can work even if /dev/urandom is inaccessible for some reason
213 * (e.g., we're running in a chroot). */
214 int mib[] = { CTL_KERN, KERN_ARND };
215 unsigned char buf[ADD_ENTROPY];
216 size_t len, n;
217 int i, any_set;
218
219 memset(buf, 0, sizeof(buf));
220
221 len = sizeof(buf);
222 if (sysctl(mib, 2, buf, &len, NULL, 0) == -1) {
223 for (len = 0; len < sizeof(buf); len += sizeof(unsigned)) {
224 n = sizeof(unsigned);
225 if (n + len > sizeof(buf))
226 n = len - sizeof(buf);
227 if (sysctl(mib, 2, &buf[len], &n, NULL, 0) == -1)
228 return -1;
229 }
230 }
231 /* make sure that the buffer actually got set. */
232 for (i=any_set=0; i<sizeof(buf); ++i) {
233 any_set |= buf[i];
234 }
235 if (!any_set)
236 return -1;
237
238 arc4_addrandom(buf, sizeof(buf));
239 evutil_memclear_(buf, sizeof(buf));
240 return 0;
241 }
242 #endif
243 #endif /* defined(EVENT__HAVE_SYS_SYSCTL_H) */
244
245 #ifdef __linux__
246 #define TRY_SEED_PROC_SYS_KERNEL_RANDOM_UUID
247 static int
arc4_seed_proc_sys_kernel_random_uuid(void)248 arc4_seed_proc_sys_kernel_random_uuid(void)
249 {
250 /* Occasionally, somebody will make /proc/sys accessible in a chroot,
251 * but not /dev/urandom. Let's try /proc/sys/kernel/random/uuid.
252 * Its format is stupid, so we need to decode it from hex.
253 */
254 int fd;
255 char buf[128];
256 unsigned char entropy[64];
257 int bytes, n, i, nybbles;
258 for (bytes = 0; bytes<ADD_ENTROPY; ) {
259 fd = evutil_open_closeonexec_("/proc/sys/kernel/random/uuid", O_RDONLY, 0);
260 if (fd < 0)
261 return -1;
262 n = read(fd, buf, sizeof(buf));
263 close(fd);
264 if (n<=0)
265 return -1;
266 memset(entropy, 0, sizeof(entropy));
267 for (i=nybbles=0; i<n; ++i) {
268 if (EVUTIL_ISXDIGIT_(buf[i])) {
269 int nyb = evutil_hex_char_to_int_(buf[i]);
270 if (nybbles & 1) {
271 entropy[nybbles/2] |= nyb;
272 } else {
273 entropy[nybbles/2] |= nyb<<4;
274 }
275 ++nybbles;
276 }
277 }
278 if (nybbles < 2)
279 return -1;
280 arc4_addrandom(entropy, nybbles/2);
281 bytes += nybbles/2;
282 }
283 evutil_memclear_(entropy, sizeof(entropy));
284 evutil_memclear_(buf, sizeof(buf));
285 return 0;
286 }
287 #endif
288
289 #ifndef _WIN32
290 #define TRY_SEED_URANDOM
291 static char *arc4random_urandom_filename = NULL;
292
arc4_seed_urandom_helper_(const char * fname)293 static int arc4_seed_urandom_helper_(const char *fname)
294 {
295 unsigned char buf[ADD_ENTROPY];
296 int fd;
297 size_t n;
298
299 fd = evutil_open_closeonexec_(fname, O_RDONLY, 0);
300 if (fd<0)
301 return -1;
302 n = read_all(fd, buf, sizeof(buf));
303 close(fd);
304 if (n != sizeof(buf))
305 return -1;
306 arc4_addrandom(buf, sizeof(buf));
307 evutil_memclear_(buf, sizeof(buf));
308 return 0;
309 }
310
311 static int
arc4_seed_urandom(void)312 arc4_seed_urandom(void)
313 {
314 /* This is adapted from Tor's crypto_seed_rng() */
315 static const char *filenames[] = {
316 "/dev/srandom", "/dev/urandom", "/dev/random", NULL
317 };
318 int i;
319 if (arc4random_urandom_filename)
320 return arc4_seed_urandom_helper_(arc4random_urandom_filename);
321
322 for (i = 0; filenames[i]; ++i) {
323 if (arc4_seed_urandom_helper_(filenames[i]) == 0) {
324 return 0;
325 }
326 }
327
328 return -1;
329 }
330 #endif
331
332 static int
arc4_seed(void)333 arc4_seed(void)
334 {
335 int ok = 0;
336 /* We try every method that might work, and don't give up even if one
337 * does seem to work. There's no real harm in over-seeding, and if
338 * one of these sources turns out to be broken, that would be bad. */
339 #ifdef TRY_SEED_WIN32
340 if (0 == arc4_seed_win32())
341 ok = 1;
342 #endif
343 #ifdef TRY_SEED_GETRANDOM
344 if (0 == arc4_seed_getrandom())
345 ok = 1;
346 #endif
347 #ifdef TRY_SEED_URANDOM
348 if (0 == arc4_seed_urandom())
349 ok = 1;
350 #endif
351 #ifdef TRY_SEED_PROC_SYS_KERNEL_RANDOM_UUID
352 if (arc4random_urandom_filename == NULL &&
353 0 == arc4_seed_proc_sys_kernel_random_uuid())
354 ok = 1;
355 #endif
356 #ifdef TRY_SEED_SYSCTL_BSD
357 if (0 == arc4_seed_sysctl_bsd())
358 ok = 1;
359 #endif
360 return ok ? 0 : -1;
361 }
362
363 static int
arc4_stir(void)364 arc4_stir(void)
365 {
366 int i;
367
368 if (!rs_initialized) {
369 arc4_init();
370 rs_initialized = 1;
371 }
372
373 if (0 != arc4_seed())
374 return -1;
375
376 /*
377 * Discard early keystream, as per recommendations in
378 * "Weaknesses in the Key Scheduling Algorithm of RC4" by
379 * Scott Fluhrer, Itsik Mantin, and Adi Shamir.
380 * http://www.wisdom.weizmann.ac.il/~itsik/RC4/Papers/Rc4_ksa.ps
381 *
382 * Ilya Mironov's "(Not So) Random Shuffles of RC4" suggests that
383 * we drop at least 2*256 bytes, with 12*256 as a conservative
384 * value.
385 *
386 * RFC4345 says to drop 6*256.
387 *
388 * At least some versions of this code drop 4*256, in a mistaken
389 * belief that "words" in the Fluhrer/Mantin/Shamir paper refers
390 * to processor words.
391 *
392 * We add another sect to the cargo cult, and choose 12*256.
393 */
394 for (i = 0; i < 12*256; i++)
395 (void)arc4_getbyte();
396
397 arc4_count = BYTES_BEFORE_RESEED;
398
399 return 0;
400 }
401
402
403 static void
arc4_stir_if_needed(void)404 arc4_stir_if_needed(void)
405 {
406 pid_t pid = getpid();
407
408 if (arc4_count <= 0 || !rs_initialized || arc4_stir_pid != pid)
409 {
410 arc4_stir_pid = pid;
411 arc4_stir();
412 }
413 }
414
415 static inline unsigned char
arc4_getbyte(void)416 arc4_getbyte(void)
417 {
418 unsigned char si, sj;
419
420 rs.i = (rs.i + 1);
421 si = rs.s[rs.i];
422 rs.j = (rs.j + si);
423 sj = rs.s[rs.j];
424 rs.s[rs.i] = sj;
425 rs.s[rs.j] = si;
426 return (rs.s[(si + sj) & 0xff]);
427 }
428
429 static inline unsigned int
arc4_getword(void)430 arc4_getword(void)
431 {
432 unsigned int val;
433
434 val = arc4_getbyte() << 24;
435 val |= arc4_getbyte() << 16;
436 val |= arc4_getbyte() << 8;
437 val |= arc4_getbyte();
438
439 return val;
440 }
441
442 #ifndef ARC4RANDOM_NOSTIR
443 ARC4RANDOM_EXPORT int
arc4random_stir(void)444 arc4random_stir(void)
445 {
446 int val;
447 ARC4_LOCK_();
448 val = arc4_stir();
449 ARC4_UNLOCK_();
450 return val;
451 }
452 #endif
453
454 #ifndef ARC4RANDOM_NOADDRANDOM
455 ARC4RANDOM_EXPORT void
arc4random_addrandom(const unsigned char * dat,int datlen)456 arc4random_addrandom(const unsigned char *dat, int datlen)
457 {
458 int j;
459 ARC4_LOCK_();
460 if (!rs_initialized)
461 arc4_stir();
462 for (j = 0; j < datlen; j += 256) {
463 /* arc4_addrandom() ignores all but the first 256 bytes of
464 * its input. We want to make sure to look at ALL the
465 * data in 'dat', just in case the user is doing something
466 * crazy like passing us all the files in /var/log. */
467 arc4_addrandom(dat + j, datlen - j);
468 }
469 ARC4_UNLOCK_();
470 }
471 #endif
472
473 #ifndef ARC4RANDOM_NORANDOM
474 ARC4RANDOM_EXPORT ARC4RANDOM_UINT32
arc4random(void)475 arc4random(void)
476 {
477 ARC4RANDOM_UINT32 val;
478 ARC4_LOCK_();
479 arc4_count -= 4;
480 arc4_stir_if_needed();
481 val = arc4_getword();
482 ARC4_UNLOCK_();
483 return val;
484 }
485 #endif
486
487 ARC4RANDOM_EXPORT void
arc4random_buf(void * buf_,size_t n)488 arc4random_buf(void *buf_, size_t n)
489 {
490 unsigned char *buf = buf_;
491 ARC4_LOCK_();
492 arc4_stir_if_needed();
493 while (n--) {
494 if (--arc4_count <= 0)
495 arc4_stir();
496 buf[n] = arc4_getbyte();
497 }
498 ARC4_UNLOCK_();
499 }
500
501 #ifndef ARC4RANDOM_NOUNIFORM
502 /*
503 * Calculate a uniformly distributed random number less than upper_bound
504 * avoiding "modulo bias".
505 *
506 * Uniformity is achieved by generating new random numbers until the one
507 * returned is outside the range [0, 2**32 % upper_bound). This
508 * guarantees the selected random number will be inside
509 * [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound)
510 * after reduction modulo upper_bound.
511 */
512 ARC4RANDOM_EXPORT unsigned int
arc4random_uniform(unsigned int upper_bound)513 arc4random_uniform(unsigned int upper_bound)
514 {
515 ARC4RANDOM_UINT32 r, min;
516
517 if (upper_bound < 2)
518 return 0;
519
520 #if (UINT_MAX > 0xffffffffUL)
521 min = 0x100000000UL % upper_bound;
522 #else
523 /* Calculate (2**32 % upper_bound) avoiding 64-bit math */
524 if (upper_bound > 0x80000000)
525 min = 1 + ~upper_bound; /* 2**32 - upper_bound */
526 else {
527 /* (2**32 - (x * 2)) % x == 2**32 % x when x <= 2**31 */
528 min = ((0xffffffff - (upper_bound * 2)) + 1) % upper_bound;
529 }
530 #endif
531
532 /*
533 * This could theoretically loop forever but each retry has
534 * p > 0.5 (worst case, usually far better) of selecting a
535 * number inside the range we need, so it should rarely need
536 * to re-roll.
537 */
538 for (;;) {
539 r = arc4random();
540 if (r >= min)
541 break;
542 }
543
544 return r % upper_bound;
545 }
546 #endif
547