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 void RandAddSeed()
  69 {
  70     // Seed with CPU performance counter
  71     int64_t nCounter = GetPerformanceCounter();
  72     RAND_add(&nCounter, sizeof(nCounter), 1.5);
  73     memory_cleanse((void*)&nCounter, sizeof(nCounter));
  74 }
  75
  76 static void RandAddSeedPerfmon()
  77 {
  78     RandAddSeed();
  79
  80 #ifdef WIN32
  81     // Don't need this on Linux, OpenSSL automatically uses /dev/urandom
  82     // Seed with the entire set of perfmon data
  83
  84     // This can take up to 2 seconds, so only do it every 10 minutes
  85     static int64_t nLastPerfmon;
  86     if (GetTime() < nLastPerfmon + 10 * 60)
  87         return;
  88     nLastPerfmon = GetTime();
  89
  90     std::vector<unsigned char> vData(250000, 0);
  91     long ret = 0;
  92     unsigned long nSize = 0;
  93     const size_t nMaxSize = 10000000; // Bail out at more than 10MB of performance data
  94     while (true) {
  95         nSize = vData.size();
  96         ret = RegQueryValueExA(HKEY_PERFORMANCE_DATA, "Global", NULL, NULL, vData.data(), &nSize);
  97         if (ret != ERROR_MORE_DATA || vData.size() >= nMaxSize)
  98             break;
  99         vData.resize(std::max((vData.size() * 3) / 2, nMaxSize)); // Grow size of buffer exponentially
 100     }
 101     RegCloseKey(HKEY_PERFORMANCE_DATA);
 102     if (ret == ERROR_SUCCESS) {
 103         RAND_add(vData.data(), nSize, nSize / 100.0);
 104         memory_cleanse(vData.data(), nSize);
 105         LogPrint(BCLog::RAND, "%s: %lu bytes\n", __func__, nSize);
 106     } else {
 107         static bool warned = false; // Warn only once
 108         if (!warned) {
 109             LogPrintf("%s: Warning: RegQueryValueExA(HKEY_PERFORMANCE_DATA) failed with code %i\n", __func__, ret);
 110             warned = true;
 111         }
 112     }
 113 #endif
 114 }
 115
 116 #ifndef WIN32
 117 /** Fallback: get 32 bytes of system entropy from /dev/urandom. The most
 118  * compatible way to get cryptographic randomness on UNIX-ish platforms.
 119  */
 120 void GetDevURandom(unsigned char *ent32)
 121 {
 122     int f = open("/dev/urandom", O_RDONLY);
 123     if (f == -1) {
 124         RandFailure();
 125     }
 126     int have = 0;
 127     do {
 128         ssize_t n = read(f, ent32 + have, NUM_OS_RANDOM_BYTES - have);
 129         if (n <= 0 || n + have > NUM_OS_RANDOM_BYTES) {
 130             RandFailure();
 131         }
 132         have += n;
 133     } while (have < NUM_OS_RANDOM_BYTES);
 134     close(f);
 135 }
 136 #endif
 137
 138 /** Get 32 bytes of system entropy. */
 139 void GetOSRand(unsigned char *ent32)
 140 {
 141 #if defined(WIN32)
 142     HCRYPTPROV hProvider;
 143     int ret = CryptAcquireContextW(&hProvider, NULL, NULL, PROV_RSA_FULL, CRYPT_VERIFYCONTEXT);
 144     if (!ret) {
 145         RandFailure();
 146     }
 147     ret = CryptGenRandom(hProvider, NUM_OS_RANDOM_BYTES, ent32);
 148     if (!ret) {
 149         RandFailure();
 150     }
 151     CryptReleaseContext(hProvider, 0);
 152 #elif defined(HAVE_SYS_GETRANDOM)
 153     /* Linux. From the getrandom(2) man page:
 154      * "If the urandom source has been initialized, reads of up to 256 bytes
 155      * will always return as many bytes as requested and will not be
 156      * interrupted by signals."
 157      */
 158     int rv = syscall(SYS_getrandom, ent32, NUM_OS_RANDOM_BYTES, 0);
 159     if (rv != NUM_OS_RANDOM_BYTES) {
 160         if (rv < 0 && errno == ENOSYS) {
 161             /* Fallback for kernel <3.17: the return value will be -1 and errno
 162              * ENOSYS if the syscall is not available, in that case fall back
 163              * to /dev/urandom.
 164              */
 165             GetDevURandom(ent32);
 166         } else {
 167             RandFailure();
 168         }
 169     }
 170 #elif defined(HAVE_GETENTROPY)
 171     /* On OpenBSD this can return up to 256 bytes of entropy, will return an
 172      * error if more are requested.
 173      * The call cannot return less than the requested number of bytes.
 174      */
 175     if (getentropy(ent32, NUM_OS_RANDOM_BYTES) != 0) {
 176         RandFailure();
 177     }
 178 #elif defined(HAVE_SYSCTL_ARND)
 179     /* FreeBSD and similar. It is possible for the call to return less
 180      * bytes than requested, so need to read in a loop.
 181      */
 182     static const int name[2] = {CTL_KERN, KERN_ARND};
 183     int have = 0;
 184     do {
 185         size_t len = NUM_OS_RANDOM_BYTES - have;
 186         if (sysctl(name, ARRAYLEN(name), ent32 + have, &len, NULL, 0) != 0) {
 187             RandFailure();
 188         }
 189         have += len;
 190     } while (have < NUM_OS_RANDOM_BYTES);
 191 #else
 192     /* Fall back to /dev/urandom if there is no specific method implemented to
 193      * get system entropy for this OS.
 194      */
 195     GetDevURandom(ent32);
 196 #endif
 197 }
 198
 199 void GetRandBytes(unsigned char* buf, int num)
 200 {
 201     if (RAND_bytes(buf, num) != 1) {
 202         RandFailure();
 203     }
 204 }
 205
 206 static void AddDataToRng(void* data, size_t len);
 207
 208 void RandAddSeedSleep()
 209 {
 210     int64_t nPerfCounter1 = GetPerformanceCounter();
 211     std::this_thread::sleep_for(std::chrono::milliseconds(1));
 212     int64_t nPerfCounter2 = GetPerformanceCounter();
 213
 214     // Combine with and update state
 215     AddDataToRng(&nPerfCounter1, sizeof(nPerfCounter1));
 216     AddDataToRng(&nPerfCounter2, sizeof(nPerfCounter2));
 217
 218     memory_cleanse(&nPerfCounter1, sizeof(nPerfCounter1));
 219     memory_cleanse(&nPerfCounter2, sizeof(nPerfCounter2));
 220 }
 221
 222
 223 static std::mutex cs_rng_state;
 224 static unsigned char rng_state[32] = {0};
 225 static uint64_t rng_counter = 0;
 226
 227 static void AddDataToRng(void* data, size_t len) {
 228     CSHA512 hasher;
 229     hasher.Write((const unsigned char*)&len, sizeof(len));
 230     hasher.Write((const unsigned char*)data, len);
 231     unsigned char buf[64];
 232     {
 233         std::unique_lock<std::mutex> lock(cs_rng_state);
 234         hasher.Write(rng_state, sizeof(rng_state));
 235         hasher.Write((const unsigned char*)&rng_counter, sizeof(rng_counter));
 236         ++rng_counter;
 237         hasher.Finalize(buf);
 238         memcpy(rng_state, buf + 32, 32);
 239     }
 240     memory_cleanse(buf, 64);
 241 }
 242
 243 void GetStrongRandBytes(unsigned char* out, int num)
 244 {
 245     assert(num <= 32);
 246     CSHA512 hasher;
 247     unsigned char buf[64];
 248
 249     // First source: OpenSSL's RNG
 250     RandAddSeedPerfmon();
 251     GetRandBytes(buf, 32);
 252     hasher.Write(buf, 32);
 253
 254     // Second source: OS RNG
 255     GetOSRand(buf);
 256     hasher.Write(buf, 32);
 257
 258     // Combine with and update state
 259     {
 260         std::unique_lock<std::mutex> lock(cs_rng_state);
 261         hasher.Write(rng_state, sizeof(rng_state));
 262         hasher.Write((const unsigned char*)&rng_counter, sizeof(rng_counter));
 263         ++rng_counter;
 264         hasher.Finalize(buf);
 265         memcpy(rng_state, buf + 32, 32);
 266     }
 267
 268     // Produce output
 269     memcpy(out, buf, num);
 270     memory_cleanse(buf, 64);
 271 }
 272
 273 uint64_t GetRand(uint64_t nMax)
 274 {
 275     if (nMax == 0)
 276         return 0;
 277
 278     // The range of the random source must be a multiple of the modulus
 279     // to give every possible output value an equal possibility
 280     uint64_t nRange = (std::numeric_limits<uint64_t>::max() / nMax) * nMax;
 281     uint64_t nRand = 0;
 282     do {
 283         GetRandBytes((unsigned char*)&nRand, sizeof(nRand));
 284     } while (nRand >= nRange);
 285     return (nRand % nMax);
 286 }
 287
 288 int GetRandInt(int nMax)
 289 {
 290     return GetRand(nMax);
 291 }
 292
 293 uint256 GetRandHash()
 294 {
 295     uint256 hash;
 296     GetRandBytes((unsigned char*)&hash, sizeof(hash));
 297     return hash;
 298 }
 299
 300 void FastRandomContext::RandomSeed()
 301 {
 302     uint256 seed = GetRandHash();
 303     rng.SetKey(seed.begin(), 32);
 304     requires_seed = false;
 305 }
 306
 307 FastRandomContext::FastRandomContext(const uint256& seed) : requires_seed(false), bytebuf_size(0), bitbuf_size(0)
 308 {
 309     rng.SetKey(seed.begin(), 32);
 310 }
 311
 312 bool Random_SanityCheck()
 313 {
 314     uint64_t start = GetPerformanceCounter();
 315
 316     /* This does not measure the quality of randomness, but it does test that
 317      * OSRandom() overwrites all 32 bytes of the output given a maximum
 318      * number of tries.
 319      */
 320     static const ssize_t MAX_TRIES = 1024;
 321     uint8_t data[NUM_OS_RANDOM_BYTES];
 322     bool overwritten[NUM_OS_RANDOM_BYTES] = {}; /* Tracks which bytes have been overwritten at least once */
 323     int num_overwritten;
 324     int tries = 0;
 325     /* Loop until all bytes have been overwritten at least once, or max number tries reached */
 326     do {
 327         memset(data, 0, NUM_OS_RANDOM_BYTES);
 328         GetOSRand(data);
 329         for (int x=0; x < NUM_OS_RANDOM_BYTES; ++x) {
 330             overwritten[x] |= (data[x] != 0);
 331         }
 332
 333         num_overwritten = 0;
 334         for (int x=0; x < NUM_OS_RANDOM_BYTES; ++x) {
 335             if (overwritten[x]) {
 336                 num_overwritten += 1;
 337             }
 338         }
 339
 340         tries += 1;
 341     } while (num_overwritten < NUM_OS_RANDOM_BYTES && tries < MAX_TRIES);
 342     if (num_overwritten != NUM_OS_RANDOM_BYTES) return false; /* If this failed, bailed out after too many tries */
 343
 344     // Check that GetPerformanceCounter increases at least during a GetOSRand() call + 1ms sleep.
 345     std::this_thread::sleep_for(std::chrono::milliseconds(1));
 346     uint64_t stop = GetPerformanceCounter();
 347     if (stop == start) return false;
 348
 349     // We called GetPerformanceCounter. Use it as entropy.
 350     RAND_add((const unsigned char*)&start, sizeof(start), 1);
 351     RAND_add((const unsigned char*)&stop, sizeof(stop), 1);
 352
 353     return true;
 354 }
 355
 356 FastRandomContext::FastRandomContext(bool fDeterministic) : requires_seed(!fDeterministic), bytebuf_size(0), bitbuf_size(0)
 357 {
 358     if (!fDeterministic) {
 359         return;
 360     }
 361     uint256 seed;
 362     rng.SetKey(seed.begin(), 32);
 363 }