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