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