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