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