arc4random.c revision 290001
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#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 70 71/* Add platform entropy 32 bytes (256 bits) at a time. */ 72#define ADD_ENTROPY 32 73 74/* Re-seed from the platform RNG after generating this many bytes. */ 75#define BYTES_BEFORE_RESEED 1600000 76 77struct arc4_stream { 78 unsigned char i; 79 unsigned char j; 80 unsigned char s[256]; 81}; 82 83#ifdef _WIN32 84#define getpid _getpid 85#define pid_t int 86#endif 87 88static int rs_initialized; 89static struct arc4_stream rs; 90static pid_t arc4_stir_pid; 91static int arc4_count; 92static int arc4_seeded_ok; 93 94static inline unsigned char arc4_getbyte(void); 95 96static inline void 97arc4_init(void) 98{ 99 int n; 100 101 for (n = 0; n < 256; n++) 102 rs.s[n] = n; 103 rs.i = 0; 104 rs.j = 0; 105} 106 107static inline void 108arc4_addrandom(const unsigned char *dat, int datlen) 109{ 110 int n; 111 unsigned char si; 112 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; 120 } 121 rs.j = rs.i; 122} 123 124#ifndef _WIN32 125static ssize_t 126read_all(int fd, unsigned char *buf, size_t count) 127{ 128 size_t numread = 0; 129 ssize_t result; 130 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; 138 } 139 140 return (ssize_t)numread; 141} 142#endif 143 144#ifdef _WIN32 145#define TRY_SEED_WIN32 146static int 147arc4_seed_win32(void) 148{ 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]; 153 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; 159 } 160 provider_set = 1; 161 } 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; 168} 169#endif 170 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 174static int 175arc4_seed_sysctl_linux(void) 176{ 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; 186 187 memset(buf, 0, sizeof(buf)); 188 189 for (len = 0; len < sizeof(buf); len += n) { 190 n = sizeof(buf) - len; 191 192 if (0 != sysctl(mib, 3, &buf[len], &n, NULL, 0)) 193 return -1; 194 } 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]; 198 } 199 if (!any_set) 200 return -1; 201 202 arc4_addrandom(buf, sizeof(buf)); 203 evutil_memclear_(buf, sizeof(buf)); 204 arc4_seeded_ok = 1; 205 return 0; 206} 207#endif 208 209#if EVENT__HAVE_DECL_CTL_KERN && EVENT__HAVE_DECL_KERN_ARND 210#define TRY_SEED_SYSCTL_BSD 211static int 212arc4_seed_sysctl_bsd(void) 213{ 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; 222 223 memset(buf, 0, sizeof(buf)); 224 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; 233 } 234 } 235 /* make sure that the buffer actually got set. */ 236 for (i=any_set=0; i<sizeof(buf); ++i) { 237 any_set |= buf[i]; 238 } 239 if (!any_set) 240 return -1; 241 242 arc4_addrandom(buf, sizeof(buf)); 243 evutil_memclear_(buf, sizeof(buf)); 244 arc4_seeded_ok = 1; 245 return 0; 246} 247#endif 248#endif /* defined(EVENT__HAVE_SYS_SYSCTL_H) */ 249 250#ifdef __linux__ 251#define TRY_SEED_PROC_SYS_KERNEL_RANDOM_UUID 252static int 253arc4_seed_proc_sys_kernel_random_uuid(void) 254{ 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. 258 */ 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; 279 } 280 ++nybbles; 281 } 282 } 283 if (nybbles < 2) 284 return -1; 285 arc4_addrandom(entropy, nybbles/2); 286 bytes += nybbles/2; 287 } 288 evutil_memclear_(entropy, sizeof(entropy)); 289 evutil_memclear_(buf, sizeof(buf)); 290 arc4_seeded_ok = 1; 291 return 0; 292} 293#endif 294 295#ifndef _WIN32 296#define TRY_SEED_URANDOM 297static char *arc4random_urandom_filename = NULL; 298 299static int arc4_seed_urandom_helper_(const char *fname) 300{ 301 unsigned char buf[ADD_ENTROPY]; 302 int fd; 303 size_t n; 304 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; 316} 317 318static int 319arc4_seed_urandom(void) 320{ 321 /* This is adapted from Tor's crypto_seed_rng() */ 322 static const char *filenames[] = { 323 "/dev/srandom", "/dev/urandom", "/dev/random", NULL 324 }; 325 int i; 326 if (arc4random_urandom_filename) 327 return arc4_seed_urandom_helper_(arc4random_urandom_filename); 328 329 for (i = 0; filenames[i]; ++i) { 330 if (arc4_seed_urandom_helper_(filenames[i]) == 0) { 331 return 0; 332 } 333 } 334 335 return -1; 336} 337#endif 338 339static int 340arc4_seed(void) 341{ 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; 370} 371 372static int 373arc4_stir(void) 374{ 375 int i; 376 377 if (!rs_initialized) { 378 arc4_init(); 379 rs_initialized = 1; 380 } 381 382 arc4_seed(); 383 if (!arc4_seeded_ok) 384 return -1; 385 386 /* 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 391 * 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. 395 * 396 * RFC4345 says to drop 6*256. 397 * 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. 401 * 402 * We add another sect to the cargo cult, and choose 12*256. 403 */ 404 for (i = 0; i < 12*256; i++) 405 (void)arc4_getbyte(); 406 407 arc4_count = BYTES_BEFORE_RESEED; 408 409 return 0; 410} 411 412 413static void 414arc4_stir_if_needed(void) 415{ 416 pid_t pid = getpid(); 417 418 if (arc4_count <= 0 || !rs_initialized || arc4_stir_pid != pid) 419 { 420 arc4_stir_pid = pid; 421 arc4_stir(); 422 } 423} 424 425static inline unsigned char 426arc4_getbyte(void) 427{ 428 unsigned char si, sj; 429 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]); 437} 438 439static inline unsigned int 440arc4_getword(void) 441{ 442 unsigned int val; 443 444 val = arc4_getbyte() << 24; 445 val |= arc4_getbyte() << 16; 446 val |= arc4_getbyte() << 8; 447 val |= arc4_getbyte(); 448 449 return val; 450} 451 452#ifndef ARC4RANDOM_NOSTIR 453ARC4RANDOM_EXPORT int 454arc4random_stir(void) 455{ 456 int val; 457 ARC4_LOCK_(); 458 val = arc4_stir(); 459 ARC4_UNLOCK_(); 460 return val; 461} 462#endif 463 464#ifndef ARC4RANDOM_NOADDRANDOM 465ARC4RANDOM_EXPORT void 466arc4random_addrandom(const unsigned char *dat, int datlen) 467{ 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); 478 } 479 ARC4_UNLOCK_(); 480} 481#endif 482 483#ifndef ARC4RANDOM_NORANDOM 484ARC4RANDOM_EXPORT ARC4RANDOM_UINT32 485arc4random(void) 486{ 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; 494} 495#endif 496 497ARC4RANDOM_EXPORT void 498arc4random_buf(void *buf_, size_t n) 499{ 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(); 507 } 508 ARC4_UNLOCK_(); 509} 510 511#ifndef ARC4RANDOM_NOUNIFORM 512/* 513 * Calculate a uniformly distributed random number less than upper_bound 514 * avoiding "modulo bias". 515 * 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. 521 */ 522ARC4RANDOM_EXPORT unsigned int 523arc4random_uniform(unsigned int upper_bound) 524{ 525 ARC4RANDOM_UINT32 r, min; 526 527 if (upper_bound < 2) 528 return 0; 529 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; 539 } 540#endif 541 542 /* 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. 547 */ 548 for (;;) { 549 r = arc4random(); 550 if (r >= min) 551 break; 552 } 553 554 return r % upper_bound; 555} 556#endif 557