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