1 files changed, 273 insertions, 49 deletions

diff --git a/src/random.cpp b/src/random.cpp
index 0d20d205a..de7553c82 100644
--- a/src/random.cpp
+++ b/src/random.cpp
@@ -1,34 +1,68 @@
 // Copyright (c) 2009-2010 Satoshi Nakamoto
-// Copyright (c) 2009-2014 The Bitcoin developers
-// Distributed under the MIT/X11 software license, see the accompanying
+// Copyright (c) 2009-2016 The Bitcoin Core developers
+// Distributed under the MIT software license, see the accompanying
 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
 
 #include "random.h"
 
+#include "crypto/sha512.h"
+#include "support/cleanse.h"
 #ifdef WIN32
 #include "compat.h" // for Windows API
+#include <wincrypt.h>
 #endif
-#include "util.h" // for LogPrint()
+#include "util.h"             // for LogPrint()
+#include "utilstrencodings.h" // for GetTime()
+
+#include <stdlib.h>
+#include <limits>
+#include <chrono>
+#include <thread>
 
 #ifndef WIN32
 #include <sys/time.h>
 #endif
 
-#include <openssl/crypto.h>
+#ifdef HAVE_SYS_GETRANDOM
+#include <sys/syscall.h>
+#include <linux/random.h>
+#endif
+#ifdef HAVE_GETENTROPY
+#include <unistd.h>
+#endif
+#ifdef HAVE_SYSCTL_ARND
+#include <sys/sysctl.h>
+#endif
+
+#include <mutex>
+
 #include <openssl/err.h>
 #include <openssl/rand.h>
 
+static void RandFailure()
+{
+    LogPrintf("Failed to read randomness, aborting\n");
+    abort();
+}
+
 static inline int64_t GetPerformanceCounter()
 {
-    int64_t nCounter = 0;
-#ifdef WIN32
-    QueryPerformanceCounter((LARGE_INTEGER*)&nCounter);
+    // Read the hardware time stamp counter when available.
+    // See https://en.wikipedia.org/wiki/Time_Stamp_Counter for more information.
+#if defined(_MSC_VER) && (defined(_M_IX86) || defined(_M_X64))
+    return __rdtsc();
+#elif !defined(_MSC_VER) && defined(__i386__)
+    uint64_t r = 0;
+    __asm__ volatile ("rdtsc" : "=A"(r)); // Constrain the r variable to the eax:edx pair.
+    return r;
+#elif !defined(_MSC_VER) && (defined(__x86_64__) || defined(__amd64__))
+    uint64_t r1 = 0, r2 = 0;
+    __asm__ volatile ("rdtsc" : "=a"(r1), "=d"(r2)); // Constrain r1 to rax and r2 to rdx.
+    return (r2 << 32) | r1;
 #else
-    timeval t;
-    gettimeofday(&t, NULL);
-    nCounter = (int64_t)(t.tv_sec * 1000000 + t.tv_usec);
+    // Fall back to using C++11 clock (usually microsecond or nanosecond precision)
+    return std::chrono::high_resolution_clock::now().time_since_epoch().count();
 #endif
-    return nCounter;
 }
 
 void RandAddSeed()
@@ -36,44 +70,42 @@ void RandAddSeed()
     // Seed with CPU performance counter
     int64_t nCounter = GetPerformanceCounter();
     RAND_add(&nCounter, sizeof(nCounter), 1.5);
-    OPENSSL_cleanse((void*)&nCounter, sizeof(nCounter));
+    memory_cleanse((void*)&nCounter, sizeof(nCounter));
 }
 
