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