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