src/lib/crypt_ops/crypto_rand.c

   1 /* Copyright (c) 2001, Matej Pfajfar.
   2  * Copyright (c) 2001-2004, Roger Dingledine.
   3  * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
   4  * Copyright (c) 2007-2021, The Tor Project, Inc. */
   5 /* See LICENSE for licensing information */
   6
   7 /**
   8  * \file crypto_rand.c
   9  *
  10  * \brief Functions for initialising and seeding (pseudo-)random
  11  * number generators, and working with randomness.
  12  **/
  13
  14 #define CRYPTO_RAND_PRIVATE
  15
  16 #include "lib/crypt_ops/crypto_rand.h"
  17
  18 #ifdef _WIN32
  19 #include <windows.h>
  20 #include <wincrypt.h>
  21 #endif /* defined(_WIN32) */
  22
  23 #include "lib/container/smartlist.h"
  24 #include "lib/crypt_ops/compat_openssl.h"
  25 #include "lib/crypt_ops/crypto_util.h"
  26 #include "lib/encoding/binascii.h"
  27 #include "lib/intmath/weakrng.h"
  28 #include "lib/log/log.h"
  29 #include "lib/log/util_bug.h"
  30 #include "lib/malloc/malloc.h"
  31 #include "lib/sandbox/sandbox.h"
  32 #include "lib/string/compat_string.h"
  33 #include "lib/string/util_string.h"
  34 #include "lib/testsupport/testsupport.h"
  35 #include "lib/fs/files.h"
  36
  37 #include "lib/defs/digest_sizes.h"
  38 #include "lib/crypt_ops/crypto_digest.h"
  39 #include "lib/ctime/di_ops.h"
  40
  41 #ifdef ENABLE_NSS
  42 #include "lib/crypt_ops/crypto_nss_mgt.h"
  43 #endif
  44
  45 #ifdef ENABLE_OPENSSL
  46 DISABLE_GCC_WARNING("-Wredundant-decls")
  47 #include <openssl/rand.h>
  48 #include <openssl/sha.h>
  49 ENABLE_GCC_WARNING("-Wredundant-decls")
  50 #endif /* defined(ENABLE_OPENSSL) */
  51
  52 #ifdef ENABLE_NSS
  53 DISABLE_GCC_WARNING("-Wstrict-prototypes")
  54 #include <pk11pub.h>
  55 #include <secerr.h>
  56 #include <prerror.h>
  57 ENABLE_GCC_WARNING("-Wstrict-prototypes")
  58 #endif
  59
  60 #if __GNUC__ && GCC_VERSION >= 402
  61 #if GCC_VERSION >= 406
  62 #pragma GCC diagnostic pop
  63 #else
  64 #pragma GCC diagnostic warning "-Wredundant-decls"
  65 #endif
  66 #endif /* __GNUC__ && GCC_VERSION >= 402 */
  67
  68 #ifdef HAVE_FCNTL_H
  69 #include <fcntl.h>
  70 #endif
  71 #ifdef HAVE_SYS_FCNTL_H
  72 #include <sys/fcntl.h>
  73 #endif
  74 #ifdef HAVE_SYS_STAT_H
  75 #include <sys/stat.h>
  76 #endif
  77 #ifdef HAVE_UNISTD_H
  78 #include <unistd.h>
  79 #endif
  80 #ifdef HAVE_SYS_SYSCALL_H
  81 #include <sys/syscall.h>
  82 #endif
  83 #ifdef HAVE_SYS_RANDOM_H
  84 #include <sys/random.h>
  85 #endif
  86
  87 #include <string.h>
  88 #include <errno.h>
  89
  90 /**
  91  * How many bytes of entropy we add at once.
  92  *
  93  * This is how much entropy OpenSSL likes to add right now, so maybe it will
  94  * work for us too.
  95  **/
  96 #define ADD_ENTROPY 32
  97
  98 /**
  99  * Longest recognized DNS query.
 100  **/
 101 #define MAX_DNS_LABEL_SIZE 63
 102
 103 /**
 104  * Largest strong entropy request permitted.
 105  **/
 106 #define MAX_STRONGEST_RAND_SIZE 256
 107
 108 /**
 109  * Set the seed of the weak RNG to a random value.
 110  **/
 111 void
 112 crypto_seed_weak_rng(tor_weak_rng_t *rng)
 113 {
 114   unsigned seed;
 115   crypto_rand((void*)&seed, sizeof(seed));
 116   tor_init_weak_random(rng, seed);
 117 }
 118
 119 #ifdef TOR_UNIT_TESTS
 120 int break_strongest_rng_syscall = 0;
 121 int break_strongest_rng_fallback = 0;
 122 #endif
 123
 124 /**
 125  * Try to get <b>out_len</b> bytes of the strongest entropy we can generate,
 126  * via system calls, storing it into <b>out</b>. Return 0 on success, -1 on
 127  * failure.  A maximum request size of 256 bytes is imposed.
 128  **/
 129 static int
 130 crypto_strongest_rand_syscall(uint8_t *out, size_t out_len)
 131 {
 132   tor_assert(out_len <= MAX_STRONGEST_RAND_SIZE);
 133
 134   /* We only log at notice-level here because in the case that this function
 135    * fails the crypto_strongest_rand_raw() caller will log with a warning-level
 136    * message and let crypto_strongest_rand() error out and finally terminating
 137    * Tor with an assertion error.
 138    */
 139
 140 #ifdef TOR_UNIT_TESTS
 141   if (break_strongest_rng_syscall)
 142     return -1;
 143 #endif
 144
 145 #if defined(_WIN32)
 146   static int provider_set = 0;
 147   static HCRYPTPROV provider;
 148
 149   if (!provider_set) {
 150     if (!CryptAcquireContext(&provider, NULL, NULL, PROV_RSA_FULL,
 151                              CRYPT_VERIFYCONTEXT)) {
 152       log_notice(LD_CRYPTO, "Unable to set Windows CryptoAPI provider [1].");
 153       return -1;
 154     }
 155     provider_set = 1;
 156   }
 157   if (!CryptGenRandom(provider, out_len, out)) {
 158     log_notice(LD_CRYPTO, "Unable get entropy from the Windows CryptoAPI.");
 159     return -1;
 160   }
 161
 162   return 0;
 163 #elif defined(__linux__) && defined(SYS_getrandom)
 164   static int getrandom_works = 1; /* Be optimistic about our chances... */
 165
 166   /* getrandom() isn't as straightforward as getentropy(), and has
 167    * no glibc wrapper.
 168    *
 169    * As far as I can tell from getrandom(2) and the source code, the
 170    * requests we issue will always succeed (though it will block on the
 171    * call if /dev/urandom isn't seeded yet), since we are NOT specifying
 172    * GRND_NONBLOCK and the request is <= 256 bytes.
 173    *
 174    * The manpage is unclear on what happens if a signal interrupts the call
 175    * while the request is blocked due to lack of entropy....
 176    *
 177    * We optimistically assume that getrandom() is available and functional
 178    * because it is the way of the future, and 2 branch mispredicts pale in
 179    * comparison to the overheads involved with failing to open
 180    * /dev/srandom followed by opening and reading from /dev/urandom.
 181    */
 182   if (PREDICT_LIKELY(getrandom_works)) {
 183     long ret;
 184     /* A flag of '0' here means to read from '/dev/urandom', and to
 185      * block if insufficient entropy is available to service the
 186      * request.
 187      */
 188     const unsigned int flags = 0;
 189     do {
 190       ret = syscall(SYS_getrandom, out, out_len, flags);
 191     } while (ret == -1 && ((errno == EINTR) ||(errno == EAGAIN)));
 192
 193     if (PREDICT_UNLIKELY(ret == -1)) {
 194       /* LCOV_EXCL_START we can't actually make the syscall fail in testing. */
 195       tor_assert(errno != EAGAIN);
 196       tor_assert(errno != EINTR);
 197
 198       /* Useful log message for errno. */
 199       if (errno == ENOSYS) {
 200         log_notice(LD_CRYPTO, "Can't get entropy from getrandom()."
 201                    " You are running a version of Tor built to support"
 202                    " getrandom(), but the kernel doesn't implement this"
 203                    " function--probably because it is too old?"
 204                    " Trying fallback method instead.");
 205       } else {
 206         log_notice(LD_CRYPTO, "Can't get entropy from getrandom(): %s."
 207                               " Trying fallback method instead.",
 208                    strerror(errno));
 209       }
 210
 211       getrandom_works = 0; /* Don't bother trying again. */
 212       return -1;
 213       /* LCOV_EXCL_STOP */
 214     }
 215
 216     tor_assert(ret == (long)out_len);
 217     return 0;
 218   }
 219
 220   return -1; /* getrandom() previously failed unexpectedly. */
 221 #elif defined(HAVE_GETENTROPY)
 222   /* getentropy() is what Linux's getrandom() wants to be when it grows up.
 223    * the only gotcha is that requests are limited to 256 bytes.
 224    */
 225   return getentropy(out, out_len);
 226 #else
 227   (void) out;
 228 #endif /* defined(_WIN32) || ... */
 229
 230   /* This platform doesn't have a supported syscall based random. */
 231   return -1;
 232 }
 233
 234 /**
 235  * Try to get <b>out_len</b> bytes of the strongest entropy we can generate,
 236  * via the per-platform fallback mechanism, storing it into <b>out</b>.
 237  * Return 0 on success, -1 on failure.  A maximum request size of 256 bytes
 238  * is imposed.
 239  **/
 240 static int
 241 crypto_strongest_rand_fallback(uint8_t *out, size_t out_len)
 242 {
 243 #ifdef TOR_UNIT_TESTS
 244   if (break_strongest_rng_fallback)
 245     return -1;
 246 #endif
 247
 248 #ifdef _WIN32
 249   /* Windows exclusively uses crypto_strongest_rand_syscall(). */
 250   (void)out;
 251   (void)out_len;
 252   return -1;
 253 #else /* !defined(_WIN32) */
 254   static const char *filenames[] = {
 255     "/dev/srandom", "/dev/urandom", "/dev/random", NULL
 256   };
 257   int fd, i;
 258   size_t n;
 259
 260   for (i = 0; filenames[i]; ++i) {
 261     log_debug(LD_FS, "Considering %s as entropy source", filenames[i]);
 262     fd = open(sandbox_intern_string(filenames[i]), O_RDONLY, 0);
 263     if (fd<0) continue;
 264     log_info(LD_CRYPTO, "Reading entropy from \"%s\"", filenames[i]);
 265     n = read_all_from_fd(fd, (char*)out, out_len);
 266     close(fd);
 267     if (n != out_len) {
 268       /* LCOV_EXCL_START
 269        * We can't make /dev/foorandom actually fail. */
 270       log_notice(LD_CRYPTO,
 271                  "Error reading from entropy source %s (read only %lu bytes).",
 272                  filenames[i],
 273                  (unsigned long)n);
 274       return -1;
 275       /* LCOV_EXCL_STOP */
 276     }
 277
 278     return 0;
 279   }
 280
 281   return -1;
 282 #endif /* defined(_WIN32) */
 283 }
 284
 285 /**
 286  * Try to get <b>out_len</b> bytes of the strongest entropy we can generate,
 287  * storing it into <b>out</b>. Return 0 on success, -1 on failure.  A maximum
 288  * request size of 256 bytes is imposed.
 289  **/
 290 STATIC int
 291 crypto_strongest_rand_raw(uint8_t *out, size_t out_len)
 292 {
 293   static const size_t sanity_min_size = 16;
 294   static const int max_attempts = 3;
 295   tor_assert(out_len <= MAX_STRONGEST_RAND_SIZE);
 296
 297   /* For buffers >= 16 bytes (128 bits), we sanity check the output by
 298    * zero filling the buffer and ensuring that it actually was at least
 299    * partially modified.
 300    *
 301    * Checking that any individual byte is non-zero seems like it would
 302    * fail too often (p = out_len * 1/256) for comfort, but this is an
 303    * "adjust according to taste" sort of check.
 304    */
 305   memwipe(out, 0, out_len);
 306   for (int i = 0; i < max_attempts; i++) {
 307     /* Try to use the syscall/OS favored mechanism to get strong entropy. */
 308     if (crypto_strongest_rand_syscall(out, out_len) != 0) {
 309       /* Try to use the less-favored mechanism to get strong entropy. */
 310       if (crypto_strongest_rand_fallback(out, out_len) != 0) {
 311         /* Welp, we tried.  Hopefully the calling code terminates the process
 312          * since we're basically boned without good entropy.
 313          */
 314         log_warn(LD_CRYPTO,
 315                  "Cannot get strong entropy: no entropy source found.");
 316         return -1;
 317       }
 318     }
 319
 320     if ((out_len < sanity_min_size) || !safe_mem_is_zero((char*)out, out_len))
 321       return 0;
 322   }
 323
 324   /* LCOV_EXCL_START
 325    *
 326    * We tried max_attempts times to fill a buffer >= 128 bits long,
 327    * and each time it returned all '0's.  Either the system entropy
 328    * source is busted, or the user should go out and buy a ticket to
 329    * every lottery on the planet.
 330    */
 331   log_warn(LD_CRYPTO, "Strong OS entropy returned all zero buffer.");
 332
 333   return -1;
 334   /* LCOV_EXCL_STOP */
 335 }
 336
 337 /**
 338  * Try to get <b>out_len</b> bytes of the strongest entropy we can generate,
 339  * storing it into <b>out</b>.
 340  **/
 341 void
 342 crypto_strongest_rand(uint8_t *out, size_t out_len)
 343 {
 344   crypto_strongest_rand_(out, out_len);
 345 }
 346
 347 /**
 348  * Try to get <b>out_len</b> bytes of the strongest entropy we can generate,
 349  * storing it into <b>out</b>. (Mockable version.)
 350  **/
 351 MOCK_IMPL(void,
 352 crypto_strongest_rand_,(uint8_t *out, size_t out_len))
 353 {
 354 #define DLEN DIGEST512_LEN
 355
 356   /* We're going to hash DLEN bytes from the system RNG together with some
 357    * bytes from the PRNGs from our crypto librar(y/ies), in order to yield
 358    * DLEN bytes.
 359    */
 360   uint8_t inp[DLEN*3];
 361   uint8_t tmp[DLEN];
 362   tor_assert(out);
 363   while (out_len) {
 364     memset(inp, 0, sizeof(inp));
 365 #ifdef ENABLE_OPENSSL
 366     RAND_bytes(inp, DLEN);
 367 #endif
 368 #ifdef ENABLE_NSS
 369     PK11_GenerateRandom(inp+DLEN, DLEN);
 370 #endif
 371     if (crypto_strongest_rand_raw(inp+DLEN*2, DLEN) < 0) {
 372       // LCOV_EXCL_START
 373       log_err(LD_CRYPTO, "Failed to load strong entropy when generating an "
 374               "important key. Exiting.");
 375       /* Die with an assertion so we get a stack trace. */
 376       tor_assert(0);
 377       // LCOV_EXCL_STOP
 378     }
 379     if (out_len >= DLEN) {
 380       crypto_digest512((char*)out, (char*)inp, sizeof(inp), DIGEST_SHA512);
 381       out += DLEN;
 382       out_len -= DLEN;
 383     } else {
 384       crypto_digest512((char*)tmp, (char*)inp, sizeof(inp), DIGEST_SHA512);
 385       memcpy(out, tmp, out_len);
 386       break;
 387     }
 388   }
 389   memwipe(tmp, 0, sizeof(tmp));
 390   memwipe(inp, 0, sizeof(inp));
 391 #undef DLEN
 392 }
 393
 394 #ifdef ENABLE_OPENSSL
 395 /**
 396  * Seed OpenSSL's random number generator with bytes from the operating
 397  * system.  Return 0 on success, -1 on failure.
 398  **/
 399 static int
 400 crypto_seed_openssl_rng(void)
 401 {
 402   int rand_poll_ok = 0, load_entropy_ok = 0;
 403   uint8_t buf[ADD_ENTROPY];
 404
 405   /* OpenSSL has a RAND_poll function that knows about more kinds of
 406    * entropy than we do.  We'll try calling that, *and* calling our own entropy
 407    * functions.  If one succeeds, we'll accept the RNG as seeded. */
 408   rand_poll_ok = RAND_poll();
 409   if (rand_poll_ok == 0)
 410     log_warn(LD_CRYPTO, "RAND_poll() failed."); // LCOV_EXCL_LINE
 411
 412   load_entropy_ok = !crypto_strongest_rand_raw(buf, sizeof(buf));
 413   if (load_entropy_ok) {
 414     RAND_seed(buf, sizeof(buf));
 415   }
 416
 417   memwipe(buf, 0, sizeof(buf));
 418
 419   if ((rand_poll_ok || load_entropy_ok) && RAND_status() == 1)
 420     return 0;
 421   else
 422     return -1;
 423 }
 424 #endif /* defined(ENABLE_OPENSSL) */
 425
 426 #ifdef ENABLE_NSS
 427 /**
 428  * Seed OpenSSL's random number generator with bytes from the operating
 429  * system.  Return 0 on success, -1 on failure.
 430  **/
 431 static int
 432 crypto_seed_nss_rng(void)
 433 {
 434   uint8_t buf[ADD_ENTROPY];
 435
 436   int load_entropy_ok = !crypto_strongest_rand_raw(buf, sizeof(buf));
 437   if (load_entropy_ok) {
 438     if (PK11_RandomUpdate(buf, sizeof(buf)) != SECSuccess) {
 439       load_entropy_ok = 0;
 440     }
 441   }
 442
 443   memwipe(buf, 0, sizeof(buf));
 444
 445   return load_entropy_ok ? 0 : -1;
 446 }
 447 #endif /* defined(ENABLE_NSS) */
 448
 449 /**
 450  * Seed the RNG for any and all crypto libraries that we're using with bytes
 451  * from the operating system.  Return 0 on success, -1 on failure.
 452  */
 453 int
 454 crypto_seed_rng(void)
 455 {
 456   int seeded = 0;
 457 #ifdef ENABLE_NSS
 458   if (crypto_seed_nss_rng() < 0)
 459     return -1;
 460   ++seeded;
 461 #endif
 462 #ifdef ENABLE_OPENSSL
 463   if (crypto_seed_openssl_rng() < 0)
 464     return -1;
 465   ++seeded;
 466 #endif
 467   tor_assert(seeded);
 468   return 0;
 469 }
 470
 471 /**
 472  * Write <b>n</b> bytes of strong random data to <b>to</b>. Supports mocking
 473  * for unit tests.
 474  *
 475  * This function is not allowed to fail; if it would fail to generate strong
 476  * entropy, it must terminate the process instead.
 477  **/
 478 MOCK_IMPL(void,
 479 crypto_rand, (char *to, size_t n))
 480 {
 481   crypto_rand_unmocked(to, n);
 482 }
 483
 484 /**
 485  * Write <b>n</b> bytes of strong random data to <b>to</b>.  Most callers
 486  * will want crypto_rand instead.
 487  *
 488  * This function is not allowed to fail; if it would fail to generate strong
 489  * entropy, it must terminate the process instead.
 490  **/
 491 void
 492 crypto_rand_unmocked(char *to, size_t n)
 493 {
 494   if (n == 0)
 495     return;
 496
 497   tor_assert(n < INT_MAX);
 498   tor_assert(to);
 499
 500 #ifdef ENABLE_NSS
 501   SECStatus s = PK11_GenerateRandom((unsigned char*)to, (int)n);
 502   if (s != SECSuccess) {
 503     /* NSS rather sensibly might refuse to generate huge amounts of random
 504      * data at once.  Unfortunately, our unit test do this in a couple of
 505      * places.  To solve this issue, we use our XOF to stretch a shorter
 506      * output when a longer one is needed.
 507      *
 508      * Yes, this is secure. */
 509
 510     /* This is longer than it needs to be; 1600 bits == 200 bytes is the
 511      * state-size of SHA3. */
 512 #define BUFLEN 512
 513     tor_assert(PR_GetError() == SEC_ERROR_INVALID_ARGS && n > BUFLEN);
 514     unsigned char buf[BUFLEN];
 515     s = PK11_GenerateRandom(buf, BUFLEN);
 516     tor_assert(s == SECSuccess);
 517     crypto_xof_t *xof = crypto_xof_new();
 518     crypto_xof_add_bytes(xof, buf, BUFLEN);
 519     crypto_xof_squeeze_bytes(xof, (unsigned char *)to, n);
 520     crypto_xof_free(xof);
 521     memwipe(buf, 0, BUFLEN);
 522
 523 #undef BUFLEN
 524   }
 525 #else /* !defined(ENABLE_NSS) */
 526   int r = RAND_bytes((unsigned char*)to, (int)n);
 527   /* We consider a PRNG failure non-survivable. Let's assert so that we get a
 528    * stack trace about where it happened.
 529    */
 530   tor_assert(r == 1);
 531 #endif
 532 }
 533
 534 /**
 535  * Draw an unsigned 32-bit integer uniformly at random.
 536  */
 537 uint32_t
 538 crypto_rand_u32(void)
 539 {
 540   uint32_t rand;
 541   crypto_rand((void*)&rand, sizeof(rand));
 542   return rand;
 543 }
 544
 545 /**
 546  * Generate and return a new random hostname starting with <b>prefix</b>,
 547  * ending with <b>suffix</b>, and containing no fewer than
 548  * <b>min_rand_len</b> and no more than <b>max_rand_len</b> random base32
 549  * characters. Does not check for failure.
 550  *
 551  * Clip <b>max_rand_len</b> to MAX_DNS_LABEL_SIZE.
 552  **/
 553 char *
 554 crypto_random_hostname(int min_rand_len, int max_rand_len, const char *prefix,
 555                        const char *suffix)
 556 {
 557   char *result, *rand_bytes;
 558   int randlen, rand_bytes_len;
 559   size_t resultlen, prefixlen;
 560
 561   if (max_rand_len > MAX_DNS_LABEL_SIZE)
 562     max_rand_len = MAX_DNS_LABEL_SIZE;
 563   if (min_rand_len > max_rand_len)
 564     min_rand_len = max_rand_len;
 565
 566   randlen = crypto_rand_int_range(min_rand_len, max_rand_len+1);
 567
 568   prefixlen = strlen(prefix);
 569   resultlen = prefixlen + strlen(suffix) + randlen + 16;
 570
 571   /* (x+(n-1))/n is an idiom for dividing x by n, rounding up to the nearest
 572    * integer and thus why this construction. */
 573   rand_bytes_len = ((randlen*5)+7)/8;
 574   if (rand_bytes_len % 5)
 575     rand_bytes_len += 5 - (rand_bytes_len%5);
 576   rand_bytes = tor_malloc(rand_bytes_len);
 577   crypto_rand(rand_bytes, rand_bytes_len);
 578
 579   result = tor_malloc(resultlen);
 580   memcpy(result, prefix, prefixlen);
 581   base32_encode(result+prefixlen, resultlen-prefixlen,
 582                 rand_bytes, rand_bytes_len);
 583   tor_free(rand_bytes);
 584   strlcpy(result+prefixlen+randlen, suffix, resultlen-(prefixlen+randlen));
 585
 586   return result;
 587 }
 588
 589 /**
 590  * Return a randomly chosen element of <b>sl</b>; or NULL if <b>sl</b>
 591  * is empty.
 592  **/
 593 void *
 594 smartlist_choose(const smartlist_t *sl)
 595 {
 596   int len = smartlist_len(sl);
 597   if (len)
 598     return smartlist_get(sl,crypto_rand_int(len));
 599   return NULL; /* no elements to choose from */
 600 }
 601
 602 /**
 603  * Scramble the elements of <b>sl</b> into a random order.
 604  **/
 605 void
 606 smartlist_shuffle(smartlist_t *sl)
 607 {
 608   int i;
 609   /* From the end of the list to the front, choose at random from the
 610      positions we haven't looked at yet, and swap that position into the
 611      current position.  Remember to give "no swap" the same probability as
 612      any other swap. */
 613   for (i = smartlist_len(sl)-1; i > 0; --i) {
 614     int j = crypto_rand_int(i+1);
 615     smartlist_swap(sl, i, j);
 616   }
 617 }
 618
 619 /** Make sure that openssl is using its default PRNG. Return 1 if we had to
 620  * adjust it; 0 otherwise. */
 621 int
 622 crypto_force_rand_ssleay(void)
 623 {
 624 #ifdef ENABLE_OPENSSL
 625   RAND_METHOD *default_method;
 626   default_method = RAND_OpenSSL();
 627   if (RAND_get_rand_method() != default_method) {
 628     log_notice(LD_CRYPTO, "It appears that one of our engines has provided "
 629                "a replacement the OpenSSL RNG. Resetting it to the default "
 630                "implementation.");
 631     RAND_set_rand_method(default_method);
 632     return 1;
 633   }
 634 #endif /* defined(ENABLE_OPENSSL) */
 635   return 0;
 636 }