1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/ipc/chromium/src/third_party/libevent/arc4random.c Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,539 @@
1.4 +/* Portable arc4random.c based on arc4random.c from OpenBSD.
1.5 + * Portable version by Chris Davis, adapted for Libevent by Nick Mathewson
1.6 + * Copyright (c) 2010 Chris Davis, Niels Provos, and Nick Mathewson
1.7 + * Copyright (c) 2010-2012 Niels Provos and Nick Mathewson
1.8 + *
1.9 + * Note that in Libevent, this file isn't compiled directly. Instead,
1.10 + * it's included from evutil_rand.c
1.11 + */
1.12 +
1.13 +/*
1.14 + * Copyright (c) 1996, David Mazieres <dm@uun.org>
1.15 + * Copyright (c) 2008, Damien Miller <djm@openbsd.org>
1.16 + *
1.17 + * Permission to use, copy, modify, and distribute this software for any
1.18 + * purpose with or without fee is hereby granted, provided that the above
1.19 + * copyright notice and this permission notice appear in all copies.
1.20 + *
1.21 + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
1.22 + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
1.23 + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
1.24 + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
1.25 + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
1.26 + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
1.27 + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
1.28 + */
1.29 +
1.30 +/*
1.31 + * Arc4 random number generator for OpenBSD.
1.32 + *
1.33 + * This code is derived from section 17.1 of Applied Cryptography,
1.34 + * second edition, which describes a stream cipher allegedly
1.35 + * compatible with RSA Labs "RC4" cipher (the actual description of
1.36 + * which is a trade secret). The same algorithm is used as a stream
1.37 + * cipher called "arcfour" in Tatu Ylonen's ssh package.
1.38 + *
1.39 + * Here the stream cipher has been modified always to include the time
1.40 + * when initializing the state. That makes it impossible to
1.41 + * regenerate the same random sequence twice, so this can't be used
1.42 + * for encryption, but will generate good random numbers.
1.43 + *
1.44 + * RC4 is a registered trademark of RSA Laboratories.
1.45 + */
1.46 +
1.47 +#ifndef ARC4RANDOM_EXPORT
1.48 +#define ARC4RANDOM_EXPORT
1.49 +#endif
1.50 +
1.51 +#ifndef ARC4RANDOM_UINT32
1.52 +#define ARC4RANDOM_UINT32 uint32_t
1.53 +#endif
1.54 +
1.55 +#ifndef ARC4RANDOM_NO_INCLUDES
1.56 +#ifdef WIN32
1.57 +#include <wincrypt.h>
1.58 +#include <process.h>
1.59 +#else
1.60 +#include <fcntl.h>
1.61 +#include <unistd.h>
1.62 +#include <sys/param.h>
1.63 +#include <sys/time.h>
1.64 +#ifdef _EVENT_HAVE_SYS_SYSCTL_H
1.65 +#include <sys/sysctl.h>
1.66 +#endif
1.67 +#endif
1.68 +#include <limits.h>
1.69 +#include <stdlib.h>
1.70 +#include <string.h>
1.71 +#endif
1.72 +
1.73 +/* Add platform entropy 32 bytes (256 bits) at a time. */
1.74 +#define ADD_ENTROPY 32
1.75 +
1.76 +/* Re-seed from the platform RNG after generating this many bytes. */
1.77 +#define BYTES_BEFORE_RESEED 1600000
1.78 +
1.79 +struct arc4_stream {
1.80 + unsigned char i;
1.81 + unsigned char j;
1.82 + unsigned char s[256];
1.83 +};
1.84 +
1.85 +#ifdef WIN32
1.86 +#define getpid _getpid
1.87 +#define pid_t int
1.88 +#endif
1.89 +
1.90 +static int rs_initialized;
1.91 +static struct arc4_stream rs;
1.92 +static pid_t arc4_stir_pid;
1.93 +static int arc4_count;
1.94 +static int arc4_seeded_ok;
1.95 +
1.96 +static inline unsigned char arc4_getbyte(void);
1.97 +
1.98 +static inline void
1.99 +arc4_init(void)
1.100 +{
1.101 + int n;
1.102 +
1.103 + for (n = 0; n < 256; n++)
1.104 + rs.s[n] = n;
1.105 + rs.i = 0;
1.106 + rs.j = 0;
1.107 +}
1.108 +
1.109 +static inline void
1.110 +arc4_addrandom(const unsigned char *dat, int datlen)
1.111 +{
1.112 + int n;
1.113 + unsigned char si;
1.114 +
1.115 + rs.i--;
1.116 + for (n = 0; n < 256; n++) {
1.117 + rs.i = (rs.i + 1);
1.118 + si = rs.s[rs.i];
1.119 + rs.j = (rs.j + si + dat[n % datlen]);
1.120 + rs.s[rs.i] = rs.s[rs.j];
1.121 + rs.s[rs.j] = si;
1.122 + }
1.123 + rs.j = rs.i;
1.124 +}
1.125 +
1.126 +#ifndef WIN32
1.127 +static ssize_t
1.128 +read_all(int fd, unsigned char *buf, size_t count)
1.129 +{
1.130 + size_t numread = 0;
1.131 + ssize_t result;
1.132 +
1.133 + while (numread < count) {
1.134 + result = read(fd, buf+numread, count-numread);
1.135 + if (result<0)
1.136 + return -1;
1.137 + else if (result == 0)
1.138 + break;
1.139 + numread += result;
1.140 + }
1.141 +
1.142 + return (ssize_t)numread;
1.143 +}
1.144 +#endif
1.145 +
1.146 +#ifdef WIN32
1.147 +#define TRY_SEED_WIN32
1.148 +static int
1.149 +arc4_seed_win32(void)
1.150 +{
1.151 + /* This is adapted from Tor's crypto_seed_rng() */
1.152 + static int provider_set = 0;
1.153 + static HCRYPTPROV provider;
1.154 + unsigned char buf[ADD_ENTROPY];
1.155 +
1.156 + if (!provider_set) {
1.157 + if (!CryptAcquireContext(&provider, NULL, NULL, PROV_RSA_FULL,
1.158 + CRYPT_VERIFYCONTEXT)) {
1.159 + if (GetLastError() != (DWORD)NTE_BAD_KEYSET)
1.160 + return -1;
1.161 + }
1.162 + provider_set = 1;
1.163 + }
1.164 + if (!CryptGenRandom(provider, sizeof(buf), buf))
1.165 + return -1;
1.166 + arc4_addrandom(buf, sizeof(buf));
1.167 + memset(buf, 0, sizeof(buf));
1.168 + arc4_seeded_ok = 1;
1.169 + return 0;
1.170 +}
1.171 +#endif
1.172 +
1.173 +#if defined(_EVENT_HAVE_SYS_SYSCTL_H) && defined(_EVENT_HAVE_SYSCTL)
1.174 +#if _EVENT_HAVE_DECL_CTL_KERN && _EVENT_HAVE_DECL_KERN_RANDOM && _EVENT_HAVE_DECL_RANDOM_UUID
1.175 +#define TRY_SEED_SYSCTL_LINUX
1.176 +static int
1.177 +arc4_seed_sysctl_linux(void)
1.178 +{
1.179 + /* Based on code by William Ahern, this function tries to use the
1.180 + * RANDOM_UUID sysctl to get entropy from the kernel. This can work
1.181 + * even if /dev/urandom is inaccessible for some reason (e.g., we're
1.182 + * running in a chroot). */
1.183 + int mib[] = { CTL_KERN, KERN_RANDOM, RANDOM_UUID };
1.184 + unsigned char buf[ADD_ENTROPY];
1.185 + size_t len, n;
1.186 + unsigned i;
1.187 + int any_set;
1.188 +
1.189 + memset(buf, 0, sizeof(buf));
1.190 +
1.191 + for (len = 0; len < sizeof(buf); len += n) {
1.192 + n = sizeof(buf) - len;
1.193 +
1.194 + if (0 != sysctl(mib, 3, &buf[len], &n, NULL, 0))
1.195 + return -1;
1.196 + }
1.197 + /* make sure that the buffer actually got set. */
1.198 + for (i=0,any_set=0; i<sizeof(buf); ++i) {
1.199 + any_set |= buf[i];
1.200 + }
1.201 + if (!any_set)
1.202 + return -1;
1.203 +
1.204 + arc4_addrandom(buf, sizeof(buf));
1.205 + memset(buf, 0, sizeof(buf));
1.206 + arc4_seeded_ok = 1;
1.207 + return 0;
1.208 +}
1.209 +#endif
1.210 +
1.211 +#if _EVENT_HAVE_DECL_CTL_KERN && _EVENT_HAVE_DECL_KERN_ARND
1.212 +#define TRY_SEED_SYSCTL_BSD
1.213 +static int
1.214 +arc4_seed_sysctl_bsd(void)
1.215 +{
1.216 + /* Based on code from William Ahern and from OpenBSD, this function
1.217 + * tries to use the KERN_ARND syscall to get entropy from the kernel.
1.218 + * This can work even if /dev/urandom is inaccessible for some reason
1.219 + * (e.g., we're running in a chroot). */
1.220 + int mib[] = { CTL_KERN, KERN_ARND };
1.221 + unsigned char buf[ADD_ENTROPY];
1.222 + size_t len, n;
1.223 + int i, any_set;
1.224 +
1.225 + memset(buf, 0, sizeof(buf));
1.226 +
1.227 + len = sizeof(buf);
1.228 + if (sysctl(mib, 2, buf, &len, NULL, 0) == -1) {
1.229 + for (len = 0; len < sizeof(buf); len += sizeof(unsigned)) {
1.230 + n = sizeof(unsigned);
1.231 + if (n + len > sizeof(buf))
1.232 + n = len - sizeof(buf);
1.233 + if (sysctl(mib, 2, &buf[len], &n, NULL, 0) == -1)
1.234 + return -1;
1.235 + }
1.236 + }
1.237 + /* make sure that the buffer actually got set. */
1.238 + for (i=any_set=0; i<sizeof(buf); ++i) {
1.239 + any_set |= buf[i];
1.240 + }
1.241 + if (!any_set)
1.242 + return -1;
1.243 +
1.244 + arc4_addrandom(buf, sizeof(buf));
1.245 + memset(buf, 0, sizeof(buf));
1.246 + arc4_seeded_ok = 1;
1.247 + return 0;
1.248 +}
1.249 +#endif
1.250 +#endif /* defined(_EVENT_HAVE_SYS_SYSCTL_H) */
1.251 +
1.252 +#ifdef __linux__
1.253 +#define TRY_SEED_PROC_SYS_KERNEL_RANDOM_UUID
1.254 +static int
1.255 +arc4_seed_proc_sys_kernel_random_uuid(void)
1.256 +{
1.257 + /* Occasionally, somebody will make /proc/sys accessible in a chroot,
1.258 + * but not /dev/urandom. Let's try /proc/sys/kernel/random/uuid.
1.259 + * Its format is stupid, so we need to decode it from hex.
1.260 + */
1.261 + int fd;
1.262 + char buf[128];
1.263 + unsigned char entropy[64];
1.264 + int bytes, n, i, nybbles;
1.265 + for (bytes = 0; bytes<ADD_ENTROPY; ) {
1.266 + fd = evutil_open_closeonexec("/proc/sys/kernel/random/uuid", O_RDONLY, 0);
1.267 + if (fd < 0)
1.268 + return -1;
1.269 + n = read(fd, buf, sizeof(buf));
1.270 + close(fd);
1.271 + if (n<=0)
1.272 + return -1;
1.273 + memset(entropy, 0, sizeof(entropy));
1.274 + for (i=nybbles=0; i<n; ++i) {
1.275 + if (EVUTIL_ISXDIGIT(buf[i])) {
1.276 + int nyb = evutil_hex_char_to_int(buf[i]);
1.277 + if (nybbles & 1) {
1.278 + entropy[nybbles/2] |= nyb;
1.279 + } else {
1.280 + entropy[nybbles/2] |= nyb<<4;
1.281 + }
1.282 + ++nybbles;
1.283 + }
1.284 + }
1.285 + if (nybbles < 2)
1.286 + return -1;
1.287 + arc4_addrandom(entropy, nybbles/2);
1.288 + bytes += nybbles/2;
1.289 + }
1.290 + memset(entropy, 0, sizeof(entropy));
1.291 + memset(buf, 0, sizeof(buf));
1.292 + return 0;
1.293 +}
1.294 +#endif
1.295 +
1.296 +#ifndef WIN32
1.297 +#define TRY_SEED_URANDOM
1.298 +static int
1.299 +arc4_seed_urandom(void)
1.300 +{
1.301 + /* This is adapted from Tor's crypto_seed_rng() */
1.302 + static const char *filenames[] = {
1.303 + "/dev/srandom", "/dev/urandom", "/dev/random", NULL
1.304 + };
1.305 + unsigned char buf[ADD_ENTROPY];
1.306 + int fd, i;
1.307 + size_t n;
1.308 +
1.309 + for (i = 0; filenames[i]; ++i) {
1.310 + fd = evutil_open_closeonexec(filenames[i], O_RDONLY, 0);
1.311 + if (fd<0)
1.312 + continue;
1.313 + n = read_all(fd, buf, sizeof(buf));
1.314 + close(fd);
1.315 + if (n != sizeof(buf))
1.316 + return -1;
1.317 + arc4_addrandom(buf, sizeof(buf));
1.318 + memset(buf, 0, sizeof(buf));
1.319 + arc4_seeded_ok = 1;
1.320 + return 0;
1.321 + }
1.322 +
1.323 + return -1;
1.324 +}
1.325 +#endif
1.326 +
1.327 +static int
1.328 +arc4_seed(void)
1.329 +{
1.330 + int ok = 0;
1.331 + /* We try every method that might work, and don't give up even if one
1.332 + * does seem to work. There's no real harm in over-seeding, and if
1.333 + * one of these sources turns out to be broken, that would be bad. */
1.334 +#ifdef TRY_SEED_WIN32
1.335 + if (0 == arc4_seed_win32())
1.336 + ok = 1;
1.337 +#endif
1.338 +#ifdef TRY_SEED_URANDOM
1.339 + if (0 == arc4_seed_urandom())
1.340 + ok = 1;
1.341 +#endif
1.342 +#ifdef TRY_SEED_PROC_SYS_KERNEL_RANDOM_UUID
1.343 + if (0 == arc4_seed_proc_sys_kernel_random_uuid())
1.344 + ok = 1;
1.345 +#endif
1.346 +#ifdef TRY_SEED_SYSCTL_LINUX
1.347 + /* Apparently Linux is deprecating sysctl, and spewing warning
1.348 + * messages when you try to use it. */
1.349 + if (!ok && 0 == arc4_seed_sysctl_linux())
1.350 + ok = 1;
1.351 +#endif
1.352 +#ifdef TRY_SEED_SYSCTL_BSD
1.353 + if (0 == arc4_seed_sysctl_bsd())
1.354 + ok = 1;
1.355 +#endif
1.356 + return ok ? 0 : -1;
1.357 +}
1.358 +
1.359 +static int
1.360 +arc4_stir(void)
1.361 +{
1.362 + int i;
1.363 +
1.364 + if (!rs_initialized) {
1.365 + arc4_init();
1.366 + rs_initialized = 1;
1.367 + }
1.368 +
1.369 + arc4_seed();
1.370 + if (!arc4_seeded_ok)
1.371 + return -1;
1.372 +
1.373 + /*
1.374 + * Discard early keystream, as per recommendations in
1.375 + * "Weaknesses in the Key Scheduling Algorithm of RC4" by
1.376 + * Scott Fluhrer, Itsik Mantin, and Adi Shamir.
1.377 + * http://www.wisdom.weizmann.ac.il/~itsik/RC4/Papers/Rc4_ksa.ps
1.378 + *
1.379 + * Ilya Mironov's "(Not So) Random Shuffles of RC4" suggests that
1.380 + * we drop at least 2*256 bytes, with 12*256 as a conservative
1.381 + * value.
1.382 + *
1.383 + * RFC4345 says to drop 6*256.
1.384 + *
1.385 + * At least some versions of this code drop 4*256, in a mistaken
1.386 + * belief that "words" in the Fluhrer/Mantin/Shamir paper refers
1.387 + * to processor words.
1.388 + *
1.389 + * We add another sect to the cargo cult, and choose 12*256.
1.390 + */
1.391 + for (i = 0; i < 12*256; i++)
1.392 + (void)arc4_getbyte();
1.393 + arc4_count = BYTES_BEFORE_RESEED;
1.394 +
1.395 + return 0;
1.396 +}
1.397 +
1.398 +
1.399 +static void
1.400 +arc4_stir_if_needed(void)
1.401 +{
1.402 + pid_t pid = getpid();
1.403 +
1.404 + if (arc4_count <= 0 || !rs_initialized || arc4_stir_pid != pid)
1.405 + {
1.406 + arc4_stir_pid = pid;
1.407 + arc4_stir();
1.408 + }
1.409 +}
1.410 +
1.411 +static inline unsigned char
1.412 +arc4_getbyte(void)
1.413 +{
1.414 + unsigned char si, sj;
1.415 +
1.416 + rs.i = (rs.i + 1);
1.417 + si = rs.s[rs.i];
1.418 + rs.j = (rs.j + si);
1.419 + sj = rs.s[rs.j];
1.420 + rs.s[rs.i] = sj;
1.421 + rs.s[rs.j] = si;
1.422 + return (rs.s[(si + sj) & 0xff]);
1.423 +}
1.424 +
1.425 +static inline unsigned int
1.426 +arc4_getword(void)
1.427 +{
1.428 + unsigned int val;
1.429 +
1.430 + val = arc4_getbyte() << 24;
1.431 + val |= arc4_getbyte() << 16;
1.432 + val |= arc4_getbyte() << 8;
1.433 + val |= arc4_getbyte();
1.434 +
1.435 + return val;
1.436 +}
1.437 +
1.438 +#ifndef ARC4RANDOM_NOSTIR
1.439 +ARC4RANDOM_EXPORT int
1.440 +arc4random_stir(void)
1.441 +{
1.442 + int val;
1.443 + _ARC4_LOCK();
1.444 + val = arc4_stir();
1.445 + _ARC4_UNLOCK();
1.446 + return val;
1.447 +}
1.448 +#endif
1.449 +
1.450 +#ifndef ARC4RANDOM_NOADDRANDOM
1.451 +ARC4RANDOM_EXPORT void
1.452 +arc4random_addrandom(const unsigned char *dat, int datlen)
1.453 +{
1.454 + int j;
1.455 + _ARC4_LOCK();
1.456 + if (!rs_initialized)
1.457 + arc4_stir();
1.458 + for (j = 0; j < datlen; j += 256) {
1.459 + /* arc4_addrandom() ignores all but the first 256 bytes of
1.460 + * its input. We want to make sure to look at ALL the
1.461 + * data in 'dat', just in case the user is doing something
1.462 + * crazy like passing us all the files in /var/log. */
1.463 + arc4_addrandom(dat + j, datlen - j);
1.464 + }
1.465 + _ARC4_UNLOCK();
1.466 +}
1.467 +#endif
1.468 +
1.469 +#ifndef ARC4RANDOM_NORANDOM
1.470 +ARC4RANDOM_EXPORT ARC4RANDOM_UINT32
1.471 +arc4random(void)
1.472 +{
1.473 + ARC4RANDOM_UINT32 val;
1.474 + _ARC4_LOCK();
1.475 + arc4_count -= 4;
1.476 + arc4_stir_if_needed();
1.477 + val = arc4_getword();
1.478 + _ARC4_UNLOCK();
1.479 + return val;
1.480 +}
1.481 +#endif
1.482 +
1.483 +ARC4RANDOM_EXPORT void
1.484 +arc4random_buf(void *_buf, size_t n)
1.485 +{
1.486 + unsigned char *buf = _buf;
1.487 + _ARC4_LOCK();
1.488 + arc4_stir_if_needed();
1.489 + while (n--) {
1.490 + if (--arc4_count <= 0)
1.491 + arc4_stir();
1.492 + buf[n] = arc4_getbyte();
1.493 + }
1.494 + _ARC4_UNLOCK();
1.495 +}
1.496 +
1.497 +#ifndef ARC4RANDOM_NOUNIFORM
1.498 +/*
1.499 + * Calculate a uniformly distributed random number less than upper_bound
1.500 + * avoiding "modulo bias".
1.501 + *
1.502 + * Uniformity is achieved by generating new random numbers until the one
1.503 + * returned is outside the range [0, 2**32 % upper_bound). This
1.504 + * guarantees the selected random number will be inside
1.505 + * [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound)
1.506 + * after reduction modulo upper_bound.
1.507 + */
1.508 +ARC4RANDOM_EXPORT unsigned int
1.509 +arc4random_uniform(unsigned int upper_bound)
1.510 +{
1.511 + ARC4RANDOM_UINT32 r, min;
1.512 +
1.513 + if (upper_bound < 2)
1.514 + return 0;
1.515 +
1.516 +#if (UINT_MAX > 0xffffffffUL)
1.517 + min = 0x100000000UL % upper_bound;
1.518 +#else
1.519 + /* Calculate (2**32 % upper_bound) avoiding 64-bit math */
1.520 + if (upper_bound > 0x80000000)
1.521 + min = 1 + ~upper_bound; /* 2**32 - upper_bound */
1.522 + else {
1.523 + /* (2**32 - (x * 2)) % x == 2**32 % x when x <= 2**31 */
1.524 + min = ((0xffffffff - (upper_bound * 2)) + 1) % upper_bound;
1.525 + }
1.526 +#endif
1.527 +
1.528 + /*
1.529 + * This could theoretically loop forever but each retry has
1.530 + * p > 0.5 (worst case, usually far better) of selecting a
1.531 + * number inside the range we need, so it should rarely need
1.532 + * to re-roll.
1.533 + */
1.534 + for (;;) {
1.535 + r = arc4random();
1.536 + if (r >= min)
1.537 + break;
1.538 + }
1.539 +
1.540 + return r % upper_bound;
1.541 +}
1.542 +#endif
