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 #include "evconfig-private.h"
  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
  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         evutil_memclear_(buf, sizeof(buf));
 165         return 0;
 166 }
 167 #endif
 168
 169 #if defined(EVENT__HAVE_SYS_SYSCTL_H) && defined(EVENT__HAVE_SYSCTL)
 170 #if EVENT__HAVE_DECL_CTL_KERN && EVENT__HAVE_DECL_KERN_RANDOM && EVENT__HAVE_DECL_RANDOM_UUID
 171 #define TRY_SEED_SYSCTL_LINUX
 172 static int
 173 arc4_seed_sysctl_linux(void)
 174 {
 175         /* Based on code by William Ahern, this function tries to use the
 176          * RANDOM_UUID sysctl to get entropy from the kernel.  This can work
 177          * even if /dev/urandom is inaccessible for some reason (e.g., we're
 178          * running in a chroot). */
 179         int mib[] = { CTL_KERN, KERN_RANDOM, RANDOM_UUID };
 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 != sysctl(mib, 3, &buf[len], &n, NULL, 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
 205
 206 #if EVENT__HAVE_DECL_CTL_KERN && EVENT__HAVE_DECL_KERN_ARND
 207 #define TRY_SEED_SYSCTL_BSD
 208 static int
 209 arc4_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
 248 static int
 249 arc4_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
 292 static char *arc4random_urandom_filename = NULL;
 293
 294 static 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
 312 static int
 313 arc4_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
 333 static int
 334 arc4_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_URANDOM
 345         if (0 == arc4_seed_urandom())
 346                 ok = 1;
 347 #endif
 348 #ifdef TRY_SEED_PROC_SYS_KERNEL_RANDOM_UUID
 349         if (arc4random_urandom_filename == NULL &&
 350             0 == arc4_seed_proc_sys_kernel_random_uuid())
 351                 ok = 1;
 352 #endif
 353 #ifdef TRY_SEED_SYSCTL_LINUX
 354         /* Apparently Linux is deprecating sysctl, and spewing warning
 355          * messages when you try to use it. */
 356         if (!ok && 0 == arc4_seed_sysctl_linux())
 357                 ok = 1;
 358 #endif
 359 #ifdef TRY_SEED_SYSCTL_BSD
 360         if (0 == arc4_seed_sysctl_bsd())
 361                 ok = 1;
 362 #endif
 363         return ok ? 0 : -1;
 364 }
 365
 366 static int
 367 arc4_stir(void)
 368 {
 369         int     i;
 370
 371         if (!rs_initialized) {
 372                 arc4_init();
 373                 rs_initialized = 1;
 374         }
 375
 376         if (0 != arc4_seed())
 377                 return -1;
 378
 379         /*
 380          * Discard early keystream, as per recommendations in
 381          * "Weaknesses in the Key Scheduling Algorithm of RC4" by
 382          * Scott Fluhrer, Itsik Mantin, and Adi Shamir.
 383          * http://www.wisdom.weizmann.ac.il/~itsik/RC4/Papers/Rc4_ksa.ps
 384          *
 385          * Ilya Mironov's "(Not So) Random Shuffles of RC4" suggests that
 386          * we drop at least 2*256 bytes, with 12*256 as a conservative
 387          * value.
 388          *
 389          * RFC4345 says to drop 6*256.
 390          *
 391          * At least some versions of this code drop 4*256, in a mistaken
 392          * belief that "words" in the Fluhrer/Mantin/Shamir paper refers
 393          * to processor words.
 394          *
 395          * We add another sect to the cargo cult, and choose 12*256.
 396          */
 397         for (i = 0; i < 12*256; i++)
 398                 (void)arc4_getbyte();
 399
 400         arc4_count = BYTES_BEFORE_RESEED;
 401
 402         return 0;
 403 }
 404
 405
 406 static void
 407 arc4_stir_if_needed(void)
 408 {
 409         pid_t pid = getpid();
 410
 411         if (arc4_count <= 0 || !rs_initialized || arc4_stir_pid != pid)
 412         {
 413                 arc4_stir_pid = pid;
 414                 arc4_stir();
 415         }
 416 }
 417
 418 static inline unsigned char
 419 arc4_getbyte(void)
 420 {
 421         unsigned char si, sj;
 422
 423         rs.i = (rs.i + 1);
 424         si = rs.s[rs.i];
 425         rs.j = (rs.j + si);
 426         sj = rs.s[rs.j];
 427         rs.s[rs.i] = sj;
 428         rs.s[rs.j] = si;
 429         return (rs.s[(si + sj) & 0xff]);
 430 }
 431
 432 static inline unsigned int
 433 arc4_getword(void)
 434 {
 435         unsigned int val;
 436
 437         val = arc4_getbyte() << 24;
 438         val |= arc4_getbyte() << 16;
 439         val |= arc4_getbyte() << 8;
 440         val |= arc4_getbyte();
 441
 442         return val;
 443 }
 444
 445 #ifndef ARC4RANDOM_NOSTIR
 446 ARC4RANDOM_EXPORT int
 447 arc4random_stir(void)
 448 {
 449         int val;
 450         ARC4_LOCK_();
 451         val = arc4_stir();
 452         ARC4_UNLOCK_();
 453         return val;
 454 }
 455 #endif
 456
 457 #ifndef ARC4RANDOM_NOADDRANDOM
 458 ARC4RANDOM_EXPORT void
 459 arc4random_addrandom(const unsigned char *dat, int datlen)
 460 {
 461         int j;
 462         ARC4_LOCK_();
 463         if (!rs_initialized)
 464                 arc4_stir();
 465         for (j = 0; j < datlen; j += 256) {
 466                 /* arc4_addrandom() ignores all but the first 256 bytes of
 467                  * its input.  We want to make sure to look at ALL the
 468                  * data in 'dat', just in case the user is doing something
 469                  * crazy like passing us all the files in /var/log. */
 470                 arc4_addrandom(dat + j, datlen - j);
 471         }
 472         ARC4_UNLOCK_();
 473 }
 474 #endif
 475
 476 #ifndef ARC4RANDOM_NORANDOM
 477 ARC4RANDOM_EXPORT ARC4RANDOM_UINT32
 478 arc4random(void)
 479 {
 480         ARC4RANDOM_UINT32 val;
 481         ARC4_LOCK_();
 482         arc4_count -= 4;
 483         arc4_stir_if_needed();
 484         val = arc4_getword();
 485         ARC4_UNLOCK_();
 486         return val;
 487 }
 488 #endif
 489
 490 ARC4RANDOM_EXPORT void
 491 arc4random_buf(void *buf_, size_t n)
 492 {
 493         unsigned char *buf = buf_;
 494         ARC4_LOCK_();
 495         arc4_stir_if_needed();
 496         while (n--) {
 497                 if (--arc4_count <= 0)
 498                         arc4_stir();
 499                 buf[n] = arc4_getbyte();
 500         }
 501         ARC4_UNLOCK_();
 502 }
 503
 504 #ifndef ARC4RANDOM_NOUNIFORM
 505 /*
 506  * Calculate a uniformly distributed random number less than upper_bound
 507  * avoiding "modulo bias".
 508  *
 509  * Uniformity is achieved by generating new random numbers until the one
 510  * returned is outside the range [0, 2**32 % upper_bound).  This
 511  * guarantees the selected random number will be inside
 512  * [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound)
 513  * after reduction modulo upper_bound.
 514  */
 515 ARC4RANDOM_EXPORT unsigned int
 516 arc4random_uniform(unsigned int upper_bound)
 517 {
 518         ARC4RANDOM_UINT32 r, min;
 519
 520         if (upper_bound < 2)
 521                 return 0;
 522
 523 #if (UINT_MAX > 0xffffffffUL)
 524         min = 0x100000000UL % upper_bound;
 525 #else
 526         /* Calculate (2**32 % upper_bound) avoiding 64-bit math */
 527         if (upper_bound > 0x80000000)
 528                 min = 1 + ~upper_bound;         /* 2**32 - upper_bound */
 529         else {
 530                 /* (2**32 - (x * 2)) % x == 2**32 % x when x <= 2**31 */
 531                 min = ((0xffffffff - (upper_bound * 2)) + 1) % upper_bound;
 532         }
 533 #endif
 534
 535         /*
 536          * This could theoretically loop forever but each retry has
 537          * p > 0.5 (worst case, usually far better) of selecting a
 538          * number inside the range we need, so it should rarely need
 539          * to re-roll.
 540          */
 541         for (;;) {
 542                 r = arc4random();
 543                 if (r >= min)
 544                         break;
 545         }
 546
 547         return r % upper_bound;
 548 }
 549 #endif