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