libevent/arc4random.c

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