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