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 (at) uun.org> 12 * Copyright (c) 2008, Damien Miller <djm (at) 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 #ifdef WIN32 54 #include <wincrypt.h> 55 #include <process.h> 56 #else 57 #include <fcntl.h> 58 #include <unistd.h> 59 #include <sys/param.h> 60 #include <sys/time.h> 61 #ifdef _EVENT_HAVE_SYS_SYSCTL_H 62 #include <sys/sysctl.h> 63 #endif 64 #endif 65 #include <limits.h> 66 #include <stdlib.h> 67 #include <string.h> 68 #endif 69 70 /* Add platform entropy 32 bytes (256 bits) at a time. */ 71 #define ADD_ENTROPY 32 72 73 /* Re-seed from the platform RNG after generating this many bytes. */ 74 #define BYTES_BEFORE_RESEED 1600000 75 76 struct arc4_stream { 77 unsigned char i; 78 unsigned char j; 79 unsigned char s[256]; 80 }; 81 82 #ifdef WIN32 83 #define getpid _getpid 84 #define pid_t int 85 #endif 86 87 static int rs_initialized; 88 static struct arc4_stream rs; 89 static pid_t arc4_stir_pid; 90 static int arc4_count; 91 static int arc4_seeded_ok; 92 93 static inline unsigned char arc4_getbyte(void); 94 95 static inline void 96 arc4_init(void) 97 { 98 int n; 99 100 for (n = 0; n < 256; n++) 101 rs.s[n] = n; 102 rs.i = 0; 103 rs.j = 0; 104 } 105 106 static inline void 107 arc4_addrandom(const unsigned char *dat, int datlen) 108 { 109 int n; 110 unsigned char si; 111 112 rs.i--; 113 for (n = 0; n < 256; n++) { 114 rs.i = (rs.i + 1); 115 si = rs.s[rs.i]; 116 rs.j = (rs.j + si + dat[n % datlen]); 117 rs.s[rs.i] = rs.s[rs.j]; 118 rs.s[rs.j] = si; 119 } 120 rs.j = rs.i; 121 } 122 123 #ifndef WIN32 124 static ssize_t 125 read_all(int fd, unsigned char *buf, size_t count) 126 { 127 size_t numread = 0; 128 ssize_t result; 129 130 while (numread < count) { 131 result = read(fd, buf+numread, count-numread); 132 if (result<0) 133 return -1; 134 else if (result == 0) 135 break; 136 numread += result; 137 } 138 139 return (ssize_t)numread; 140 } 141 #endif 142 143 #ifdef WIN32 144 #define TRY_SEED_WIN32 145 static int 146 arc4_seed_win32(void) 147 { 148 /* This is adapted from Tor's crypto_seed_rng() */ 149 static int provider_set = 0; 150 static HCRYPTPROV provider; 151 unsigned char buf[ADD_ENTROPY]; 152 153 if (!provider_set) { 154 if (!CryptAcquireContext(&provider, NULL, NULL, PROV_RSA_FULL, 155 CRYPT_VERIFYCONTEXT)) { 156 if (GetLastError() != (DWORD)NTE_BAD_KEYSET) 157 return -1; 158 } 159 provider_set = 1; 160 } 161 if (!CryptGenRandom(provider, sizeof(buf), buf)) 162 return -1; 163 arc4_addrandom(buf, sizeof(buf)); 164 evutil_memclear_(buf, sizeof(buf)); 165 arc4_seeded_ok = 1; 166 return 0; 167 } 168 #endif 169 170 #if defined(_EVENT_HAVE_SYS_SYSCTL_H) && defined(_EVENT_HAVE_SYSCTL) 171 #if _EVENT_HAVE_DECL_CTL_KERN && _EVENT_HAVE_DECL_KERN_RANDOM && _EVENT_HAVE_DECL_RANDOM_UUID 172 #define TRY_SEED_SYSCTL_LINUX 173 static int 174 arc4_seed_sysctl_linux(void) 175 { 176 /* Based on code by William Ahern, this function tries to use the 177 * RANDOM_UUID sysctl to get entropy from the kernel. This can work 178 * even if /dev/urandom is inaccessible for some reason (e.g., we're 179 * running in a chroot). */ 180 int mib[] = { CTL_KERN, KERN_RANDOM, RANDOM_UUID }; 181 unsigned char buf[ADD_ENTROPY]; 182 size_t len, n; 183 unsigned i; 184 int any_set; 185 186 memset(buf, 0, sizeof(buf)); 187 188 for (len = 0; len < sizeof(buf); len += n) { 189 n = sizeof(buf) - len; 190 191 if (0 != sysctl(mib, 3, &buf[len], &n, NULL, 0)) 192 return -1; 193 } 194 /* make sure that the buffer actually got set. */ 195 for (i=0,any_set=0; i<sizeof(buf); ++i) { 196 any_set |= buf[i]; 197 } 198 if (!any_set) 199 return -1; 200 201 arc4_addrandom(buf, sizeof(buf)); 202 evutil_memclear_(buf, sizeof(buf)); 203 arc4_seeded_ok = 1; 204 return 0; 205 } 206 #endif 207 208 #if _EVENT_HAVE_DECL_CTL_KERN && _EVENT_HAVE_DECL_KERN_ARND 209 #define TRY_SEED_SYSCTL_BSD 210 static int 211 arc4_seed_sysctl_bsd(void) 212 { 213 /* Based on code from William Ahern and from OpenBSD, this function 214 * tries to use the KERN_ARND syscall to get entropy from the kernel. 215 * This can work even if /dev/urandom is inaccessible for some reason 216 * (e.g., we're running in a chroot). */ 217 int mib[] = { CTL_KERN, KERN_ARND }; 218 unsigned char buf[ADD_ENTROPY]; 219 size_t len, n; 220 int i, any_set; 221 222 memset(buf, 0, sizeof(buf)); 223 224 len = sizeof(buf); 225 if (sysctl(mib, 2, buf, &len, NULL, 0) == -1) { 226 for (len = 0; len < sizeof(buf); len += sizeof(unsigned)) { 227 n = sizeof(unsigned); 228 if (n + len > sizeof(buf)) 229 n = len - sizeof(buf); 230 if (sysctl(mib, 2, &buf[len], &n, NULL, 0) == -1) 231 return -1; 232 } 233 } 234 /* make sure that the buffer actually got set. */ 235 for (i=any_set=0; i<sizeof(buf); ++i) { 236 any_set |= buf[i]; 237 } 238 if (!any_set) 239 return -1; 240 241 arc4_addrandom(buf, sizeof(buf)); 242 evutil_memclear_(buf, sizeof(buf)); 243 arc4_seeded_ok = 1; 244 return 0; 245 } 246 #endif 247 #endif /* defined(_EVENT_HAVE_SYS_SYSCTL_H) */ 248 249 #ifdef __linux__ 250 #define TRY_SEED_PROC_SYS_KERNEL_RANDOM_UUID 251 static int 252 arc4_seed_proc_sys_kernel_random_uuid(void) 253 { 254 /* Occasionally, somebody will make /proc/sys accessible in a chroot, 255 * but not /dev/urandom. Let's try /proc/sys/kernel/random/uuid. 256 * Its format is stupid, so we need to decode it from hex. 257 */ 258 int fd; 259 char buf[128]; 260 unsigned char entropy[64]; 261 int bytes, n, i, nybbles; 262 for (bytes = 0; bytes<ADD_ENTROPY; ) { 263 fd = evutil_open_closeonexec("/proc/sys/kernel/random/uuid", O_RDONLY, 0); 264 if (fd < 0) 265 return -1; 266 n = read(fd, buf, sizeof(buf)); 267 close(fd); 268 if (n<=0) 269 return -1; 270 memset(entropy, 0, sizeof(entropy)); 271 for (i=nybbles=0; i<n; ++i) { 272 if (EVUTIL_ISXDIGIT(buf[i])) { 273 int nyb = evutil_hex_char_to_int(buf[i]); 274 if (nybbles & 1) { 275 entropy[nybbles/2] |= nyb; 276 } else { 277 entropy[nybbles/2] |= nyb<<4; 278 } 279 ++nybbles; 280 } 281 } 282 if (nybbles < 2) 283 return -1; 284 arc4_addrandom(entropy, nybbles/2); 285 bytes += nybbles/2; 286 } 287 evutil_memclear_(entropy, sizeof(entropy)); 288 evutil_memclear_(buf, sizeof(buf)); 289 arc4_seeded_ok = 1; 290 return 0; 291 } 292 #endif 293 294 #ifndef WIN32 295 #define TRY_SEED_URANDOM 296 static char *arc4random_urandom_filename = NULL; 297 298 static int arc4_seed_urandom_helper_(const char *fname) 299 { 300 unsigned char buf[ADD_ENTROPY]; 301 int fd; 302 size_t n; 303 304 fd = evutil_open_closeonexec(fname, O_RDONLY, 0); 305 if (fd<0) 306 return -1; 307 n = read_all(fd, buf, sizeof(buf)); 308 close(fd); 309 if (n != sizeof(buf)) 310 return -1; 311 arc4_addrandom(buf, sizeof(buf)); 312 evutil_memclear_(buf, sizeof(buf)); 313 arc4_seeded_ok = 1; 314 return 0; 315 } 316 317 static int 318 arc4_seed_urandom(void) 319 { 320 /* This is adapted from Tor's crypto_seed_rng() */ 321 static const char *filenames[] = { 322 "/dev/srandom", "/dev/urandom", "/dev/random", NULL 323 }; 324 int i; 325 if (arc4random_urandom_filename) 326 return arc4_seed_urandom_helper_(arc4random_urandom_filename); 327 328 for (i = 0; filenames[i]; ++i) { 329 if (arc4_seed_urandom_helper_(filenames[i]) == 0) { 330 return 0; 331 } 332 } 333 334 return -1; 335 } 336 #endif 337 338 static int 339 arc4_seed(void) 340 { 341 int ok = 0; 342 /* We try every method that might work, and don't give up even if one 343 * does seem to work. There's no real harm in over-seeding, and if 344 * one of these sources turns out to be broken, that would be bad. */ 345 #ifdef TRY_SEED_WIN32 346 if (0 == arc4_seed_win32()) 347 ok = 1; 348 #endif 349 #ifdef TRY_SEED_URANDOM 350 if (0 == arc4_seed_urandom()) 351 ok = 1; 352 #endif 353 #ifdef TRY_SEED_PROC_SYS_KERNEL_RANDOM_UUID 354 if (arc4random_urandom_filename == NULL && 355 0 == arc4_seed_proc_sys_kernel_random_uuid()) 356 ok = 1; 357 #endif 358 #ifdef TRY_SEED_SYSCTL_LINUX 359 /* Apparently Linux is deprecating sysctl, and spewing warning 360 * messages when you try to use it. */ 361 if (!ok && 0 == arc4_seed_sysctl_linux()) 362 ok = 1; 363 #endif 364 #ifdef TRY_SEED_SYSCTL_BSD 365 if (0 == arc4_seed_sysctl_bsd()) 366 ok = 1; 367 #endif 368 return ok ? 0 : -1; 369 } 370 371 static int 372 arc4_stir(void) 373 { 374 int i; 375 376 if (!rs_initialized) { 377 arc4_init(); 378 rs_initialized = 1; 379 } 380 381 arc4_seed(); 382 if (!arc4_seeded_ok) 383 return -1; 384 385 /* 386 * Discard early keystream, as per recommendations in 387 * "Weaknesses in the Key Scheduling Algorithm of RC4" by 388 * Scott Fluhrer, Itsik Mantin, and Adi Shamir. 389 * http://www.wisdom.weizmann.ac.il/~itsik/RC4/Papers/Rc4_ksa.ps 390 * 391 * Ilya Mironov's "(Not So) Random Shuffles of RC4" suggests that 392 * we drop at least 2*256 bytes, with 12*256 as a conservative 393 * value. 394 * 395 * RFC4345 says to drop 6*256. 396 * 397 * At least some versions of this code drop 4*256, in a mistaken 398 * belief that "words" in the Fluhrer/Mantin/Shamir paper refers 399 * to processor words. 400 * 401 * We add another sect to the cargo cult, and choose 12*256. 402 */ 403 for (i = 0; i < 12*256; i++) 404 (void)arc4_getbyte(); 405 406 arc4_count = BYTES_BEFORE_RESEED; 407 408 return 0; 409 } 410 411 412 static void 413 arc4_stir_if_needed(void) 414 { 415 pid_t pid = getpid(); 416 417 if (arc4_count <= 0 || !rs_initialized || arc4_stir_pid != pid) 418 { 419 arc4_stir_pid = pid; 420 arc4_stir(); 421 } 422 } 423 424 static inline unsigned char 425 arc4_getbyte(void) 426 { 427 unsigned char si, sj; 428 429 rs.i = (rs.i + 1); 430 si = rs.s[rs.i]; 431 rs.j = (rs.j + si); 432 sj = rs.s[rs.j]; 433 rs.s[rs.i] = sj; 434 rs.s[rs.j] = si; 435 return (rs.s[(si + sj) & 0xff]); 436 } 437 438 static inline unsigned int 439 arc4_getword(void) 440 { 441 unsigned int val; 442 443 val = arc4_getbyte() << 24; 444 val |= arc4_getbyte() << 16; 445 val |= arc4_getbyte() << 8; 446 val |= arc4_getbyte(); 447 448 return val; 449 } 450 451 #ifndef ARC4RANDOM_NOSTIR 452 ARC4RANDOM_EXPORT int 453 arc4random_stir(void) 454 { 455 int val; 456 _ARC4_LOCK(); 457 val = arc4_stir(); 458 _ARC4_UNLOCK(); 459 return val; 460 } 461 #endif 462 463 #ifndef ARC4RANDOM_NOADDRANDOM 464 ARC4RANDOM_EXPORT void 465 arc4random_addrandom(const unsigned char *dat, int datlen) 466 { 467 int j; 468 _ARC4_LOCK(); 469 if (!rs_initialized) 470 arc4_stir(); 471 for (j = 0; j < datlen; j += 256) { 472 /* arc4_addrandom() ignores all but the first 256 bytes of 473 * its input. We want to make sure to look at ALL the 474 * data in 'dat', just in case the user is doing something 475 * crazy like passing us all the files in /var/log. */ 476 arc4_addrandom(dat + j, datlen - j); 477 } 478 _ARC4_UNLOCK(); 479 } 480 #endif 481 482 #ifndef ARC4RANDOM_NORANDOM 483 ARC4RANDOM_EXPORT ARC4RANDOM_UINT32 484 arc4random(void) 485 { 486 ARC4RANDOM_UINT32 val; 487 _ARC4_LOCK(); 488 arc4_count -= 4; 489 arc4_stir_if_needed(); 490 val = arc4_getword(); 491 _ARC4_UNLOCK(); 492 return val; 493 } 494 #endif 495 496 ARC4RANDOM_EXPORT void 497 arc4random_buf(void *_buf, size_t n) 498 { 499 unsigned char *buf = _buf; 500 _ARC4_LOCK(); 501 arc4_stir_if_needed(); 502 while (n--) { 503 if (--arc4_count <= 0) 504 arc4_stir(); 505 buf[n] = arc4_getbyte(); 506 } 507 _ARC4_UNLOCK(); 508 } 509 510 #ifndef ARC4RANDOM_NOUNIFORM 511 /* 512 * Calculate a uniformly distributed random number less than upper_bound 513 * avoiding "modulo bias". 514 * 515 * Uniformity is achieved by generating new random numbers until the one 516 * returned is outside the range [0, 2**32 % upper_bound). This 517 * guarantees the selected random number will be inside 518 * [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound) 519 * after reduction modulo upper_bound. 520 */ 521 ARC4RANDOM_EXPORT unsigned int 522 arc4random_uniform(unsigned int upper_bound) 523 { 524 ARC4RANDOM_UINT32 r, min; 525 526 if (upper_bound < 2) 527 return 0; 528 529 #if (UINT_MAX > 0xffffffffUL) 530 min = 0x100000000UL % upper_bound; 531 #else 532 /* Calculate (2**32 % upper_bound) avoiding 64-bit math */ 533 if (upper_bound > 0x80000000) 534 min = 1 + ~upper_bound; /* 2**32 - upper_bound */ 535 else { 536 /* (2**32 - (x * 2)) % x == 2**32 % x when x <= 2**31 */ 537 min = ((0xffffffff - (upper_bound * 2)) + 1) % upper_bound; 538 } 539 #endif 540 541 /* 542 * This could theoretically loop forever but each retry has 543 * p > 0.5 (worst case, usually far better) of selecting a 544 * number inside the range we need, so it should rarely need 545 * to re-roll. 546 */ 547 for (;;) { 548 r = arc4random(); 549 if (r >= min) 550 break; 551 } 552 553 return r % upper_bound; 554 } 555 #endif 556
