src/random.cpp

   1 // Copyright (c) 2009-2010 Satoshi Nakamoto
   2 // Copyright (c) 2009-2016 The Bitcoin Core developers
   3 // Distributed under the MIT software license, see the accompanying
   4 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
   5
   6 #include "random.h"
   7
   8 #include "crypto/sha512.h"
   9 #include "support/cleanse.h"
  10 #ifdef WIN32
  11 #include "compat.h" // for Windows API
  12 #include <wincrypt.h>
  13 #endif
  14 #include "util.h"             // for LogPrint()
  15 #include "utilstrencodings.h" // for GetTime()
  16
  17 #include <stdlib.h>
  18 #include <limits>
  19 #include <chrono>
  20 #include <thread>
  21
  22 #ifndef WIN32
  23 #include <sys/time.h>
  24 #endif
  25
  26 #ifdef HAVE_SYS_GETRANDOM
  27 #include <sys/syscall.h>
  28 #include <linux/random.h>
  29 #endif
  30 #if defined(HAVE_GETENTROPY) || (defined(HAVE_GETENTROPY_RAND) && defined(MAC_OSX))
  31 #include <unistd.h>
  32 #endif
  33 #if defined(HAVE_GETENTROPY_RAND) && defined(MAC_OSX)
  34 #include <sys/random.h>
  35 #endif
  36 #ifdef HAVE_SYSCTL_ARND
  37 #include <sys/sysctl.h>
  38 #endif
  39
  40 #include <mutex>
  41
  42 #if defined(__x86_64__) || defined(__amd64__) || defined(__i386__)
  43 #include <cpuid.h>
  44 #endif
  45
  46 #include <openssl/err.h>
  47 #include <openssl/rand.h>
  48
  49 [[noreturn]] static void RandFailure()
  50 {
  51     LogPrintf("Failed to read randomness, aborting\n");
  52     std::abort();
  53 }
  54
  55 static inline int64_t GetPerformanceCounter()
  56 {
  57     // Read the hardware time stamp counter when available.
  58     // See https://en.wikipedia.org/wiki/Time_Stamp_Counter for more information.
  59 #if defined(_MSC_VER) && (defined(_M_IX86) || defined(_M_X64))
  60     return __rdtsc();
  61 #elif !defined(_MSC_VER) && defined(__i386__)
  62     uint64_t r = 0;
  63     __asm__ volatile ("rdtsc" : "=A"(r)); // Constrain the r variable to the eax:edx pair.
  64     return r;
  65 #elif !defined(_MSC_VER) && (defined(__x86_64__) || defined(__amd64__))
  66     uint64_t r1 = 0, r2 = 0;
  67     __asm__ volatile ("rdtsc" : "=a"(r1), "=d"(r2)); // Constrain r1 to rax and r2 to rdx.
  68     return (r2 << 32) | r1;
  69 #else
  70     // Fall back to using C++11 clock (usually microsecond or nanosecond precision)
  71     return std::chrono::high_resolution_clock::now().time_since_epoch().count();
  72 #endif
  73 }
  74
  75
  76 #if defined(__x86_64__) || defined(__amd64__) || defined(__i386__)
  77 static std::atomic<bool> hwrand_initialized{false};
  78 static bool rdrand_supported = false;
  79 static constexpr uint32_t CPUID_F1_ECX_RDRAND = 0x40000000;
  80 static void RDRandInit()
  81 {
  82     uint32_t eax, ebx, ecx, edx;
  83     if (__get_cpuid(1, &eax, &ebx, &ecx, &edx) && (ecx & CPUID_F1_ECX_RDRAND)) {
  84         LogPrintf("Using RdRand as an additional entropy source\n");
  85         rdrand_supported = true;
  86     }
  87     hwrand_initialized.store(true);
  88 }
  89 #else
  90 static void RDRandInit() {}
  91 #endif
  92
  93 static bool GetHWRand(unsigned char* ent32) {
  94 #if defined(__x86_64__) || defined(__amd64__) || defined(__i386__)
  95     assert(hwrand_initialized.load(std::memory_order_relaxed));
  96     if (rdrand_supported) {
  97         uint8_t ok;
  98         // Not all assemblers support the rdrand instruction, write it in hex.
  99 #ifdef __i386__
 100         for (int iter = 0; iter < 4; ++iter) {
 101             uint32_t r1, r2;
 102             __asm__ volatile (".byte 0x0f, 0xc7, 0xf0;" // rdrand %eax
 103                               ".byte 0x0f, 0xc7, 0xf2;" // rdrand %edx
 104                               "setc %2" :
 105                               "=a"(r1), "=d"(r2), "=q"(ok) :: "cc");
 106             if (!ok) return false;
 107             WriteLE32(ent32 + 8 * iter, r1);
 108             WriteLE32(ent32 + 8 * iter + 4, r2);
 109         }
 110 #else
 111         uint64_t r1, r2, r3, r4;
 112         __asm__ volatile (".byte 0x48, 0x0f, 0xc7, 0xf0, " // rdrand %rax
 113                                 "0x48, 0x0f, 0xc7, 0xf3, " // rdrand %rbx
 114                                 "0x48, 0x0f, 0xc7, 0xf1, " // rdrand %rcx
 115                                 "0x48, 0x0f, 0xc7, 0xf2; " // rdrand %rdx
 116                           "setc %4" :
 117                           "=a"(r1), "=b"(r2), "=c"(r3), "=d"(r4), "=q"(ok) :: "cc");
 118         if (!ok) return false;
 119         WriteLE64(ent32, r1);
 120         WriteLE64(ent32 + 8, r2);
 121         WriteLE64(ent32 + 16, r3);
 122         WriteLE64(ent32 + 24, r4);
 123 #endif
 124         return true;
 125     }
 126 #endif
 127     return false;
 128 }
 129
 130 void RandAddSeed()
 131 {
 132     // Seed with CPU performance counter
 133     int64_t nCounter = GetPerformanceCounter();
 134     RAND_add(&nCounter, sizeof(nCounter), 1.5);
 135     memory_cleanse((void*)&nCounter, sizeof(nCounter));
 136 }
 137
 138 static void RandAddSeedPerfmon()
 139 {
 140     RandAddSeed();
 141
 142 #ifdef WIN32
 143     // Don't need this on Linux, OpenSSL automatically uses /dev/urandom
 144     // Seed with the entire set of perfmon data
 145
 146     // This can take up to 2 seconds, so only do it every 10 minutes
 147     static int64_t nLastPerfmon;
 148     if (GetTime() < nLastPerfmon + 10 * 60)
 149         return;
 150     nLastPerfmon = GetTime();
 151
 152     std::vector<unsigned char> vData(250000, 0);
 153     long ret = 0;
 154     unsigned long nSize = 0;
 155     const size_t nMaxSize = 10000000; // Bail out at more than 10MB of performance data
 156     while (true) {
 157         nSize = vData.size();
 158         ret = RegQueryValueExA(HKEY_PERFORMANCE_DATA, "Global", nullptr, nullptr, vData.data(), &nSize);
 159         if (ret != ERROR_MORE_DATA || vData.size() >= nMaxSize)
 160             break;
 161         vData.resize(std::max((vData.size() * 3) / 2, nMaxSize)); // Grow size of buffer exponentially
 162     }
 163     RegCloseKey(HKEY_PERFORMANCE_DATA);
 164     if (ret == ERROR_SUCCESS) {
 165         RAND_add(vData.data(), nSize, nSize / 100.0);
 166         memory_cleanse(vData.data(), nSize);
 167         LogPrint(BCLog::RAND, "%s: %lu bytes\n", __func__, nSize);
 168     } else {
 169         static bool warned = false; // Warn only once
 170         if (!warned) {
 171             LogPrintf("%s: Warning: RegQueryValueExA(HKEY_PERFORMANCE_DATA) failed with code %i\n", __func__, ret);
 172             warned = true;
 173         }
 174     }
 175 #endif
 176 }
 177
 178 #ifndef WIN32
 179 /** Fallback: get 32 bytes of system entropy from /dev/urandom. The most
 180  * compatible way to get cryptographic randomness on UNIX-ish platforms.
 181  */
 182 void GetDevURandom(unsigned char *ent32)
 183 {
 184     int f = open("/dev/urandom", O_RDONLY);
 185     if (f == -1) {
 186         RandFailure();
 187     }
 188     int have = 0;
 189     do {
 190         ssize_t n = read(f, ent32 + have, NUM_OS_RANDOM_BYTES - have);
 191         if (n <= 0 || n + have > NUM_OS_RANDOM_BYTES) {
 192             close(f);
 193             RandFailure();
 194         }
 195         have += n;
 196     } while (have < NUM_OS_RANDOM_BYTES);
 197     close(f);
 198 }
 199 #endif
 200
 201 /** Get 32 bytes of system entropy. */
 202 void GetOSRand(unsigned char *ent32)
 203 {
 204 #if defined(WIN32)
 205     HCRYPTPROV hProvider;
 206     int ret = CryptAcquireContextW(&hProvider, nullptr, nullptr, PROV_RSA_FULL, CRYPT_VERIFYCONTEXT);
 207     if (!ret) {
 208         RandFailure();
 209     }
 210     ret = CryptGenRandom(hProvider, NUM_OS_RANDOM_BYTES, ent32);
 211     if (!ret) {
 212         RandFailure();
 213     }
 214     CryptReleaseContext(hProvider, 0);
 215 #elif defined(HAVE_SYS_GETRANDOM)
 216     /* Linux. From the getrandom(2) man page:
 217      * "If the urandom source has been initialized, reads of up to 256 bytes
 218      * will always return as many bytes as requested and will not be
 219      * interrupted by signals."
 220      */
 221     int rv = syscall(SYS_getrandom, ent32, NUM_OS_RANDOM_BYTES, 0);
 222     if (rv != NUM_OS_RANDOM_BYTES) {
 223         if (rv < 0 && errno == ENOSYS) {
 224             /* Fallback for kernel <3.17: the return value will be -1 and errno
 225              * ENOSYS if the syscall is not available, in that case fall back
 226              * to /dev/urandom.
 227              */
 228             GetDevURandom(ent32);
 229         } else {
 230             RandFailure();
 231         }
 232     }
 233 #elif defined(HAVE_GETENTROPY) && defined(__OpenBSD__)
 234     /* On OpenBSD this can return up to 256 bytes of entropy, will return an
 235      * error if more are requested.
 236      * The call cannot return less than the requested number of bytes.
 237        getentropy is explicitly limited to openbsd here, as a similar (but not
 238        the same) function may exist on other platforms via glibc.
 239      */
 240     if (getentropy(ent32, NUM_OS_RANDOM_BYTES) != 0) {
 241         RandFailure();
 242     }
 243 #elif defined(HAVE_GETENTROPY_RAND) && defined(MAC_OSX)
 244     // We need a fallback for OSX < 10.12
 245     if (&getentropy != nullptr) {
 246         if (getentropy(ent32, NUM_OS_RANDOM_BYTES) != 0) {
 247             RandFailure();
 248         }
 249     } else {
 250         GetDevURandom(ent32);
 251     }
 252 #elif defined(HAVE_SYSCTL_ARND)
 253     /* FreeBSD and similar. It is possible for the call to return less
 254      * bytes than requested, so need to read in a loop.
 255      */
 256     static const int name[2] = {CTL_KERN, KERN_ARND};
 257     int have = 0;
 258     do {
 259         size_t len = NUM_OS_RANDOM_BYTES - have;
 260         if (sysctl(name, ARRAYLEN(name), ent32 + have, &len, nullptr, 0) != 0) {
 261             RandFailure();
 262         }
 263         have += len;
 264     } while (have < NUM_OS_RANDOM_BYTES);
 265 #else
 266     /* Fall back to /dev/urandom if there is no specific method implemented to
 267      * get system entropy for this OS.
 268      */
 269     GetDevURandom(ent32);
 270 #endif
 271 }
 272
 273 void GetRandBytes(unsigned char* buf, int num)
 274 {
 275     if (RAND_bytes(buf, num) != 1) {
 276         RandFailure();
 277     }
 278 }
 279
 280 static void AddDataToRng(void* data, size_t len);
 281
 282 void RandAddSeedSleep()
 283 {
 284     int64_t nPerfCounter1 = GetPerformanceCounter();
 285     std::this_thread::sleep_for(std::chrono::milliseconds(1));
 286     int64_t nPerfCounter2 = GetPerformanceCounter();
 287
 288     // Combine with and update state
 289     AddDataToRng(&nPerfCounter1, sizeof(nPerfCounter1));
 290     AddDataToRng(&nPerfCounter2, sizeof(nPerfCounter2));
 291
 292     memory_cleanse(&nPerfCounter1, sizeof(nPerfCounter1));
 293     memory_cleanse(&nPerfCounter2, sizeof(nPerfCounter2));
 294 }
 295
 296
 297 static std::mutex cs_rng_state;
 298 static unsigned char rng_state[32] = {0};
 299 static uint64_t rng_counter = 0;
 300
 301 static void AddDataToRng(void* data, size_t len) {
 302     CSHA512 hasher;
 303     hasher.Write((const unsigned char*)&len, sizeof(len));
 304     hasher.Write((const unsigned char*)data, len);
 305     unsigned char buf[64];
 306     {
 307         std::unique_lock<std::mutex> lock(cs_rng_state);
 308         hasher.Write(rng_state, sizeof(rng_state));
 309         hasher.Write((const unsigned char*)&rng_counter, sizeof(rng_counter));
 310         ++rng_counter;
 311         hasher.Finalize(buf);
 312         memcpy(rng_state, buf + 32, 32);
 313     }
 314     memory_cleanse(buf, 64);
 315 }
 316
 317 void GetStrongRandBytes(unsigned char* out, int num)
 318 {
 319     assert(num <= 32);
 320     CSHA512 hasher;
 321     unsigned char buf[64];
 322
 323     // First source: OpenSSL's RNG
 324     RandAddSeedPerfmon();
 325     GetRandBytes(buf, 32);
 326     hasher.Write(buf, 32);
 327
 328     // Second source: OS RNG
 329     GetOSRand(buf);
 330     hasher.Write(buf, 32);
 331
 332     // Third source: HW RNG, if available.
 333     if (GetHWRand(buf)) {
 334         hasher.Write(buf, 32);
 335     }
 336
 337     // Combine with and update state
 338     {
 339         std::unique_lock<std::mutex> lock(cs_rng_state);
 340         hasher.Write(rng_state, sizeof(rng_state));
 341         hasher.Write((const unsigned char*)&rng_counter, sizeof(rng_counter));
 342         ++rng_counter;
 343         hasher.Finalize(buf);
 344         memcpy(rng_state, buf + 32, 32);
 345     }
 346
 347     // Produce output
 348     memcpy(out, buf, num);
 349     memory_cleanse(buf, 64);
 350 }
 351
 352 uint64_t GetRand(uint64_t nMax)
 353 {
 354     if (nMax == 0)
 355         return 0;
 356
 357     // The range of the random source must be a multiple of the modulus
 358     // to give every possible output value an equal possibility
 359     uint64_t nRange = (std::numeric_limits<uint64_t>::max() / nMax) * nMax;
 360     uint64_t nRand = 0;
 361     do {
 362         GetRandBytes((unsigned char*)&nRand, sizeof(nRand));
 363     } while (nRand >= nRange);
 364     return (nRand % nMax);
 365 }
 366
 367 int GetRandInt(int nMax)
 368 {
 369     return GetRand(nMax);
 370 }
 371
 372 uint256 GetRandHash()
 373 {
 374     uint256 hash;
 375     GetRandBytes((unsigned char*)&hash, sizeof(hash));
 376     return hash;
 377 }
 378
 379 void FastRandomContext::RandomSeed()
 380 {
 381     uint256 seed = GetRandHash();
 382     rng.SetKey(seed.begin(), 32);
 383     requires_seed = false;
 384 }
 385
 386 uint256 FastRandomContext::rand256()
 387 {
 388     if (bytebuf_size < 32) {
 389         FillByteBuffer();
 390     }
 391     uint256 ret;
 392     memcpy(ret.begin(), bytebuf + 64 - bytebuf_size, 32);
 393     bytebuf_size -= 32;
 394     return ret;
 395 }
 396
 397 std::vector<unsigned char> FastRandomContext::randbytes(size_t len)
 398 {
 399     std::vector<unsigned char> ret(len);
 400     if (len > 0) {
 401         rng.Output(&ret[0], len);
 402     }
 403     return ret;
 404 }
 405
 406 FastRandomContext::FastRandomContext(const uint256& seed) : requires_seed(false), bytebuf_size(0), bitbuf_size(0)
 407 {
 408     rng.SetKey(seed.begin(), 32);
 409 }
 410
 411 bool Random_SanityCheck()
 412 {
 413     uint64_t start = GetPerformanceCounter();
 414
 415     /* This does not measure the quality of randomness, but it does test that
 416      * OSRandom() overwrites all 32 bytes of the output given a maximum
 417      * number of tries.
 418      */
 419     static const ssize_t MAX_TRIES = 1024;
 420     uint8_t data[NUM_OS_RANDOM_BYTES];
 421     bool overwritten[NUM_OS_RANDOM_BYTES] = {}; /* Tracks which bytes have been overwritten at least once */
 422     int num_overwritten;
 423     int tries = 0;
 424     /* Loop until all bytes have been overwritten at least once, or max number tries reached */
 425     do {
 426         memset(data, 0, NUM_OS_RANDOM_BYTES);
 427         GetOSRand(data);
 428         for (int x=0; x < NUM_OS_RANDOM_BYTES; ++x) {
 429             overwritten[x] |= (data[x] != 0);
 430         }
 431
 432         num_overwritten = 0;
 433         for (int x=0; x < NUM_OS_RANDOM_BYTES; ++x) {
 434             if (overwritten[x]) {
 435                 num_overwritten += 1;
 436             }
 437         }
 438
 439         tries += 1;
 440     } while (num_overwritten < NUM_OS_RANDOM_BYTES && tries < MAX_TRIES);
 441     if (num_overwritten != NUM_OS_RANDOM_BYTES) return false; /* If this failed, bailed out after too many tries */
 442
 443     // Check that GetPerformanceCounter increases at least during a GetOSRand() call + 1ms sleep.
 444     std::this_thread::sleep_for(std::chrono::milliseconds(1));
 445     uint64_t stop = GetPerformanceCounter();
 446     if (stop == start) return false;
 447
 448     // We called GetPerformanceCounter. Use it as entropy.
 449     RAND_add((const unsigned char*)&start, sizeof(start), 1);
 450     RAND_add((const unsigned char*)&stop, sizeof(stop), 1);
 451
 452     return true;
 453 }
 454
 455 FastRandomContext::FastRandomContext(bool fDeterministic) : requires_seed(!fDeterministic), bytebuf_size(0), bitbuf_size(0)
 456 {
 457     if (!fDeterministic) {
 458         return;
 459     }
 460     uint256 seed;
 461     rng.SetKey(seed.begin(), 32);
 462 }
 463
 464 void RandomInit()
 465 {
 466     RDRandInit();
 467 }