-void RandAddSeedPerfmon()
+static void RandAddSeedPerfmon()
 {
     RandAddSeed();
 
+#ifdef WIN32
+    // Don't need this on Linux, OpenSSL automatically uses /dev/urandom
+    // Seed with the entire set of perfmon data
+
     // This can take up to 2 seconds, so only do it every 10 minutes
     static int64_t nLastPerfmon;
     if (GetTime() < nLastPerfmon + 10 * 60)
         return;
     nLastPerfmon = GetTime();
 
-#ifdef WIN32
-    // Don't need this on Linux, OpenSSL automatically uses /dev/urandom
-    // Seed with the entire set of perfmon data
-    std::vector <unsigned char> vData(250000,0);
+    std::vector<unsigned char> vData(250000, 0);
     long ret = 0;
     unsigned long nSize = 0;
     const size_t nMaxSize = 10000000; // Bail out at more than 10MB of performance data
-    while (true)
-    {
+    while (true) {
         nSize = vData.size();
-        ret = RegQueryValueExA(HKEY_PERFORMANCE_DATA, "Global", NULL, NULL, begin_ptr(vData), &nSize);
+        ret = RegQueryValueExA(HKEY_PERFORMANCE_DATA, "Global", NULL, NULL, vData.data(), &nSize);
         if (ret != ERROR_MORE_DATA || vData.size() >= nMaxSize)
             break;
-        vData.resize(std::max((vData.size()*3)/2, nMaxSize)); // Grow size of buffer exponentially
+        vData.resize(std::max((vData.size() * 3) / 2, nMaxSize)); // Grow size of buffer exponentially
     }
     RegCloseKey(HKEY_PERFORMANCE_DATA);
-    if (ret == ERROR_SUCCESS)
-    {
-        RAND_add(begin_ptr(vData), nSize, nSize/100.0);
-        OPENSSL_cleanse(begin_ptr(vData), nSize);
-        LogPrint("rand", "%s: %lu bytes\n", __func__, nSize);
+    if (ret == ERROR_SUCCESS) {
+        RAND_add(vData.data(), nSize, nSize / 100.0);
+        memory_cleanse(vData.data(), nSize);
+        LogPrint(BCLog::RAND, "%s: %lu bytes\n", __func__, nSize);
     } else {
         static bool warned = false; // Warn only once
-        if (!warned)
-        {
+        if (!warned) {
             LogPrintf("%s: Warning: RegQueryValueExA(HKEY_PERFORMANCE_DATA) failed with code %i\n", __func__, ret);
             warned = true;
         }
@@ -81,13 +113,161 @@ void RandAddSeedPerfmon()
 #endif
 }
 
-bool GetRandBytes(unsigned char *buf, int num)
+#ifndef WIN32
+/** Fallback: get 32 bytes of system entropy from /dev/urandom. The most
+ * compatible way to get cryptographic randomness on UNIX-ish platforms.
+ */
+void GetDevURandom(unsigned char *ent32)
+{
+    int f = open("/dev/urandom", O_RDONLY);
+    if (f == -1) {
+        RandFailure();
+    }
+    int have = 0;
+    do {
+        ssize_t n = read(f, ent32 + have, NUM_OS_RANDOM_BYTES - have);
+        if (n <= 0 || n + have > NUM_OS_RANDOM_BYTES) {
+            RandFailure();
+        }
+        have += n;
+    } while (have < NUM_OS_RANDOM_BYTES);
+    close(f);
+}
+#endif
+
+/** Get 32 bytes of system entropy. */
+void GetOSRand(unsigned char *ent32)
+{
+#if defined(WIN32)
+    HCRYPTPROV hProvider;
+    int ret = CryptAcquireContextW(&hProvider, NULL, NULL, PROV_RSA_FULL, CRYPT_VERIFYCONTEXT);
+    if (!ret) {
+        RandFailure();
+    }
+    ret = CryptGenRandom(hProvider, NUM_OS_RANDOM_BYTES, ent32);
+    if (!ret) {
+        RandFailure();
+    }
+    CryptReleaseContext(hProvider, 0);
+#elif defined(HAVE_SYS_GETRANDOM)
+    /* Linux. From the getrandom(2) man page:
+     * "If the urandom source has been initialized, reads of up to 256 bytes
+     * will always return as many bytes as requested and will not be
+     * interrupted by signals."
+     */
+    int rv = syscall(SYS_getrandom, ent32, NUM_OS_RANDOM_BYTES, 0);
+    if (rv != NUM_OS_RANDOM_BYTES) {
+        if (rv < 0 && errno == ENOSYS) {
+            /* Fallback for kernel <3.17: the return value will be -1 and errno
+             * ENOSYS if the syscall is not available, in that case fall back
+             * to /dev/urandom.
+             */
+            GetDevURandom(ent32);
+        } else {
+            RandFailure();
+        }
+    }
+#elif defined(HAVE_GETENTROPY)
+    /* On OpenBSD this can return up to 256 bytes of entropy, will return an
+     * error if more are requested.
+     * The call cannot return less than the requested number of bytes.
+     */
+    if (getentropy(ent32, NUM_OS_RANDOM_BYTES) != 0) {
+        RandFailure();
+    }
+#elif defined(HAVE_SYSCTL_ARND)
+    /* FreeBSD and similar. It is possible for the call to return less
+     * bytes than requested, so need to read in a loop.
+     */
+    static const int name[2] = {CTL_KERN, KERN_ARND};
+    int have = 0;
+    do {
+        size_t len = NUM_OS_RANDOM_BYTES - have;
+        if (sysctl(name, ARRAYLEN(name), ent32 + have, &len, NULL, 0) != 0) {
+            RandFailure();
+        }
+        have += len;
+    } while (have < NUM_OS_RANDOM_BYTES);
+#else
+    /* Fall back to /dev/urandom if there is no specific method implemented to
+     * get system entropy for this OS.
+     */
+    GetDevURandom(ent32);
+#endif
+}
+
+void GetRandBytes(unsigned char* buf, int num)
 {
     if (RAND_bytes(buf, num) != 1) {
-        LogPrintf("%s: OpenSSL RAND_bytes() failed with error: %s\n", __func__, ERR_error_string(ERR_get_error(), NULL));
-        return false;
+        RandFailure();
     }
-    return true;
+}
+
+static void AddDataToRng(void* data, size_t len);
+
+void RandAddSeedSleep()
+{
+    int64_t nPerfCounter1 = GetPerformanceCounter();
+    std::this_thread::sleep_for(std::chrono::milliseconds(1));
+    int64_t nPerfCounter2 = GetPerformanceCounter();
+
+    // Combine with and update state
+    AddDataToRng(&nPerfCounter1, sizeof(nPerfCounter1));
+    AddDataToRng(&nPerfCounter2, sizeof(nPerfCounter2));
+
+    memory_cleanse(&nPerfCounter1, sizeof(nPerfCounter1));
+    memory_cleanse(&nPerfCounter2, sizeof(nPerfCounter2));
+}
+
+
+static std::mutex cs_rng_state;
+static unsigned char rng_state[32] = {0};
+static uint64_t rng_counter = 0;
+
+static void AddDataToRng(void* data, size_t len) {
+    CSHA512 hasher;
+    hasher.Write((const unsigned char*)&len, sizeof(len));
+    hasher.Write((const unsigned char*)data, len);
+    unsigned char buf[64];
+    {
+        std::unique_lock<std::mutex> lock(cs_rng_state);
+        hasher.Write(rng_state, sizeof(rng_state));
+        hasher.Write((const unsigned char*)&rng_counter, sizeof(rng_counter));
+        ++rng_counter;
+        hasher.Finalize(buf);
+        memcpy(rng_state, buf + 32, 32);
+    }
+    memory_cleanse(buf, 64);
+}
+
+void GetStrongRandBytes(unsigned char* out, int num)
+{
+    assert(num <= 32);
+    CSHA512 hasher;
+    unsigned char buf[64];
+
+    // First source: OpenSSL's RNG
+    RandAddSeedPerfmon();
+    GetRandBytes(buf, 32);
+    hasher.Write(buf, 32);
+
+    // Second source: OS RNG
+    GetOSRand(buf);
+    hasher.Write(buf, 32);
+
+    // Combine with and update state
+    {
+        std::unique_lock<std::mutex> lock(cs_rng_state);
+        hasher.Write(rng_state, sizeof(rng_state));
+        hasher.Write((const unsigned char*)&rng_counter, sizeof(rng_counter));
+        ++rng_counter;
+        hasher.Finalize(buf);
+        memcpy(rng_state, buf + 32, 32);
+    }
+
+    // Produce output
+    memcpy(out, buf, num);
+    memory_cleanse(buf, 64);
 }
 
 uint64_t GetRand(uint64_t nMax)
@@ -117,23 +297,67 @@ uint256 GetRandHash()
     return hash;
 }
 
-uint32_t insecure_rand_Rz = 11;
-uint32_t insecure_rand_Rw = 11;
-void seed_insecure_rand(bool fDeterministic)
+void FastRandomContext::RandomSeed()
 {
-    // The seed values have some unlikely fixed points which we avoid.
-    if(fDeterministic)
-    {
-        insecure_rand_Rz = insecure_rand_Rw = 11;
-    } else {
-        uint32_t tmp;
-        do {
-            GetRandBytes((unsigned char*)&tmp, 4);
-        } while(tmp == 0 || tmp == 0x9068ffffU);
-        insecure_rand_Rz = tmp;
-        do {
-            GetRandBytes((unsigned char*)&tmp, 4);
-        } while(tmp == 0 || tmp == 0x464fffffU);
-        insecure_rand_Rw = tmp;
+    uint256 seed = GetRandHash();
+    rng.SetKey(seed.begin(), 32);
+    requires_seed = false;
+}
+
+FastRandomContext::FastRandomContext(const uint256& seed) : requires_seed(false), bytebuf_size(0), bitbuf_size(0)
+{
+    rng.SetKey(seed.begin(), 32);
+}
+
+bool Random_SanityCheck()
+{
+    uint64_t start = GetPerformanceCounter();
+
+    /* This does not measure the quality of randomness, but it does test that
+     * OSRandom() overwrites all 32 bytes of the output given a maximum
+     * number of tries.
+     */
+    static const ssize_t MAX_TRIES = 1024;
+    uint8_t data[NUM_OS_RANDOM_BYTES];
+    bool overwritten[NUM_OS_RANDOM_BYTES] = {}; /* Tracks which bytes have been overwritten at least once */
+    int num_overwritten;
+    int tries = 0;
+    /* Loop until all bytes have been overwritten at least once, or max number tries reached */
+    do {
+        memset(data, 0, NUM_OS_RANDOM_BYTES);
+        GetOSRand(data);
+        for (int x=0; x < NUM_OS_RANDOM_BYTES; ++x) {
+            overwritten[x] |= (data[x] != 0);
+        }
+
+        num_overwritten = 0;
+        for (int x=0; x < NUM_OS_RANDOM_BYTES; ++x) {
+            if (overwritten[x]) {
+                num_overwritten += 1;
+            }
+        }
+
+        tries += 1;
+    } while (num_overwritten < NUM_OS_RANDOM_BYTES && tries < MAX_TRIES);
+    if (num_overwritten != NUM_OS_RANDOM_BYTES) return false; /* If this failed, bailed out after too many tries */
+
+    // Check that GetPerformanceCounter increases at least during a GetOSRand() call + 1ms sleep.
+    std::this_thread::sleep_for(std::chrono::milliseconds(1));
+    uint64_t stop = GetPerformanceCounter();
+    if (stop == start) return false;
+
+    // We called GetPerformanceCounter. Use it as entropy.
+    RAND_add((const unsigned char*)&start, sizeof(start), 1);
+    RAND_add((const unsigned char*)&stop, sizeof(stop), 1);
+
+    return true;
+}
+
+FastRandomContext::FastRandomContext(bool fDeterministic) : requires_seed(!fDeterministic), bytebuf_size(0), bitbuf_size(0)
+{
+    if (!fDeterministic) {
+        return;
     }
+    uint256 seed;
+    rng.SetKey(seed.begin(), 32);
 }