1 /* $NetBSD: arc4random.c,v 1.1.1.1 2013/04/11 16:43:21 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 #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 77 struct 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 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; 93 94 static inline unsigned char arc4_getbyte(void); 95 96 static inline void 97 arc4_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 107 static inline void 108 arc4_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 125 static ssize_t 126 read_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 146 static int 147 arc4_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 memset(buf, 0, 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 174 static int 175 arc4_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 memset(buf, 0, 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 211 static int 212 arc4_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 memset(buf, 0, 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 252 static int 253 arc4_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 memset(entropy, 0, sizeof(entropy)); 289 memset(buf, 0, sizeof(buf)); 290 return 0; 291 } 292 #endif 293 294 #ifndef WIN32 295 #define TRY_SEED_URANDOM 296 static int 297 arc4_seed_urandom(void) 298 { 299 /* This is adapted from Tor's crypto_seed_rng() */ 300 static const char *filenames[] = { 301 "/dev/srandom", "/dev/urandom", "/dev/random", NULL 302 }; 303 unsigned char buf[ADD_ENTROPY]; 304 int fd, i; 305 size_t n; 306 307 for (i = 0; filenames[i]; ++i) { 308 fd = evutil_open_closeonexec(filenames[i], O_RDONLY, 0); 309 if (fd<0) 310 continue; 311 n = read_all(fd, buf, sizeof(buf)); 312 close(fd); 313 if (n != sizeof(buf)) 314 return -1; 315 arc4_addrandom(buf, sizeof(buf)); 316 memset(buf, 0, sizeof(buf)); 317 arc4_seeded_ok = 1; 318 return 0; 319 } 320 321 return -1; 322 } 323 #endif 324 325 static int 326 arc4_seed(void) 327 { 328 int ok = 0; 329 /* We try every method that might work, and don't give up even if one 330 * does seem to work. There's no real harm in over-seeding, and if 331 * one of these sources turns out to be broken, that would be bad. */ 332 #ifdef TRY_SEED_WIN32 333 if (0 == arc4_seed_win32()) 334 ok = 1; 335 #endif 336 #ifdef TRY_SEED_URANDOM 337 if (0 == arc4_seed_urandom()) 338 ok = 1; 339 #endif 340 #ifdef TRY_SEED_PROC_SYS_KERNEL_RANDOM_UUID 341 if (0 == arc4_seed_proc_sys_kernel_random_uuid()) 342 ok = 1; 343 #endif 344 #ifdef TRY_SEED_SYSCTL_LINUX 345 /* Apparently Linux is deprecating sysctl, and spewing warning 346 * messages when you try to use it. */ 347 if (!ok && 0 == arc4_seed_sysctl_linux()) 348 ok = 1; 349 #endif 350 #ifdef TRY_SEED_SYSCTL_BSD 351 if (0 == arc4_seed_sysctl_bsd()) 352 ok = 1; 353 #endif 354 return ok ? 0 : -1; 355 } 356 357 static int 358 arc4_stir(void) 359 { 360 int i; 361 362 if (!rs_initialized) { 363 arc4_init(); 364 rs_initialized = 1; 365 } 366 367 arc4_seed(); 368 if (!arc4_seeded_ok) 369 return -1; 370 371 /* 372 * Discard early keystream, as per recommendations in 373 * "Weaknesses in the Key Scheduling Algorithm of RC4" by 374 * Scott Fluhrer, Itsik Mantin, and Adi Shamir. 375 * http://www.wisdom.weizmann.ac.il/~itsik/RC4/Papers/Rc4_ksa.ps 376 * 377 * Ilya Mironov's "(Not So) Random Shuffles of RC4" suggests that 378 * we drop at least 2*256 bytes, with 12*256 as a conservative 379 * value. 380 * 381 * RFC4345 says to drop 6*256. 382 * 383 * At least some versions of this code drop 4*256, in a mistaken 384 * belief that "words" in the Fluhrer/Mantin/Shamir paper refers 385 * to processor words. 386 * 387 * We add another sect to the cargo cult, and choose 12*256. 388 */ 389 for (i = 0; i < 12*256; i++) 390 (void)arc4_getbyte(); 391 arc4_count = BYTES_BEFORE_RESEED; 392 393 return 0; 394 } 395 396 397 static void 398 arc4_stir_if_needed(void) 399 { 400 pid_t pid = getpid(); 401 402 if (arc4_count <= 0 || !rs_initialized || arc4_stir_pid != pid) 403 { 404 arc4_stir_pid = pid; 405 arc4_stir(); 406 } 407 } 408 409 static inline unsigned char 410 arc4_getbyte(void) 411 { 412 unsigned char si, sj; 413 414 rs.i = (rs.i + 1); 415 si = rs.s[rs.i]; 416 rs.j = (rs.j + si); 417 sj = rs.s[rs.j]; 418 rs.s[rs.i] = sj; 419 rs.s[rs.j] = si; 420 return (rs.s[(si + sj) & 0xff]); 421 } 422 423 static inline unsigned int 424 arc4_getword(void) 425 { 426 unsigned int val; 427 428 val = arc4_getbyte() << 24; 429 val |= arc4_getbyte() << 16; 430 val |= arc4_getbyte() << 8; 431 val |= arc4_getbyte(); 432 433 return val; 434 } 435 436 #ifndef ARC4RANDOM_NOSTIR 437 ARC4RANDOM_EXPORT int 438 arc4random_stir(void) 439 { 440 int val; 441 _ARC4_LOCK(); 442 val = arc4_stir(); 443 _ARC4_UNLOCK(); 444 return val; 445 } 446 #endif 447 448 #ifndef ARC4RANDOM_NOADDRANDOM 449 ARC4RANDOM_EXPORT void 450 arc4random_addrandom(const unsigned char *dat, int datlen) 451 { 452 int j; 453 _ARC4_LOCK(); 454 if (!rs_initialized) 455 arc4_stir(); 456 for (j = 0; j < datlen; j += 256) { 457 /* arc4_addrandom() ignores all but the first 256 bytes of 458 * its input. We want to make sure to look at ALL the 459 * data in 'dat', just in case the user is doing something 460 * crazy like passing us all the files in /var/log. */ 461 arc4_addrandom(dat + j, datlen - j); 462 } 463 _ARC4_UNLOCK(); 464 } 465 #endif 466 467 #ifndef ARC4RANDOM_NORANDOM 468 ARC4RANDOM_EXPORT ARC4RANDOM_UINT32 469 arc4random(void) 470 { 471 ARC4RANDOM_UINT32 val; 472 _ARC4_LOCK(); 473 arc4_count -= 4; 474 arc4_stir_if_needed(); 475 val = arc4_getword(); 476 _ARC4_UNLOCK(); 477 return val; 478 } 479 #endif 480 481 ARC4RANDOM_EXPORT void 482 arc4random_buf(void *_buf, size_t n) 483 { 484 unsigned char *buf = _buf; 485 _ARC4_LOCK(); 486 arc4_stir_if_needed(); 487 while (n--) { 488 if (--arc4_count <= 0) 489 arc4_stir(); 490 buf[n] = arc4_getbyte(); 491 } 492 _ARC4_UNLOCK(); 493 } 494 495 #ifndef ARC4RANDOM_NOUNIFORM 496 /* 497 * Calculate a uniformly distributed random number less than upper_bound 498 * avoiding "modulo bias". 499 * 500 * Uniformity is achieved by generating new random numbers until the one 501 * returned is outside the range [0, 2**32 % upper_bound). This 502 * guarantees the selected random number will be inside 503 * [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound) 504 * after reduction modulo upper_bound. 505 */ 506 ARC4RANDOM_EXPORT unsigned int 507 arc4random_uniform(unsigned int upper_bound) 508 { 509 ARC4RANDOM_UINT32 r, min; 510 511 if (upper_bound < 2) 512 return 0; 513 514 #if (UINT_MAX > 0xffffffffUL) 515 min = 0x100000000UL % upper_bound; 516 #else 517 /* Calculate (2**32 % upper_bound) avoiding 64-bit math */ 518 if (upper_bound > 0x80000000) 519 min = 1 + ~upper_bound; /* 2**32 - upper_bound */ 520 else { 521 /* (2**32 - (x * 2)) % x == 2**32 % x when x <= 2**31 */ 522 min = ((0xffffffff - (upper_bound * 2)) + 1) % upper_bound; 523 } 524 #endif 525 526 /* 527 * This could theoretically loop forever but each retry has 528 * p > 0.5 (worst case, usually far better) of selecting a 529 * number inside the range we need, so it should rarely need 530 * to re-roll. 531 */ 532 for (;;) { 533 r = arc4random(); 534 if (r >= min) 535 break; 536 } 537 538 return r % upper_bound; 539 } 540 #endif 541