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 <openssl/err.h>
  38 #include <openssl/rand.h>
  39
  40 static void RandFailure()
  41 {
  42     LogPrintf("Failed to read randomness, aborting\n");
  43     abort();
  44 }
  45
  46 static inline int64_t GetPerformanceCounter()
  47 {
  48     // Read the hardware time stamp counter when available.
  49     // See https://en.wikipedia.org/wiki/Time_Stamp_Counter for more information.
  50 #if defined(_MSC_VER) && (defined(_M_IX86) || defined(_M_X64))
  51     return __rdtsc();
  52 #elif !defined(_MSC_VER) && defined(__i386__)
  53     uint64_t r = 0;
  54     __asm__ volatile ("rdtsc" : "=A"(r)); // Constrain the r variable to the eax:edx pair.
  55     return r;
  56 #elif !defined(_MSC_VER) && (defined(__x86_64__) || defined(__amd64__))
  57     uint64_t r1 = 0, r2 = 0;
  58     __asm__ volatile ("rdtsc" : "=a"(r1), "=d"(r2)); // Constrain r1 to rax and r2 to rdx.
  59     return (r2 << 32) | r1;
  60 #else
  61     // Fall back to using C++11 clock (usually microsecond or nanosecond precision)
  62     return std::chrono::high_resolution_clock::now().time_since_epoch().count();
  63 #endif
  64 }
  65
  66 void RandAddSeed()
  67 {
  68     // Seed with CPU performance counter
  69     int64_t nCounter = GetPerformanceCounter();
  70     RAND_add(&nCounter, sizeof(nCounter), 1.5);
  71     memory_cleanse((void*)&nCounter, sizeof(nCounter));
  72 }
  73
  74 static void RandAddSeedPerfmon()
  75 {
  76     RandAddSeed();
  77
  78 #ifdef WIN32
  79     // Don't need this on Linux, OpenSSL automatically uses /dev/urandom
  80     // Seed with the entire set of perfmon data
  81
  82     // This can take up to 2 seconds, so only do it every 10 minutes
  83     static int64_t nLastPerfmon;
  84     if (GetTime() < nLastPerfmon + 10 * 60)
  85         return;
  86     nLastPerfmon = GetTime();
  87
  88     std::vector<unsigned char> vData(250000, 0);
  89     long ret = 0;
  90     unsigned long nSize = 0;
  91     const size_t nMaxSize = 10000000; // Bail out at more than 10MB of performance data
  92     while (true) {
  93         nSize = vData.size();
  94         ret = RegQueryValueExA(HKEY_PERFORMANCE_DATA, "Global", NULL, NULL, vData.data(), &nSize);
  95         if (ret != ERROR_MORE_DATA || vData.size() >= nMaxSize)
  96             break;
  97         vData.resize(std::max((vData.size() * 3) / 2, nMaxSize)); // Grow size of buffer exponentially
  98     }
  99     RegCloseKey(HKEY_PERFORMANCE_DATA);
 100     if (ret == ERROR_SUCCESS) {
 101         RAND_add(vData.data(), nSize, nSize / 100.0);
 102         memory_cleanse(vData.data(), nSize);
 103         LogPrint(BCLog::RAND, "%s: %lu bytes\n", __func__, nSize);
 104     } else {
 105         static bool warned = false; // Warn only once
 106         if (!warned) {
 107             LogPrintf("%s: Warning: RegQueryValueExA(HKEY_PERFORMANCE_DATA) failed with code %i\n", __func__, ret);
 108             warned = true;
 109         }
 110     }
 111 #endif
 112 }
 113
 114 #ifndef WIN32
 115 /** Fallback: get 32 bytes of system entropy from /dev/urandom. The most
 116  * compatible way to get cryptographic randomness on UNIX-ish platforms.
 117  */
 118 void GetDevURandom(unsigned char *ent32)
 119 {
 120     int f = open("/dev/urandom", O_RDONLY);
 121     if (f == -1) {
 122         RandFailure();
 123     }
 124     int have = 0;
 125     do {
 126         ssize_t n = read(f, ent32 + have, NUM_OS_RANDOM_BYTES - have);
 127         if (n <= 0 || n + have > NUM_OS_RANDOM_BYTES) {
 128             RandFailure();
 129         }
 130         have += n;
 131     } while (have < NUM_OS_RANDOM_BYTES);
 132     close(f);
 133 }
 134 #endif
 135
 136 /** Get 32 bytes of system entropy. */
 137 void GetOSRand(unsigned char *ent32)
 138 {
 139 #if defined(WIN32)
 140     HCRYPTPROV hProvider;
 141     int ret = CryptAcquireContextW(&hProvider, NULL, NULL, PROV_RSA_FULL, CRYPT_VERIFYCONTEXT);
 142     if (!ret) {
 143         RandFailure();
 144     }
 145     ret = CryptGenRandom(hProvider, NUM_OS_RANDOM_BYTES, ent32);
 146     if (!ret) {
 147         RandFailure();
 148     }
 149     CryptReleaseContext(hProvider, 0);
 150 #elif defined(HAVE_SYS_GETRANDOM)
 151     /* Linux. From the getrandom(2) man page:
 152      * "If the urandom source has been initialized, reads of up to 256 bytes
 153      * will always return as many bytes as requested and will not be
 154      * interrupted by signals."
 155      */
 156     int rv = syscall(SYS_getrandom, ent32, NUM_OS_RANDOM_BYTES, 0);
 157     if (rv != NUM_OS_RANDOM_BYTES) {
 158         if (rv < 0 && errno == ENOSYS) {
 159             /* Fallback for kernel <3.17: the return value will be -1 and errno
 160              * ENOSYS if the syscall is not available, in that case fall back
 161              * to /dev/urandom.
 162              */
 163             GetDevURandom(ent32);
 164         } else {
 165             RandFailure();
 166         }
 167     }
 168 #elif defined(HAVE_GETENTROPY)
 169     /* On OpenBSD this can return up to 256 bytes of entropy, will return an
 170      * error if more are requested.
 171      * The call cannot return less than the requested number of bytes.
 172      */
 173     if (getentropy(ent32, NUM_OS_RANDOM_BYTES) != 0) {
 174         RandFailure();
 175     }
 176 #elif defined(HAVE_SYSCTL_ARND)
 177     /* FreeBSD and similar. It is possible for the call to return less
 178      * bytes than requested, so need to read in a loop.
 179      */
 180     static const int name[2] = {CTL_KERN, KERN_ARND};
 181     int have = 0;
 182     do {
 183         size_t len = NUM_OS_RANDOM_BYTES - have;
 184         if (sysctl(name, ARRAYLEN(name), ent32 + have, &len, NULL, 0) != 0) {
 185             RandFailure();
 186         }
 187         have += len;
 188     } while (have < NUM_OS_RANDOM_BYTES);
 189 #else
 190     /* Fall back to /dev/urandom if there is no specific method implemented to
 191      * get system entropy for this OS.
 192      */
 193     GetDevURandom(ent32);
 194 #endif
 195 }
 196
 197 void GetRandBytes(unsigned char* buf, int num)
 198 {
 199     if (RAND_bytes(buf, num) != 1) {
 200         RandFailure();
 201     }
 202 }
 203
 204 void GetStrongRandBytes(unsigned char* out, int num)
 205 {
 206     assert(num <= 32);
 207     CSHA512 hasher;
 208     unsigned char buf[64];
 209
 210     // First source: OpenSSL's RNG
 211     RandAddSeedPerfmon();
 212     GetRandBytes(buf, 32);
 213     hasher.Write(buf, 32);
 214
 215     // Second source: OS RNG
 216     GetOSRand(buf);
 217     hasher.Write(buf, 32);
 218
 219     // Produce output
 220     hasher.Finalize(buf);
 221     memcpy(out, buf, num);
 222     memory_cleanse(buf, 64);
 223 }
 224
 225 uint64_t GetRand(uint64_t nMax)
 226 {
 227     if (nMax == 0)
 228         return 0;
 229
 230     // The range of the random source must be a multiple of the modulus
 231     // to give every possible output value an equal possibility
 232     uint64_t nRange = (std::numeric_limits<uint64_t>::max() / nMax) * nMax;
 233     uint64_t nRand = 0;
 234     do {
 235         GetRandBytes((unsigned char*)&nRand, sizeof(nRand));
 236     } while (nRand >= nRange);
 237     return (nRand % nMax);
 238 }
 239
 240 int GetRandInt(int nMax)
 241 {
 242     return GetRand(nMax);
 243 }
 244
 245 uint256 GetRandHash()
 246 {
 247     uint256 hash;
 248     GetRandBytes((unsigned char*)&hash, sizeof(hash));
 249     return hash;
 250 }
 251
 252 void FastRandomContext::RandomSeed()
 253 {
 254     uint256 seed = GetRandHash();
 255     rng.SetKey(seed.begin(), 32);
 256     requires_seed = false;
 257 }
 258
 259 FastRandomContext::FastRandomContext(const uint256& seed) : requires_seed(false), bytebuf_size(0), bitbuf_size(0)
 260 {
 261     rng.SetKey(seed.begin(), 32);
 262 }
 263
 264 bool Random_SanityCheck()
 265 {
 266     uint64_t start = GetPerformanceCounter();
 267
 268     /* This does not measure the quality of randomness, but it does test that
 269      * OSRandom() overwrites all 32 bytes of the output given a maximum
 270      * number of tries.
 271      */
 272     static const ssize_t MAX_TRIES = 1024;
 273     uint8_t data[NUM_OS_RANDOM_BYTES];
 274     bool overwritten[NUM_OS_RANDOM_BYTES] = {}; /* Tracks which bytes have been overwritten at least once */
 275     int num_overwritten;
 276     int tries = 0;
 277     /* Loop until all bytes have been overwritten at least once, or max number tries reached */
 278     do {
 279         memset(data, 0, NUM_OS_RANDOM_BYTES);
 280         GetOSRand(data);
 281         for (int x=0; x < NUM_OS_RANDOM_BYTES; ++x) {
 282             overwritten[x] |= (data[x] != 0);
 283         }
 284
 285         num_overwritten = 0;
 286         for (int x=0; x < NUM_OS_RANDOM_BYTES; ++x) {
 287             if (overwritten[x]) {
 288                 num_overwritten += 1;
 289             }
 290         }
 291
 292         tries += 1;
 293     } while (num_overwritten < NUM_OS_RANDOM_BYTES && tries < MAX_TRIES);
 294     if (num_overwritten != NUM_OS_RANDOM_BYTES) return false; /* If this failed, bailed out after too many tries */
 295
 296     // Check that GetPerformanceCounter increases at least during a GetOSRand() call + 1ms sleep.
 297     std::this_thread::sleep_for(std::chrono::milliseconds(1));
 298     uint64_t stop = GetPerformanceCounter();
 299     if (stop == start) return false;
 300
 301     return true;
 302 }
 303
 304 FastRandomContext::FastRandomContext(bool fDeterministic) : requires_seed(!fDeterministic), bytebuf_size(0), bitbuf_size(0)
 305 {
 306     if (!fDeterministic) {
 307         return;
 308     }
 309     uint256 seed;
 310     rng.SetKey(seed.begin(), 32);
 311 }